Найти количество разложений числа на простые слагаемые, например, для 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.

Заранее спасибо.

Цитата(GoldMan @ 09.12.2002, 19: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. Заранее спасибо.

Впоследнее время я слишком часто слушы такии вопросы, товарищи это вы на какой алимпиаде побывали.

Кстати тупым перебором не пробывали.... ну и что, что долго...

На некоторых олимпиадах именно такие задачи. Решение состоит в том, чтобы написать алгоритм решения такой задачи. А если это число 11-значное? Какой тут тогда перебор?
Итак, задача - написать алгоритм.

Ограничения:
число в пределах от 1 до 5000;
15 секунд на тест
Перебор успевает за 15 секунд число, не большее 120 ((

Цитата(GoldMan @ 10.12.2002, 08:29)

Ограничения: число в пределах от 1 до 5000; 15 секунд на тест Перебор успевает за 15 секунд число, не большее 120 ((

что значит 15 секунд? 15 секунд на 486DX2 или на AthlonXP 2.5GHz?

хотя есть у меня смутная догадка как это сделать... скоро че-нить нарисую...

А почему среди слагаемых нет числа 1? Тогда 11 не шестью способами можно получить.

Цитата

А почему среди слагаемых нет числа 1?

Число 1 не является простым.

В таком случае наша задача отличается от http://algolist.manual.ru/olimp/per_sol.php#a8 тем, что надо предварительно найти и записать массив простых чисел, меньших заданного, и работать только с этим массивом.

2 MutoGen: комп 486DX, поэтому перебор для n=5000 не успевает.

такой вариант, правда, он не самый лучший:
в массиве c имеем простые числа от 0 до 5000, кол-во простых чисел равно k. все что после k - неинициализированные элементы массива

Вот, вроде сделал. Адская рекурсия и прочий изврат ;)

Для полного решения надо выделить еще кучу памяти, что меня делать заломало, поэтому я посчитал (на P-120) тока до 300-т ;)

(Именно от количества памяти зависит комфортное быстродействие)

кстати если известно, что число будет не больше 5000, то вроде как божно просчитать (с помощью другой программы) все простые числа до 5000 и вставить их в программу как константу, чтобы не просчитывать заново.

Цитата

MuToGeN Дата сообщения: 15.12.2002,05:19 кстати если известно, что число будет не больше 5000, то вроде как божно просчитать (с помощью другой программы) все простые числа до 5000 и вставить их в программу как константу, чтобы не просчитывать заново.

Проверка ЛЮБОГО числа на простоту тут по времени <<< времени подсчета числа сумм. Хотя я и этим не побрезговал ;)

To Chingachguk: так сколько по времени у тебя прога считает? например числа 200, 300..? Ты укладываешься в 15 сек?

Цитата

BlowFish Дата сообщения: 17.12.2002,103 To Chingachguk: так сколько по времени у тебя прога считает? например числа 200, 300..? Ты укладываешься в 15 сек?

Моя прога на 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)

Когда проверяете, является ли число простым, то надо в качестве делителей числа N перебирать до sqrt(N) - уже на этом время сэкономите.
2 ChinqachqukИнтересный у тебя алгоритм, но слишком громоздкий.

Интересная задачка!
Сейчас что-то влом вызовы отлавливать, завтра-послезавтра точно решу.

Цитата

Alex101 Дата сообщения: 04.1.2003,20:14 Когда проверяете, является ли число простым, то надо в качестве делителей числа N перебирать до sqrt(N) - уже на этом время сэкономите. 2 ChinqachqukИнтересный у тебя алгоритм, но слишком громоздкий.

Время определения простоты числа тут некритично. Я довольствовался сравнением: делиться на 2 ? на 4 ? (битовые операции) - даже про 8 не стал писать. Хотя с корнем интересно, я не знал этого. Алгоритм не громоздкий, он просто очень тупо написан (массивы PNN[] нужно было слить в один и сделать цикл по уже двумерному массиву) - чего громоздкого, это всего лишь одна рекурсивная процедура - первая процедура (Sum_Number) вообще приведена для примера, ее можно замочить ;)

по-моему, решение олимпиадной задачи не должно быть длинным...
не обращайте внимания на процедуру определения простоты числа (мне просто лень писать что-то сложнее, а идея алгоритма состоит не в этом)



Это сообщение отредактировал(а) maxim1000 - 9.9.2006, 22:16

Гм. Что-то я не вижу отличия от моего решения ;)

Все та же рекурсия - но только без оптимизации. Так, например, если заменить integer->longint, то она почти мгновенно считает writeln(quantity(100,2));, но вот с writeln(quantity(200,2)); конкретно замирает - и это на P800 ! У меня считало нормально на P120 до 300 ж)

Прошу прощения, не разобрался в этом коде и сразу начал писать свой...
Просто мне хотелось сделать сам алгоритм понятным (по-моему, так и должно быть на олимпиадах).

Да фигня ;) интересно, что у тебя выйдет, если ты попробуешь для серьезных чисел посчитать Ж)

Вот, написал на Паскале для дос то же самое, но более аккуратно, с выделением памяти. Позволяет секунд за 5 на P800 сосчитать для чисел около 1000. Дальше надо либо с расширенной памятью (dpmi и тд) возиться, либо с диском ;)

Примечание: из-под среды не пойдет (не хватит памяти), надо пускать экзе.

Нашел еще красивое решение (используется динамическое программирование)

Это стандартная задача на динамическое программирование.
Вот общий агоритм:
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)

Я бы пробовал искать формулу.
GoldMan, Попробуйте найти функцию f(x), x=есть разлогаемое число, а f - возвращает количесто разложений. Обычно на аллимпиадах местного масштаба редко загибают сложно - переборные задачи (часто ставят ограничение по времени - и перебор не проходит), поэтому наверняка есть иное решение.
 Наверняка эт формула будет связана с арифметическим треугольником.
Щас посижу, попробую, если получится у меня сообщу.

To IvanoffAndrey: мне кажется Вы слишком упрощаете ситуацию и нерекурсивное алгебраического выражения для этой функции найти очень сложно. Кстати, известный метод треугольника Паскаля можно рассматривать как частный случай метода динамического программирования.


To Kuvaldis, Executer:
Ваш метод мне в общем понятен, однако в правильности реалзации не уверен. Если не сложно, приведите пожалуйста значения, которые выдают ваши программы, скажем, для чисел 7, 20 и 1000.

Добавлено @ 08:28 
Да, Executer, как Ваша программа могла посчитать ответ для 5000, если уже ответ для 1400 не влазит в 8-байтное целое, а длинную арифметику Вы, судя по коду, не используете?

Код на Pascal - с сайта УрГУ. Думаю, что там правильно.

Вот лично мой вариант (программа все тесты на моей универской олимпиаде прошла)


Я тесты прикрепляю (правда, у нас было ограничение для входящего числа <= 330, но все же)

Это сообщение отредактировал(а) Kuvaldis - 13.9.2006, 10:40

Присоединённый файл ( Кол-во скачиваний: 2 )
 F.zip 1,57 Kb

То 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.