Вот уже второй день ломаю голову над одной "типичной программерской" задачей. Суть её заключается в том, что надо сгенирировать всевозможные числовые последовательности, сумма всех членов которых должна равняться определенному числу. Я решил эту задачу с помощью тупого перебора всевозможных последовательностей, но при больших числах время выполнения оставляет желать лучшего. Какое бы вы предложили решение?
Скажем, дана последовательность от 1 до A, пользуясь которой нужно генерировать последовательности, представляющие сумму числа N.
Ответ
Рекомендую почитать учебники по теории чисел. Это называется композиции и разбиения в зависимости от того считать ли 5=1+1+2+1+1 или 5=2+1+1+1+1 одним и тем же или нет. В Википедии более менее доходчиво изложено. Вот скажем пример алгоритма на Java: http://www.btinternet.com/~se16/js/PartitionChoice.java Два примера на C++: http://www.cyberforum.ru/cpp-beginners/thread342773.html http://www.cyberforum.ru/cpp-beginners/thread372700.html Вот еще хорошая бумага: http://www.tusur.ru/filearchive/reports-magazine/2008-1/113-119.pdf Ну и конечно классика: TAOCP том 4 7.2.1.3. Generating all combinations 7.2.1.4. Generating all partitions
Комментариев нет:
Отправить комментарий