Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Rastaviti broj na sabirke

[es] :: Art of Programming :: Rastaviti broj na sabirke

[ Pregleda: 4547 | Odgovora: 13 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Smilebey
Easy Smilebey
Kod kuće

Član broj: 48170
Poruke: 58
*.dlp197.bih.net.ba.

Sajt: www.art-bike.biz


Profil

icon Rastaviti broj na sabirke19.04.2006. u 17:21 - pre 218 meseci
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?


"Na svetu postoje dve stvari koje su beskonačne. To su univerzum i čovekova glupost. Ali za univerzum nisam baš siguran!"
Albert Einstein
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.sr.gov.yu.



+2789 Profil

icon Re: Rastaviti broj na sabirke19.04.2006. u 21:13 - pre 218 meseci
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;
}

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

miniplazma

Član broj: 240037
Poruke: 68
*.crnagora.net.



Profil

icon Re: Rastaviti broj na sabirke13.05.2010. u 18:59 - pre 168 meseci
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?
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
212.200.65.*



+2789 Profil

icon Re: Rastaviti broj na sabirke13.05.2010. u 21:22 - pre 168 meseci
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;
}

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

miniplazma

Član broj: 240037
Poruke: 68
*.crnagora.net.



Profil

icon Re: Rastaviti broj na sabirke13.05.2010. u 22:42 - pre 168 meseci

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
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
212.200.65.*



+2789 Profil

icon Re: Rastaviti broj na sabirke13.05.2010. u 23:07 - pre 168 meseci
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.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

vlaiv
Vladimir Vlaisavljevic
Novi Sad

Član broj: 15993
Poruke: 352
212.200.249.*



+1 Profil

icon Re: Rastaviti broj na sabirke14.05.2010. u 08:21 - pre 168 meseci
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.
 
Odgovor na temu

miniplazma

Član broj: 240037
Poruke: 68
*.crnagora.net.



Profil

icon Re: Rastaviti broj na sabirke14.05.2010. u 13:33 - pre 168 meseci
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.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
212.200.65.*



+2789 Profil

icon Re: Rastaviti broj na sabirke15.05.2010. u 06:39 - pre 168 meseci
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.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

miniplazma

Član broj: 240037
Poruke: 68
*.crnagora.net.



Profil

icon Re: Rastaviti broj na sabirke15.05.2010. u 12:33 - pre 168 meseci
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
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
212.200.65.*



+2789 Profil

icon Re: Rastaviti broj na sabirke15.05.2010. u 15:21 - pre 168 meseci
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.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

miniplazma

Član broj: 240037
Poruke: 68
*.crnagora.net.



Profil

icon Re: Rastaviti broj na sabirke15.05.2010. u 17:49 - pre 168 meseci
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.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.ptt.rs.



+2789 Profil

icon Re: Rastaviti broj na sabirke15.05.2010. u 18:20 - pre 168 meseci
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.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

miniplazma

Član broj: 240037
Poruke: 68
*.crnagora.net.



Profil

icon Re: Rastaviti broj na sabirke16.05.2010. u 12:44 - pre 168 meseci
hvala :)
 
Odgovor na temu

[es] :: Art of Programming :: Rastaviti broj na sabirke

[ Pregleda: 4547 | Odgovora: 13 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.