Kombinatorika :: zadatak

[ Divjak @ 16.04.2005. 23:44 ] @

Radi se o zadatku za takmicenje iz programiranja, no nije ni bitno...

Dat je broj n
Na koliko se nacina moze dobiti broj n sabiranjem brojeva 1,2,3,4,5 ako se isti mogu ponavljati redom m1,m2,m3,m4,m5 puta uzastopno...
(ne znam da li sam najbolje formulisao - 1 se sme uzastopno ponoviti m1 puta, 2 m2 puta,...)

kako ovo resiti?

[ gpreda @ 18.04.2005. 12:17 ] @

Resenje je f(m1, m1, m2, m2, m3, m3, m4, m4, m5, m5, n), a funkcija je data rekurzivnom formulom:

Code:

int f(int m1, int mo1, int m2, int mo2, int m3, int mo3, int m4, int mo4, int m5, int mo5, int n)
{
    int rez = 0;

    if (mo1 > 0 && n >= 1)
        rez += f(m1, mo1 - 1, m2, m2, m3, m3, m4, m4, m5, m5, n - 1);

    if (mo2 > 0 && n >= 2)
        rez += f(m1, m1, m2, mo2 - 1, m3, m3, m4, m4, m5, m5, n - 2);

    if (mo3 > 0 && n >= 3)
        rez += f(m1, m1, m2, m2, m3, mo3 - 1, m4, m4, m5, m5, n - 3);

    if (mo4 > 0 && n >= 4)
        rez += f(m1, m1, m2, m2, m3, m3, m4, mo4 - 1, m5, m5, n - 4);

    if (mo5 > 0 && n >= 5)
        rez += f(m1, m1, m2, m2, m3, m3, m4, m4, m5, mo5 - 1, n - 5);

    return rez;
}

Objasnjenje: funkcija bira jedan po jedan sabirak, sve dok se n ne smanji na nulu. Kada za tekuci sabirak izaberemo neki broj, moramo voditi racuna koliko jos puta uzastopno mozemo upotrebiti taj isti broj - zato sluze vrednosti mo1, mo2, mo3, mo4 i mo5 (kada izaberemo na primer dvojku, mo2 ce se smanjiti za jedan, a mo1, mo3, mo4 i mo5 ce se postaviti na pocetne vrednosti).

[ Divjak @ 18.04.2005. 16:24 ] @

ne znam da li ovo radi u cpp ali koliko ja vidim nesto malo fali... evo kako treba da izgleda (u pascalu)

k1p,k2p,k3p,k4p,k5p - pocetne vrednosi (umesto m1,m2,m3,m4,m5)

Code:

PROCEDURE RACUNAJ(bk1,bk2,bk3,bk4,bk5,n:integer);
BEGIN
        if n=0 then inc(rez);
        if (bk1>0) and (n>=1) then begin
                RACUNAJ(bk1-1,bk2,bk3,bk4,bk5,n-1);
                bk2:=k2p;
                bk3:=k3p;
                bk4:=k4p;
                bk5:=k5p;
        end;
        if (bk2>0) and (n>=2) then begin
                RACUNAJ(bk1,bk2-1,bk3,bk4,bk5,n-2);
                bk1:=k1p;
                bk3:=k3p;
                bk4:=k4p;
                bk5:=k5p;
        end;
        if (bk3>0) and (n>=3) then begin
                RACUNAJ(bk1,bk2,bk3-1,bk4,bk5,n-3);
                bk1:=k1p;
                bk2:=k2p;
                bk4:=k4p;
                bk5:=k5p;
        end;
        if (bk4>0) and (n>=4) then begin
                RACUNAJ(bk1,bk2,bk3,bk4-1,bk5,n-4);
                bk1:=k1p;
                bk2:=k2p;
                bk3:=k3p;
                bk5:=k5p;
        end;
        if (bk5>0) and (n>=5) then begin
                RACUNAJ(bk1,bk2,bk3,bk4,bk5,n-5);
                bk1:=k1p;
                bk2:=k2p;
                bk3:=k3p;
                bk4:=k4p;
        end;

END;

[ gpreda @ 18.04.2005. 19:24 ] @

Jel si siguran da je tvoje resenje dobro, da li si ga testirao? I uopste, da li si dobro objasnio zadakat?

Recimo slucaj da je zbir jednak 2 + 2 + ... Ovaj slucaj pocinje kada udjes u drugi IF, zatim ces u sledecem ulazu u funkciju upasti u prvi IF i vratices bk2 na k2p. Nikada neces smanjiti bk2 za dva?

[ Divjak @ 18.04.2005. 20:46 ] @

moje resenje je dobro, testirano...
pogledaj dobro kada se vrednosti vracaju na prvobitne - posle pozivanja procedure

u slucaju da nisam dobro objasnio zadatak ako je n=5, k1p=1, k2p=2, k3p,k4p,k5p=0
onda postoje 3 resenja: 1+2+2, 2+1+2, 2+2+1

[ gpreda @ 18.04.2005. 21:32 ] @

Dobro, mozda je tacno, nisam ulazio u dublju analizu koda. Hteo sam da kazem da ti je funkcija dosta nerazumljiva.

Ako izaberes, na primer, dvojku kao sabirak u jednom trenutku, ti pozivas rekurzivnu funkciju sa starim parametrima za bk1, bk3, bk4 i bk5, a ispravno je da ih postavis na kp1, kp3, kp4 i kp5 (pocetne vrednosti). Zasto to radi (ako uopste radi) kada ih vratis posle poziva funkcije nije odmah jasno. Da li si testirao na zvanicnim test primerima na takmicenju?

Probaj da objasnis svoj algoritam recima.

[ Divjak @ 18.04.2005. 22:11 ] @

bio si u pravu...

Code:

PROCEDURE RACUNAJ(bk1,bk2,bk3,bk4,bk5,n:integer);
BEGIN
        if n=0 then inc(rez);
        if (bk1>0) and (n>=1) then RACUNAJ(bk1-1,k2p,k3p,k4p,k5p,n-1);
        if (bk2>0) and (n>=2) then RACUNAJ(k1p,bk2-1,k3p,k4p,k5p,n-2);
        if (bk3>0) and (n>=3) then RACUNAJ(k1p,k2p,bk3-1,k4p,k5p,n-3);
        if (bk4>0) and (n>=4) then RACUNAJ(k1p,k2p,k3p,bk4-1,k5p,n-4);
        if (bk5>0) and (n>=5) then RACUNAJ(k1p,k2p,k3p,k4p,bk5-1,n-5);
END;

sad je dobro, s' tim sto recimo vec za n>30 hoce malo da potraje a da ne pricamo za 600 sto je i MAXn na takmicenju... Ja ne vidim kako se ovo moze optimizovati, a ti?

[ gpreda @ 19.04.2005. 08:44 ] @

Ako se uradi na ovakav nacin, slozenost algoritma je eksponencijalna, i ne moze proci ni na jednom takmicenju. Bitno je da izbacis rekurziju iz resenja!

Na primer, isto je kada bi ovako napisao funkciju koja racuna n-ti Fibonacijev broj:

Code:

int fib(int n)
{
    if (n == 0 || n == 1)
        return 1;

    return fib(n - 1) + fib(n - 2);
}

Zasto je ovo sporo? Zato sto kada racuna fib(10), poziva se fib(9) i fib(8). Kada racunas fib(9), ponovo poziva fib(8) - a nema potrebe zato sto je fib(8) vec jednom izracunao. fib(7) ce se 3 puta racunati, itd.

Bolje je resenje ici unapred (dinamicko programiranje) nego ici unazad (rekurzija). Kada resis problem za K < N, treba da zapamtis koliko ima suma koje se zavrsavaju sa jednom jedinicom, dve jedinice, ..., m1 jedinica; koliko suma se zavrsava sa jednom dvojkom, itd.