Суммирование чисел из файла |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Суммирование чисел из файла |
Huver |
14.11.2005 15:32
Сообщение
#1
|
Группа: Пользователи Сообщений: 3 Пол: Мужской Репутация: 0 |
Задача:
Дано N целых чисел A1, A2 ... An. Требуется найти кол-во различных сумм вида k1A1 + k2A2 + ... + knAn. Ввод из файла sums.in. В первой строке находится число N, во второй - A1, A2 ... An через пробел. Вывод в файл sums.out. Вывести одно число - количество различных значений сумм. Пример 1: Ввод 1 3 1 1 2 Вывод 1 5 Пример 2: Ввод 2 5 49 100 98 49 0 Вывод 3 10 Заранее спасибо. Сообщение отредактировано: Huver - 14.11.2005 18:39 |
volvo |
14.11.2005 16:06
Сообщение
#2
|
Гость |
Сначала уточни, что значит
Цитата кол-во различных сумм ? Именно на примере 1, 2, 3 что должно быть выведено? |
Huver |
14.11.2005 18:19
Сообщение
#3
|
Группа: Пользователи Сообщений: 3 Пол: Мужской Репутация: 0 |
В файле sums.in записывается вручную:
3 //кол-во чисел 1 1 2 //числа через пробел Необходимо вычеслить кол-во различных значений сумм и записать результат в файл sums.out ввиде: Ввод 1 3 1 1 2 Вывод 1 3 //результат Поиск различных сумм (складываются все возможные варианты чисел): 1+1=2 1+1=2 1+2=3 2+1=3 2+1=3 1+1+2=4 1+2+1=4 2+1+1=4 2+1+1=4 Результат: кол-во различных сумм: 3. Сообщение отредактировано: Huver - 14.11.2005 18:20 |
volvo |
14.11.2005 18:29
Сообщение
#4
|
Гость |
разложение числа ничего не напоминает?
|
FreeMan |
14.11.2005 18:41
Сообщение
#5
|
- Группа: Пользователи Сообщений: 480 Пол: Мужской Репутация: 4 |
Суммированием всех чисел находишь максимум. Потом каждое число меньшее максимума раскладываешь на слагаемые. Если все слагаемые есть в файле, тогда это число подходит. Увеличиваем кол-во сумм, переходим к следующему числу.
-------------------- бб
|
volvo |
14.11.2005 18:44
Сообщение
#6
|
Гость |
To: FreeMan
Объясни мне, в свете твоего алгоритма, 1+2=3 и 2+1=3 это разные суммы? |
klem4 |
14.11.2005 18:45
Сообщение
#7
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Я предлагаю забить числа из файла в массив, а потом ипользовать прогу, которая находится по ссылке, которую дал volvo. Там решена абсолютно такая-же задача, только без файла.
-------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Huver |
14.11.2005 19:23
Сообщение
#8
|
Группа: Пользователи Сообщений: 3 Пол: Мужской Репутация: 0 |
To: volvo
значение сумм одинаковое, а порядок разный 1[1] 1[2] 2 1[1]+2=3 1[2]+2=3 |
FreeMan |
15.11.2005 9:39
Сообщение
#9
|
- Группа: Пользователи Сообщений: 480 Пол: Мужской Репутация: 4 |
To: volvo
Нашёл ты первую сумму. 1+2=3. Посмотрел, что 1 и 2 есть в файле. Если есть, то 3 подходит, переходишь к проверке 2. -------------------- бб
|
volvo |
15.11.2005 9:42
Сообщение
#10
|
Гость |
Угу... Продолжаем. Нашел вторую, 2+1=3, посмотрел, 1 и 2 есть в файле, увеличиваем счетчик... А не надо, т.к. это просто перестановка уже существующей суммы.
Стоп. Huver, ты бы для себя решил, чего тебе надо. В первом посте ты пишешь, что для Цитата <1, 1, 2> результат будет 5, в посте №3 - для той же входной последовательности результат уже равен 3...Вопрос: Что будет ПРАВИЛЬНЫМ результатом? |
FreeMan |
15.11.2005 9:53
Сообщение
#11
|
- Группа: Пользователи Сообщений: 480 Пол: Мужской Репутация: 4 |
Не. Когда мы нашли, что тройка подходит - надо к двойке переходить и раскладывать её, а тройку больше не трогать
-------------------- бб
|
FreeMan |
1.12.2005 10:17
Сообщение
#12
|
- Группа: Пользователи Сообщений: 480 Пол: Мужской Репутация: 4 |
Вот решение.
Volvo, извини, что так изуродовал твою процедуру Прикрепленные файлы AAA.PAS ( 1.03 килобайт ) Кол-во скачиваний: 201 -------------------- бб
|
volvo |
1.12.2005 10:22
Сообщение
#13
|
Гость |
FreeMan,
я, например, жду ответа на свой вопрос (что считать правильным решением), прежде чем что-то выкладывать... По-моему, автор сам не знает, что хочет, а "принеси то, не знаю что" я не умею... |
c-ch |
14.03.2009 20:50
Сообщение
#14
|
Новичок Группа: Пользователи Сообщений: 13 Пол: Мужской Репутация: 1 |
прошу прощения за поднимание явно древней темы
уточняю условие задачи: Дано N целых чисел A1, A2, ..., AN. Требуется найти количество различных значений сумм вида k1A1 + k2A2 + ... + kNAN. Входные данные Входной файл INPUT.TXT в первой строке содержит число N, во второй - A1, A2, ..., AN через пробел. Ограничения: все числа целые, 1 <= N <= 500, 0 <= Ai <=100, 0 <= ki <= 1. Выходные данные В выходной файл OUTPUT.TXT выведите количество различных значений сумм. т.е., для приведённого примера с числами 1, 1, 2 правильный ответ будет 5, т.к. суммы будут следующие: 0, 1, 2, 3, 4 (все к=0, к1=1 остальные=0, к3=1 остальные=0, 1+2, 1+1+2) я написал программку, решающую эту задачу, что называется, "в лоб" program qq; проблема в том, что этот алгоритм очень трудоёмок и при N=500 вычисления, мягко говоря, затягиваются у меня же одним из условий является ограничение по времени и памяти - 1 сек и 16 Мб соответственно прошу помощи у корифеев алгоритмизации хотелось бы получить рабочий исходник, т.к. времени мало осталось, но буду рад и ценным указаниям (желательно с примерами) спасибо |
Lapp |
15.03.2009 11:51
Сообщение
#15
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
проблема в том, что этот алгоритм очень трудоёмок и при N=500 вычисления, мягко говоря, затягиваются Этих ресурсов тут во много раз больше, чем достаточно (для тех пределов, которые в условии). Вот эта программка обходится примерно 50 КБ и 0.05 сек на моем ноуте (Turion 1.8 GHz) .у меня же одним из условий является ограничение по времени и памяти - 1 сек и 16 Мб соответственно const -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
c-ch |
15.03.2009 14:02
Сообщение
#16
|
Новичок Группа: Пользователи Сообщений: 13 Пол: Мужской Репутация: 1 |
Lapp
всё гениальное просто, спасибо огромное PS всем, кто будет копипастить прогу Lapp - будьте внимательны ;) |
Lapp |
16.03.2009 3:19
Сообщение
#17
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
PS всем, кто будет копипастить прогу Lapp - будьте внимательны Таинственное замечание )). Написал бы прямым текстом, что я забыл инициализировать массив s нулями. Каюсь, FP расслабляет.. Извиняюсь. Ниже исправленный вариант. Также пофиксена неточность в комментарии и добавлена некоторая рацуха, которая может еще сократить время (а может и увеличить))). const -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
c-ch |
16.03.2009 7:25
Сообщение
#18
|
Новичок Группа: Пользователи Сообщений: 13 Пол: Мужской Репутация: 1 |
нет-нет, никаких претензий, тем более, что Паскаль сам инициализацию вроде делает
намёк был на то, что в задании числа расположены в одной строке, а у тебя считывание идёт, как если бы они в столбик записаны были к тому же, я решил, что ошибка сделана намеренно, в образовательных целях))) типа что бы уж не совсем халява была |
Lapp |
16.03.2009 11:37
Сообщение
#19
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Паскаль сам инициализацию вроде делает Как-то у меня странно получилось: при повторном запуске массив s не обнулялся (в ВР). Я уже так давно не работаю с ТР/ВР, что не могу объяснить этот феномен. Волво?.. намёк был на то, что в задании числа расположены в одной строке, а у тебя считывание идёт, как если бы они в столбик записаны были Нет, просто невнимательность моя. При беглом просмотре твоей проги я не ощутил особой необходимости в подобных мерах . А "в образовательных целях" я обычно просто недописываю.к тому же, я решил, что ошибка сделана намеренно, в образовательных целях))) типа что бы уж не совсем халява была -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
volvo |
16.03.2009 13:35
Сообщение
#20
|
Гость |
Цитата Как-то у меня странно получилось: при повторном запуске массив s не обнулялся Угу... Так и должно быть. Турбо/Борланд Паскаль вообще ничего не инициализирует и не обнуляет, ни при первом запуске, ни при последующих. Просто при старте IDE память очищается, а при рестарте программы - нет. Каким было содержимое той области памяти, где компилятор расположил переменную - таким и остается. Как результат - непредсказуемое поведение программы (если переменные не инициализируются в коде самой программы).В более продвинутых компиляторах с этим чуть лучше, но все-таки лучше взять инициализацию глобальных переменных на себя, а не полагаться на компилятор. |
Текстовая версия | 27.04.2024 18:43 |