Pomoc oko zadatka

[ Byk @ 11.04.2005. 11:27 ] @

Znaci zadatak glasi:
Za unijeti broj n kao rezultat program treba da stampa u k redova sve moguce kombinacije sabiraka ciji je zbir taj (unijeti) broj. Npr: Za unijeti broj 4 to bi bilo:
1+3
3+1
2+2
2+1+1
1+1+2
1+1+1+1
-otprilike znam kako bih za 2 sabirka ali za 3,4 ili vise nemam ideju...

[ bancika @ 11.04.2005. 13:16 ] @

pogledaj na sajtu http://www.theory.csc.uvic.ca/~cos/ imas algoritme za generisanje kombinatornih objekata, konkretno ti trebaju particije prirodnih brojeva, da znas sta da trazis :)

[ Toyo @ 11.04.2005. 14:11 ] @

Evo ga. Ova procedura pisiniz bi mogla da ima samo 3 reda kada ne bi sve ispisane nizove pamtila, i pri svakom sledecem pozivu proveravala da li je vec isti ispisan na ekran.

Code:

const
  MaxN=100;
type
  niz = array[1..MaxN] of integer;
var
  a: niz;
  pam:array[1..200] of niz;
  poz,i,n:integer;

procedure pisiniz(nz: niz;n:integer);
var
   i,j: integer;
   forma:niz;
   nadjen, isti:boolean;
begin
     for i := n+1 to maxn do
         forma[i]:=0;
     for i := 1 to n do
         forma[i]:=nz[i];
     nadjen := false;
     for i := 1 to poz do
         begin
              isti := true;
              for j := 1 to maxn do
                  isti:=isti and (pam[i,j]=forma[j]);
              nadjen := nadjen or isti;
         end;
     if not nadjen then
        begin
             inc(poz);
             for i := 1 to maxn do
                 pam[poz,i]:=forma[i];
             for i :=1 to n do
                 write(nz[i]);
             writeln;
        end;
end;

procedure razvoj(a: niz; duz:integer);
var
   pa:niz;
   i,j:integer;
begin
     for i:= 1 to duz - 1 do
         begin
              for j := 1 to i-1 do
                  pa[j]:= a[j];
              pa[i]:=a[i]+a[i+1];
              for j:= i+2 to duz do
                  pa[j-1]:=a[j];
              pisiniz(pa, duz-1);
              if (duz > 3) and ((i mod 2)=1) then
                 razvoj(pa,duz-1);
         end;
end;

begin
     write('Unesi n = ');
     readln(n);
     for i := 1 to n do
         a[i]:= 1;
     pisiniz(a,n);
     razvoj(a, n);
     poz:=0;
     readln;
end.

[ --SOULMaTe-- @ 11.04.2005. 15:33 ] @

Cek, jel ti mislis na particije broja?

Da li ti je 2 + 1 + 1 razlicito od 1 + 1 + 2 ?

[ Byk @ 12.04.2005. 13:11 ] @

Soulmate je primijetio znaci moja greska u postavci zadatka. Ne radi se kombinacijama sa ponavljanjem vec bez ponavljanja. Znaci program treba da stampa umjesto (za br. 4 na primjer): 2+1+1 i 1+1+2 samo 2+1+1+ ili samo 1+1+2 zavisi kako ko krene da rjesava zadatak. Sinoc sam ipak uspio da napisem program tako sto sam poceo od 1+1+1+1 resenja a onda povecavao za 1 poslednji najmanji i smanjivao zadnji najveci broj pa je sledece rjesenje: 2+1+1+0, zatim: 2+2+0+0 i na kraju: 3+1+0+0. Jedino nisam siguran da li su ove nule greska. Sad ne znam da li je Toyov program na ovom principu jer nemam vremena da ga tumacim (pogledacu ga kuci jer sam sad na fax) ali u svakom slucaju hvala na pomoci.

[ --SOULMaTe-- @ 12.04.2005. 14:36 ] @

E onda su particije broja ono sto te bi treba. To je klasicni primer backtracka.
Ovako bi trebao da izgleda kod.

Code:

var
  p:array[1..max] of integer;
  i:integer;

procedure ispisi(pos:integer);
var
  i:integer;
begin
  write(p[1]);
  for i:=2 to pos do write('+',p[i]);
  writeln;
end;

procedure part(pos,n:integer)
var
  i:integer;
begin
  if n = 0 then Ispisi(pos)
  else
  begin
    for i:=p[pos] to n do
    begin
      p[pos+1]:=i;
      part(pos+1,n-i);
    end;
  end;
end;

begin
  for i:=1 to broj do
  begin
    p[1]:=i;
    part(1,broj-i);
  end;
  readln;
end.

[ Toyo @ 12.04.2005. 18:39 ] @

Citat:

Znaci program treba da stampa umjesto (za br. 4 na primjer): 2+1+1 i 1+1+2 samo 2+1+1+ ili samo 1+1+2

Hmm. Pa sam si napisao u 1. posti da treba i 112 i 211. a ja se mucio 3 minuta, prvo da napravim sve moguce varijacije, pa zarim "skresem" nepotrebno ponavljanje.

[ bancika @ 12.04.2005. 18:56 ] @

to je neefikasno..od n! ti treba relativno malo njih

[ Toyo @ 12.04.2005. 19:06 ] @

Pa da ali je covek tako napisao u 1. postu