![]() |
![]() ![]() |
![]() |
klem4 |
![]()
Сообщение
#1
|
![]() Perl. Just code it! ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: ![]() ![]() ![]() |
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";'
|
IUnknown |
![]()
Сообщение
#2
|
![]() a.k.a. volvo877 ![]() ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: ![]() ![]() ![]() |
При n > 22 тормозит? Что с тобой, Андрей? Вот это за полторы секунды печатает все результаты от 3 до 39 включительно
![]() {$mode objfpc} |
klem4 |
![]()
Сообщение
#3
|
![]() Perl. Just code it! ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: ![]() ![]() ![]() |
Да уж, Андрей уже не торт
![]() Добавлено через 10 мин. А у этого алогоритма есть какое-то название или чисто импровизация ? -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
IUnknown |
![]()
Сообщение
#4
|
![]() a.k.a. volvo877 ![]() ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: ![]() ![]() ![]() |
Названия нет, но сам алгоритм подсчета предложил профессор Хайнц из какого-то немецкого университета, я только запрограммировал его на Паскале
![]() Были еще предложения решать эту задачу через треугольные числа, но я не думаю, что решение будет проще. |
TarasBer |
![]()
Сообщение
#5
|
![]() Злостный любитель ![]() ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: ![]() ![]() ![]() |
А почему succ и pred, если +1 и -1 (или наоборот? не могу запомнить никак) понятнее?
> if n > m then result := 0 > else > if n = m then result := 1 > else result := f(abs(n - i), pred(i)) + f(n+i, pred(i)); Лишний перенос и отступ не нужны, потому что на самом деле все три ветки тут равноправные. Создатели языков даже специально борются с переносом между else и if, вводя оператор elseif, так нафига тут-то так делать? Я бы написал как-то так:
Сообщение отредактировано: TarasBer - 7.10.2012 16:02 -------------------- |
klem4 |
![]()
Сообщение
#6
|
![]() Perl. Just code it! ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: ![]() ![]() ![]() |
IUnknown, что-то не могу пока понять каким образом свою роль в алгоритме выполняет переменная m.
TarasBer, ну это придирки ради придирки помоему. Особенно в разделе алгоритмы очень в тему. Сообщение отредактировано: klem4 - 7.10.2012 20:05 -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
TarasBer |
![]()
Сообщение
#7
|
![]() Злостный любитель ![]() ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: ![]() ![]() ![]() |
IUnknown, что-то не могу пока понять каким образом свою роль в алгоритме выполняет переменная m m - это сумма чисел от 1 до i. Если бы он написал i*(i+1) div 2, то было бы меньше вопросов, чем с succ Сообщение отредактировано: TarasBer - 7.10.2012 20:37 -------------------- |
klem4 |
![]()
Сообщение
#8
|
![]() Perl. Just code it! ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: ![]() ![]() ![]() |
Ну да, арифм. прогрессия) Окей
![]() -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
![]() ![]() |
![]() |
Текстовая версия | 7.09.2024 12:53 |