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 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гуру
*****

Группа: Пользователи
Сообщений: 1 013
Пол: Мужской
Ада: Разработчик
Embarcadero Delphi: Разработчик
Free Pascal: Разработчик

Репутация: -  627  +


При n > 22 тормозит? Что с тобой, Андрей? Вот это за полторы секунды печатает все результаты от 3 до 39 включительно smile.gif Метод - прост, рекурсия с мемоизацией:
{$mode objfpc}
uses crt;

const
R = 780; // Больше 780 N никогда не будет при таких исходных данных
C = 100; // Это даже с запасом, для I
var
T : array[0 .. R, 0 .. C] of int64;

function f(n, i : dword) : dword;
var m : dword;
begin
if T[n, i] <> -1 then result := T[n, i] // Уже вычислялось? Вернуть сразу
else
begin

m := i * succ(i) div 2;
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));

T[n, i] := result; // иначе вычислить и запомнить
end;
end;

var
i, j : integer;
const
n = 39;

begin
for i := 0 to R do
for j := 0 to C do
T[i, j] := -1;

if pred(n) mod 4 < 2 then writeln(0)
else writeln(f(n, pred(n)));

end.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Да уж, Андрей уже не торт smile.gif Спасибо за быстрый ответ, буду вкуривать в ход твоих мыслей)

Добавлено через 10 мин.
А у этого алогоритма есть какое-то название или чисто импровизация ?


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


Гуру
*****

Группа: Пользователи
Сообщений: 1 013
Пол: Мужской
Ада: Разработчик
Embarcadero Delphi: Разработчик
Free Pascal: Разработчик

Репутация: -  627  +


Названия нет, но сам алгоритм подсчета предложил профессор Хайнц из какого-то немецкого университета, я только запрограммировал его на Паскале smile.gif Задача-то известная...

Были еще предложения решать эту задачу через треугольные числа, но я не думаю, что решение будет проще.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


А почему 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, так нафига тут-то так делать?

Я бы написал как-то так:

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));



Сообщение отредактировано: TarasBer -


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


IUnknown, что-то не могу пока понять каким образом свою роль в алгоритме выполняет переменная m.
TarasBer, ну это придирки ради придирки помоему. Особенно в разделе алгоритмы очень в тему.

Сообщение отредактировано: klem4 -


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


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Цитата(klem4 @ 7.10.2012 20:05) *

IUnknown, что-то не могу пока понять каким образом свою роль в алгоритме выполняет переменная m

m - это сумма чисел от 1 до i. Если бы он написал i*(i+1) div 2, то было бы меньше вопросов, чем с succ

Сообщение отредактировано: TarasBer -


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Ну да, арифм. прогрессия) Окей smile.gif


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

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

 




- Текстовая версия 24.05.2018 7:03
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"