Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
Форум программистов > Алгоритмы > Найти количество разложений числа |
Автор: GoldMan 10.12.2002, 03:39 |
Найти количество разложений числа на простые слагаемые, например, для 11 ответ 6, т.к. 11=2+2+2+2+3;11=2+3+3+3;11=2+2+2+5;11=3+3+5;11=7+2+2;11=11. Заранее спасибо. |
Автор: Step 10.12.2002, 04:03 | ||
Впоследнее время я слишком часто слушы такии вопросы, товарищи это вы на какой алимпиаде побывали. Кстати тупым перебором не пробывали.... ну и что, что долго... |
Автор: podval 10.12.2002, 04:43 |
На некоторых олимпиадах именно такие задачи. Решение состоит в том, чтобы написать алгоритм решения такой задачи. А если это число 11-значное? Какой тут тогда перебор? Итак, задача - написать алгоритм. |
Автор: GoldMan 10.12.2002, 16:29 |
Ограничения: число в пределах от 1 до 5000; 15 секунд на тест Перебор успевает за 15 секунд число, не большее 120 ![]() |
Автор: MuToGeN 10.12.2002, 16:35 | ||
что значит 15 секунд? 15 секунд на 486DX2 или на AthlonXP 2.5GHz? |
Автор: MuToGeN 10.12.2002, 16:38 |
хотя есть у меня смутная догадка как это сделать... скоро че-нить нарисую... |
Автор: podval 11.12.2002, 05:45 |
А почему среди слагаемых нет числа 1? Тогда 11 не шестью способами можно получить. |
Автор: Cashey 11.12.2002, 08:34 | ||
Число 1 не является простым. |
Автор: podval 11.12.2002, 18:01 |
В таком случае наша задача отличается от http://algolist.manual.ru/olimp/per_sol.php#a8 тем, что надо предварительно найти и записать массив простых чисел, меньших заданного, и работать только с этим массивом. |
Автор: GoldMan 11.12.2002, 19:18 |
2 MutoGen: комп 486DX, поэтому перебор для n=5000 не успевает. |
Автор: MuToGeN 11.12.2002, 19:58 | ||||
|
Автор: Chingachguk 15.12.2002, 13:08 | ||
Вот, вроде сделал. Адская рекурсия и прочий изврат ;) Для полного решения надо выделить еще кучу памяти, что меня делать заломало, поэтому я посчитал (на P-120) тока до 300-т ;) (Именно от количества памяти зависит комфортное быстродействие)
|
Автор: MuToGeN 15.12.2002, 13:19 |
кстати если известно, что число будет не больше 5000, то вроде как божно просчитать (с помощью другой программы) все простые числа до 5000 и вставить их в программу как константу, чтобы не просчитывать заново. |
Автор: Chingachguk 15.12.2002, 17:10 | ||
Проверка ЛЮБОГО числа на простоту тут по времени <<< времени подсчета числа сумм. Хотя я и этим не побрезговал ;) |
Автор: BlowFish 17.12.2002, 18:03 |
To Chingachguk: так сколько по времени у тебя прога считает? например числа 200, 300..? Ты укладываешься в 15 сек? |
Автор: Chingachguk 17.12.2002, 18:16 | ||
Моя прога на turbo pascal 7.0, компьютер был P-120. Числа до 300 считает примерно ~5-6 секунд легко. Если выделять больше памяти на хранение количеств разложения чисел на суммs только через простые числа, не большие 23, 29, 31 ... и т.д., то можно добиться и большего. Просто требуется выделение памяти. (Смотри мои массивы: P3:array[0..MaxValidNumber] of longint; P5:array[0..MaxValidNumber] of longint; ... P23:array[0..MaxValidNumber] of longint и их заполнение в процедуре Sum_NumberBest) |
Автор: Alex101 5.1.2003, 04:14 |
Когда проверяете, является ли число простым, то надо в качестве делителей числа N перебирать до sqrt(N) - уже на этом время сэкономите. 2 ChinqachqukИнтересный у тебя алгоритм, но слишком громоздкий. |
Автор: Alex101 5.1.2003, 04:47 |
Интересная задачка! Сейчас что-то влом вызовы отлавливать, завтра-послезавтра точно решу. |
Автор: Chingachguk 8.1.2003, 18:16 | ||
Время определения простоты числа тут некритично. Я довольствовался сравнением: делиться на 2 ? на 4 ? (битовые операции) - даже про 8 не стал писать. Хотя с корнем интересно, я не знал этого. Алгоритм не громоздкий, он просто очень тупо написан (массивы PNN[] нужно было слить в один и сделать цикл по уже двумерному массиву) - чего громоздкого, это всего лишь одна рекурсивная процедура - первая процедура (Sum_Number) вообще приведена для примера, ее можно замочить ;) |
Автор: maxim1000 11.1.2003, 02:25 | ||
по-моему, решение олимпиадной задачи не должно быть длинным... не обращайте внимания на процедуру определения простоты числа (мне просто лень писать что-то сложнее, а идея алгоритма состоит не в этом)
|
Автор: Chingachguk 14.1.2003, 01:01 |
Гм. Что-то я не вижу отличия от моего решения ;) Все та же рекурсия - но только без оптимизации. Так, например, если заменить integer->longint, то она почти мгновенно считает writeln(quantity(100,2));, но вот с writeln(quantity(200,2)); конкретно замирает - и это на P800 ! У меня считало нормально на P120 до 300 ж) |
Автор: maxim1000 14.1.2003, 01:27 |
Прошу прощения, не разобрался в этом коде и сразу начал писать свой... Просто мне хотелось сделать сам алгоритм понятным (по-моему, так и должно быть на олимпиадах). |
Автор: Chingachguk 14.1.2003, 02:07 |
Да фигня ;) интересно, что у тебя выйдет, если ты попробуешь для серьезных чисел посчитать Ж) |
Автор: Chingachguk 15.1.2003, 00:02 | ||
Вот, написал на Паскале для дос то же самое, но более аккуратно, с выделением памяти. Позволяет секунд за 5 на P800 сосчитать для чисел около 1000. Дальше надо либо с расширенной памятью (dpmi и тд) возиться, либо с диском ;) Примечание: из-под среды не пойдет (не хватит памяти), надо пускать экзе.
|
Автор: Kuvaldis 9.9.2006, 21:52 | ||
Нашел еще красивое решение (используется динамическое программирование)
|
Автор: Executer 10.9.2006, 02:24 | ||
Это стандартная задача на динамическое программирование. Вот общий агоритм: 1. Найдем все простые числа. 2. Затем начнем строить все разложения. Посмотрим на простом примере 2 = 2 3 = 3 4 = 2 + 2 5 = 2 + 3 6 = 2 + 2 + 2 6 = 3 + 3 Как можно подсчитать количество разложений числа 6? А вот как - посмотрим количество разложений числа 6 - 2 и числа 6 - 3, и сложим их. От сюда выстраивается дп алгоритм. Перебираем все числа от 0 до N, и во вложенном цикле ищем количество разложений для данного числа, заканчивающегося данным простым числом. А вот программа на java: (Кстати количество разбиений будет очень велико, поэтому надо брать последнии цифры числа, для числа 5000 программа работает меньше секунды на P4 3.0 Ghz)
|
Автор: IvanoffAndrey 12.9.2006, 16:03 |
Я бы пробовал искать формулу. GoldMan, Попробуйте найти функцию f(x), x=есть разлогаемое число, а f - возвращает количесто разложений. Обычно на аллимпиадах местного масштаба редко загибают сложно - переборные задачи (часто ставят ограничение по времени - и перебор не проходит), поэтому наверняка есть иное решение. Наверняка эт формула будет связана с арифметическим треугольником. Щас посижу, попробую, если получится у меня сообщу. |
Автор: nostromo 13.9.2006, 08:23 |
To IvanoffAndrey: мне кажется Вы слишком упрощаете ситуацию и нерекурсивное алгебраического выражения для этой функции найти очень сложно. Кстати, известный метод треугольника Паскаля можно рассматривать как частный случай метода динамического программирования. To Kuvaldis, Executer: Ваш метод мне в общем понятен, однако в правильности реалзации не уверен. Если не сложно, приведите пожалуйста значения, которые выдают ваши программы, скажем, для чисел 7, 20 и 1000. Добавлено @ 08:28 Да, Executer, как Ваша программа могла посчитать ответ для 5000, если уже ответ для 1400 не влазит в 8-байтное целое, а длинную арифметику Вы, судя по коду, не используете? |
Автор: Kuvaldis 13.9.2006, 10:34 | ||
Код на Pascal - с сайта http://contest.ur.ru/. Думаю, что там правильно. Вот лично мой вариант (программа все тесты на моей универской олимпиаде прошла)
Я тесты прикрепляю (правда, у нас было ограничение для входящего числа <= 330, но все же) |
Автор: nostromo 13.9.2006, 12:25 | ||
То Kuvaldis: посмотрел результаты --- похоже правильные (с моими, по крайней мере, совпадают). Привожу до кучи и свою реализацию на языке Smalltalk (VisualWorks). Суть алгоритма в следующем. Пусть есть число X и простое число P. Ставится задача нахождения всех вариантов представления X в виде суммы простых слагаемых, каждое из которых не превосходит P. Эта задача рекурсивно сводится к себе с меньшими параметрами: func(X,P) = func(X-P, P) + func(X, предыдущий(P)) (псевдокод) Идея подобна приводившимся ранее, однако данная ее реализация имеет свои преимущества (прежде всего, простота). Комментарии к реализации. Чтобы избежать повторных вычислений в рекурсивных вызовах, найденные значения сохраняются в словаре memoDict. Работа с простыми числами идет по индексам из предварительно составленного списка простых чисел.
Счет можно запускать так: N := 4000. index := (Integer primesUpTo: N) size. res := worker func: N lastIndex: index. Вот избранные ответы: 7: 3 20: 26 1000: 48278613741845757 4000: 1629425615961660388014828752394491 В последнем случае счет занял около 6 минут на P4 (для динамически типизированного языка с учетом длинной арифметики я считаю --- нормально) и словарь memoDict содержал 650641 элементов --- кажется, это меньше, чем требуется приведенным здесь реализациям метода динамического программирования для такого входного аргумента. Добавлено @ 12:32 Забыл, перед запуском расчета, конечно, нужно создать экземпляр класса: worker := Solver new. |