Количество разложений числа на различные слагаемые |
Количество разложений числа на различные слагаемые |
klem4 |
6.10.2012 21:03
Сообщение
#1
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Hi all!
Имею проблему с решением задачи, то есть решение есть, но за непримемлемое время(необходимо уложиться в 1с). И так, имеем последовательность числел от 1 до N (1<=N<=39). Например при N = 4 это будет последовательность {1,2,3,4} Необходимо: найти количество разбиений данного множества на две части(непустые), такие что сумма их элементов одинакова. То есть при n = 3, ответ будет 1, так как {1,2,3} == {3} и {2,1} при n = 7, ответ будет 4, так как {1,2,3,4,5,6,7} == {1, 6, 7} и {2, 3, 4, 5} {2, 5, 7} и {1, 3, 4, 6} {3, 4, 7} и {1, 2, 5, 6} {1, 2, 4, 7} и {3, 5, 6} Очевидно, если сумма всех элементов множества нечетная, то ответ - 0, так как сумма его элементов не делится на 2 и соответственно не может быть разделена на 2 равные части. Где-то полчаса потратил на поиск по форуму, похожие задачки были, но все не совсем то что надо. Я пока родил следующее решение(перебор с возвратом), но при n > 22 оно сильно тормозит, ибо количество итераций в рекурсии сильно растет. Буду признателен за наставление на путь истенный, несложная вроде задача, хочется научиться ее решать Код на python, не обессудьте Паскаль уже напроч забыл ... Кода кот наплакал, если нужны пояснения, добавлю. Спойлер (Показать/Скрыть)
-------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Текстовая версия | 28.04.2024 19:06 |