Количество разложений числа на различные слагаемые Опции

[klem4]

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

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

Спойлер (Показать/Скрыть)

Код

#!/usr/bin/python


import sys
COUNT = 0


def sequence_sum(first, last):
    return int((first + last) / 2.0 * (last - first + 1))


def element_ok(curr_sum, need_sum, element):
    return curr_sum + element <= need_sum


def sequence_ok(from_element, curr_sum, need_sum):
    seq_sum = sequence_sum(1, from_element)
    return curr_sum + seq_sum >= need_sum


def solution(curr_el, curr_sum, need_sum, size):
    if curr_sum == need_sum:
        globals()['COUNT'] += 1
    else:
        digit = curr_el - 1
        while digit:
            if not sequence_ok(digit, curr_sum, need_sum):
                break
            else:
                if element_ok(curr_sum, need_sum, digit):
                    solution(digit, curr_sum + digit, need_sum, size)
            digit -= 1


if __name__ == '__main__':

    seq_size = int(sys.argv[1] if len(sys.argv) > 1 else 3)
    full_sum = sequence_sum(1, seq_size)
    half_sum = int(full_sum / 2.0)

    if not full_sum % 2:
        solution(seq_size, seq_size, half_sum, seq_size)

    print COUNT

[IUnknown]

При 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]

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

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

[IUnknown]

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

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

[TarasBer]

А почему 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 - 7.10.2012 16:02

[klem4]

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

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

[TarasBer]

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

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

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

[klem4]

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