IPB
ЛогинПароль:

> Количество разложений числа на различные слагаемые
сообщение
Сообщение #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 оно сильно тормозит, ибо количество итераций в рекурсии сильно растет.

Буду признателен за наставление на путь истенный, несложная вроде задача, хочется научиться ее решать smile.gif
Код на python, не обессудьте smile.gif Паскаль уже напроч забыл ...

Кода кот наплакал, если нужны пояснения, добавлю.
Спойлер (Показать/Скрыть)


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 10.12.2019 17:24
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name