Visual Basic, .NET, ASP, VBScript
 

   
   
     

Форум - Олимпиады

Страница: 1 |

 

  Вопрос: Очень простая задача , OPEN ME :) Добавлено: 29.03.05 03:49  

Автор вопроса:  Карась
Задача "Отсутствующая сумма
Задана неубывающая последовательность натуральных чисел.
Составе программу, которая находит такие наименьшее натуральное число, которое нельзя представить в виде суммы некоторых
элементов заданной последовательности (каждое слагаемое входит в сумму по одному разу)

Пример

Входные данные: Выходные данные:
1 2 3 3 10 21 31 57 20

Ответить

  Ответы Всего ответов: 3  

Номер ответа: 1
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
 Web-сайт: sharpc.livejournal.com
 Профиль | | #1
Добавлено: 29.03.05 04:47
Private Sub Command1_Click()
    Dim a() As Long, b() As Long
    Dim s As Long
    s = 0
    ReDim b(UBound(Split(Text1, " ";)))
    For i = 0 To UBound(b)
        b(i) = Val(Split(Text1, " ";)(i))
    Next
    For i = 0 To UBound(b)
        s = s + b(i)
    Next
    ReDim a(s)
    For i = 0 To 2 ^ (UBound(b) + 1) - 1
        s = 0
        For j = 0 To UBound(b)
            s = s + IIf((i And 2 ^ j), b(j), 0)
        Next
        a(s) = 1
    Next
    For i = 1 To UBound(a)
        If a(i) = 0 Then Exit For
    Next
    MsgBox i
End Sub

Ответить

Номер ответа: 2
Автор ответа:
 Карась



Вопросов: 6
Ответов: 10
 Профиль | | #2 Добавлено: 29.03.05 05:13
А объяснить можешь алгоритм.

Ответить

Номер ответа: 3
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
 Web-сайт: sharpc.livejournal.com
 Профиль | | #3
Добавлено: 29.03.05 06:00
Для всех возможных подмножеств данного множества чисел берется их сумма и в массиве записывается, что такую сумму числа из этого множества образовывать могут. Затем смотрится, какое минимальное натуральное число не помечено, как возможная сумма.

Ответить

Страница: 1 |

Поиск по форуму



© Copyright 2002-2011 VBNet.RU | Пишите нам