Разложение на слагаемые Опции

[Unconnected]

Привет всем.

Точно помню, что такое было на форуме, но поиск по всяким сочетаниям ничего не дал( Нужно вывести все возможные разложения числа N на слагаемые, без повторений (3+2 и 2+3 - повтор). Я сделал рекурсией разложение на слагаемые, но с повторениями. Как их избежать, ума не приложу.

{$APPTYPE CONSOLE}

var n:byte;
    m:array[1..40] of byte;

Procedure rec(k,l:integer);
var i:integer;
begin
  if (k=n) and (l>1) then begin
    for i:=1 to l-1 do write(m[i],'+');
    writeln(m[l]);
  end else begin
    for i:=1 to n do begin
      if k+i<=n then begin
        m[l+1]:=i;
        rec(k+i,l+1);
      end else break;
    end;
  end;
end;

begin
  fillchar(m,40*sizeof(byte),0);
  assign(input,'input.txt');
  read(n);
  assign(output,'output.txt');
  rec(0,0);
end.

N<=40, на 40 этот код оччень долго работает, я не дождался. Наверное, надо отсекать повторы ещё при разложении.

Сообщение отредактировано: Unconnected - 5.08.2010 1:38

[sheka]

По моему, очень легко. Сейчас разбираться не могу - спать охота
Надо раскладывать так, чтобы следующие были меньше предыдущего.
Т. е., например, так:
передаешь процедуре само число. допустим 5.
пусть процедура его раскладывает на 4 и 1.
потом переходишь к меньшему, к единице. она не раскладывается - возврат.
3 2
опять переходишь к меньшему и раскладываешь его. получается 3 | 1 | 1.
опять к меньшему. оно равно 1, поэтому возврат, возврат.
вернулись к 3ке.
2 | 2 | 1
2 | 1 | 1 | 1
1 | 1 | 1 | 1 | 1
Если не сделаешь - завтра попробую

Сообщение отредактировано: sheka - 5.08.2010 1:40

[volvo]

но поиск по всяким сочетаниям ничего не дал

"+разложе* +слагаем*" = чудо!!! -> Разложение числа

[Unconnected]

sheka, как я понял, с твоим способом всё равно повторы будут..

Блин, я так же искал, по этому сочетанию и со звёздочками, но без плюсов)