IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> последовательность чисел, выбрать подпоследовательность, сумма равна числу
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 7
Пол: Женский
Реальное имя: Наталья

Репутация: -  0  +


Даны натуральные числа 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

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

Сообщение отредактировано: Цырилла -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






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





Группа: Пользователи
Сообщений: 7
Пол: Женский
Реальное имя: Наталья

Репутация: -  0  +


Критериев нет, если существует несколько возможностей за ответ принять первую получившуюся
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Цырилла @ 20.02.2007 20:57) *

не использовать же тупой перебор чисел с суммированием?

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5





Группа: Пользователи
Сообщений: 7
Пол: Женский
Реальное имя: Наталья

Репутация: -  0  +


Спасибо за подсказку.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 3:28
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name