Версия для печати темы

Автор: klem4 7.10.2012 1:03

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, не обессудьте Паскаль уже напроч забыл ...

Кода кот наплакал, если нужны пояснения, добавлю.

Автор: IUnknown 7.10.2012 6:14

При n > 22 тормозит? Что с тобой, Андрей? Вот это за полторы секунды печатает все результаты от 3 до 39 включительно Метод - прост, рекурсия с мемоизацией:

{$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.

Автор: klem4 7.10.2012 14:26

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

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

Автор: IUnknown 7.10.2012 17:29

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

Были еще предложения решать эту задачу через треугольные числа, но я не думаю, что решение будет проще.

Автор: TarasBer 7.10.2012 19:59

А почему 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));

Автор: klem4 8.10.2012 0:05

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

Автор: TarasBer 8.10.2012 0:37

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

Автор: klem4 8.10.2012 0:59

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