Версия для печати темы

Автор: Цырилла 21.02.2007 0:57

Даны натуральные числа K, A1, …, An. В последовательности A1, …, An выбрать подпоследовательность Ai1, Ai2, … Aij (0<=i1<i2< … <ij<=n) такую, что Ai1+ … +Aij = K.
Сообщить, если такая подпоследовательность не существует.

ввод
19
5 3 34 24 5 15 3 5 6 1
вывод: 5 3 5 6

Программу сама напишу, но алгоритм не доходит - не использовать же тупой перебор чисел с суммированием?

Автор: volvo 21.02.2007 1:49

Почему не
5 3 34 24 5 15 3 5 6 1
или
5 3 34 24 5 15 3 5 6 1
?
Чем приведенная тобой подпосдледовательность лучше? Есть еще какие-то критерии?

Автор: Цырилла 21.02.2007 12:43

Критериев нет, если существует несколько возможностей за ответ принять первую получившуюся

Автор: Lapp 21.02.2007 14:22

Боюсь, что "тупого перебора" тут не избежать. Это оправдано в целом, так как изначальная последовательность не регламентирована. Можно, конечно, снчала пройтись по ней и выкинуть члены, которые сами по себе превосходят требуемую сумму - только потом все равно: вакамба! И то, это только в случае положительных Ai..

Единственная (но немалая) радость состоит в том, что перебор этот можно сделать рекуррентно . Делаешь процедуру, входными параметрами которой является текущая сумма S и следующая позиция M в изначальной последовательности. В процедуре устраиваешь цикл по элементам от M до N. В этом цикле прибавляешь к S текущий (L-ый, M<=L<=N) элемент и смотришь: если сумма равнв K - выход из программы с триумфом, если нет - вызываешь эту же процедуру с параметрами S+AL и L+1. После этого просто вызываешь в главной программе эту процедуру с параметрами 0 и 1 - и дело в шляпе..
Если последовательность существенно положительная, также целесообразно устраивать проверку на переполнение (S>K), чтоб ускорить процесс..

Автор: Цырилла 25.02.2007 1:31

Спасибо за подсказку.