Pozdrav.
Imam jedan zadatak koji nikako ne mogu resiti.
Unesi broj n i ispisi sve mogucnosti rastavljanja tog broja na sabirke.
Npr.: n=5
1+1+1+1+1
1+1+1+2
1+1+3
1+4
1+2+2
2+3
Pokusavam napraviti odgovarajucu rekurzivnu funkciju medjutim to mi nikako ne uspeva.
Da li ima neko resenje?
Potpis
"Na svetu postoje dve stvari koje su beskonačne. To su univerzum i čovekova glupost. Ali za univerzum nisam baš siguran!"
Albert Einstein
Treba da uradim sličan zadatak,s tim da sabirci ne mogu da se ponavljaju.
Broj 8 će rastaviti kako:
7+1
6+2
5+3
5+2+1
4+3+1
Ne treba da generise sva resenja pa da štampa samo ona koja odgovaraju uslovu,nego odmah da generiše prava.
Imate li ideju kako to da uradim ?Treba li možda preko backtrackinga?
za svaki broj k manji od n, odredi sabirke n-k, resenje je
k, sabirci(n-k)
Ovaj metod je nepraktican posto ce se dosta cesto ponavljati sabirci pa bi ti trebalo
da na neki nacin pratis sta je vec bilo od resenja
na primer
za n 4
k 2
daje 2, 1 1
dok k 1
daje
1, (pa moze dati 1,1,1, 2,1, 1,2)
znaci
1,2,1
1,1,2
je isto sto i 2,1,1
sto je totalno neefikasno
drugi metod je "dinamickim" programiranjem
zamisli da za n imas ovako:
1,1,1,1,1,.....,1 (n komada)
i da postavljas u prvom koraku n-1, u drugom n-2 u trecem n-3 sibica izmedju jedinica
naprimer n =4
1|1|1|1 (to je jedini nacin da postavis n-1 odnosno 3 sibice) znaci sabirci su 1,1,1,1
pa onda imas za broj sibica n-2
1|1|1,1 = 1,1,2
1|1,1|1 = 1,2,1
1,1|1|1 = 2,1,1
U ovom slucaju iste kombinacije se pojavljuju na istom nivou broja sibica pa je lakse za pracenje.
Zapravo cak ti i ne treba da gledas "sibice" nego da gledas mesta gde sibice nedostaju. Znaci
za prvi slucaj imas da ti nedostaje 0 sibica. za drugi slucaj imas da ti nedostaje jedna sibica
i ona moze da se rasporedi na n-1 mogucih mesta znaci imas 3 mogucnosti (prvo drugo i trece).
i tako ides redom dok ne dodjes do jedne sibice koja moze na n-1 mesta da se stavi (ako pogledas ovaj
slucaj videces da se sibice simetricno rasporedjuju sa pocetka do kraja pa to uvek ostavlja mogucnost za iste sabirke
ali u suprotnom rasporedu)
1+3 = 3+1 = 1,3
Eto, nadam se da sam ti pomogao kako mozes sve razmisljati da bi resio ovaj problem.
Ovako mi je kod u pascalu,ali mi javlja 201 Error.Pošto neke druge zadatke koje pokrenem na svom računaru izacuje isto taj error,a ako pokrenem na drugom radi ako možete da vidite je li greška u kodu ili u kompajleru(free pascal)
Code: program p1;
type
niz=array[1..30]of integer;
procedure stampaniza(x:niz;n:integer);
var
i:integer;
begin
for i:=1 to n-1 do
write(x[i],' + ');
writeln(x[n]);
end;
function suma_niza(n:integer;x:niz):integer;
var
i,s:integer;
begin
s:=0;
for i:=1 to n do
s:=s+x[i];
suma_niza:=s;
end;
procedure razbij(br,n,j,prvi:integer;x:niz);
{br-trazeni broj ; n:ostatak broja koji se razbija
j: indeks u nizu ; prvi:prvi broj u nizu x}
var
t:integer;
begin
x[j]:=n;
if prvi>0 then
if suma_niza(j,x)=br then
begin
stampaniza(x,j);
if x[j]<3 then razbij(br,prvi-1,1,prvi-1,x)
else
begin
t:=x[j];
razbij(t,t-1,j,t-1,x);
end;
end
else razbij(br,br-n,j+1,prvi,x);
end;
var
x:niz;
br:integer;
begin
write('Unesite broj: ');
readln(br);
razbij(br,br-1,1,br-1,x);
readln;
Kako???Jer baš ne razumijem šta radi
Vlaiv ,ova tvoja ideja mi pravi varijacije. 1+2+1=1+1+2=2+1+1 a program bi trebao da mi odštampa samo jedno od ovih rešenja
Pa, poziva funkciju q. Funkcija q prihvata brojeve m i n i string prefix i ispisuje sva rastavljanja broja m na sabirke ne veće od n pri čemu svakom ispisu prethodi dati prefiks. Zar nije jasno da onda poziv q(n,n,s), gse je s prazan string obavlja posao?
E, sad, kako radi funkcija q. Pa, imamo dve vrste rastavljanja broja m na sabirke ne veće od n: one koji počinju sa n i one koje počinju brojem manjim od n. Potpis
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
Novi program,radi ali mi ista rešenja štampa više puta
Code: program p1;
procedure q(m,n:integer;prefix:string);
var
s:string;
begin
if ((m>0) and (n>0)) then
begin
if n>=m then
begin
str(m,s);{konvertuje integer n u string s}
writeln(prefix+s);
q(m,m-1,prefix);
end;
str(n,s);
q(m-n,n-1,prefix+s+'+');
q(m,n-1,prefix);
end;
end;
var
s:string;
n:integer;
begin
write('Broj: ');
readln(n);
s:='';
q(n,n,s);
readln;
end.
Code: program p1;
procedure q(m,n:integer;prefix:string);
var
s:string;
begin
if ((m>0) and (n>0)) then
begin
if n>=m then
begin
str(m,s);{konvertuje integer n u string s}
writeln(prefix+s);
q(m,m-1,prefix);
end
else
begin
str(n,s);
q(m-n,n-1,prefix+s+'+');
q(m,n-1,prefix);
end
end;
end;
var
s:string;
n:integer;
begin
write('Broj: ');
readln(n);
s:='';
q(n,n,s);
readln;
end.
Potpis
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.