[ Smilebey @ 19.04.2006. 17:21 ] @
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?

[ Nedeljko @ 19.04.2006. 21:13 ] @
Code:
#include <iostream>
#include <string>

using namespace std;


typedef unsigned int uint;

string cifra(uint n)
{
    char c[2];
    
    c[0] = n+'0';
    c[1] = 0;
    
    return string(c);
}

string broj(uint n)
{
    if (n<10)
        return cifra(n);
        
    return (broj(n/10)+cifra(n%10));
}

void q(uint m, uint n, string prefix)
{
    if (m==0 || n==0)
        return;

    if (n>=m)
    {
        cout << prefix << broj(m) << "\n";
        q(m,m-1, prefix);
        
        return;
    }
    
    q(m-n,n,prefix+broj(n)+"+");
    q(m,n-1,prefix);
}

void p(uint n)
{
    string s;
    
    q(n,n,s);
}

int main(int argc, char *argv[])
{
    string s;
    
    p(7);
    
    cout << endl;
    
    system("PAUSE");
    return EXIT_SUCCESS;
}
[ miniplazma @ 13.05.2010. 18:59 ] @
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?
[ Nedeljko @ 13.05.2010. 21:22 ] @
Code:
#include <iostream>
#include <string>

using namespace std;


typedef unsigned int uint;

string cifra(uint n)
{
    char c[2];
    
    c[0] = n+'0';
    c[1] = 0;
    
    return string(c);
}

string broj(uint n)
{
    if (n<10)
        return cifra(n);
        
    return (broj(n/10)+cifra(n%10));
}

void q(uint m, uint n, string prefix)
{
    if (m==0 || n==0)
        return;

    if (n>=m)
    {
        cout << prefix << broj(m) << "\n";
        q(m,m-1, prefix);
        
        return;
    }
    
    q(m-n,n-1,prefix+broj(n)+"+");
    q(m,n-1,prefix);
}

void p(uint n)
{
    string s;
    
    q(n,n,s);
}

int main(int argc, char *argv[])
{    
    p(8);    
    cout << endl;  
    system("PAUSE");

    return EXIT_SUCCESS;
}
[ miniplazma @ 13.05.2010. 22:42 ] @

Ne bih da te smaram,ali mozes li da mi objasniš kod(tj ideju),jer ne razumijem c++?Do sad sam radila u pascalu i malo c
Hvala na ovako brzom odgovoru
[ Nedeljko @ 13.05.2010. 23:07 ] @
1. Funkcija cifra vraća kao string cifru datu kao broj.

2. Funkcija broj vraća kao string broj koji zadat kao broj.

3. Funkcija q rastavlja broj m na sabirke ne veće od n ispisujući pritom prefiks dat kao string.

4. Funkcija p obavlja posao.
[ vlaiv @ 14.05.2010. 08:21 ] @
Evo par smernica za razmisljanje:

"Backtracking" metoda:

neka je n suma

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.
[ miniplazma @ 14.05.2010. 13:33 ] @
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;
        
end.
[ Nedeljko @ 15.05.2010. 06:39 ] @
Prvi poziv razbij(t,t-1,j,t-1,x) ulazi u beskonačnu petlju.

Ako staviš if suma_niza(x,j)>=br then, izbegavaš beskonačnu rekurziju, ali je rezultat netačan.
[ miniplazma @ 15.05.2010. 12:33 ] @
Pokušaću danas da napišem novi prog.
Citat:
4. Funkcija p obavlja posao.


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
[ Nedeljko @ 15.05.2010. 15:21 ] @
Citat:
miniplazma: Kako???Jer baš ne razumijem šta radi


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.
[ miniplazma @ 15.05.2010. 17:49 ] @
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.
[ Nedeljko @ 15.05.2010. 18:20 ] @
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.
[ miniplazma @ 16.05.2010. 12:44 ] @
hvala :)