Страница: 1 |
Страница: 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-сайт:
Профиль | | #1
Добавлено: 29.03.05 04:47
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
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-сайт:
Профиль | | #3
Добавлено: 29.03.05 06:00
Для всех возможных подмножеств данного множества чисел берется их сумма и в массиве записывается, что такую сумму числа из этого множества образовывать могут. Затем смотрится, какое минимальное натуральное число не помечено, как возможная сумма.