|
[quote="Redeemer"]moze skica rjesenja za zadatke 9 i 10 (vjezbe za drugi kolokvij)
ovo za misa i sir ...
ako krene od (1,1)
onda slijedeci korak je ili (2,1) ili (1,2) ...
(m+1,n) ili (m,n+1)
kako uopce postaviti rekurziju da obilazi apsolutno sve moguce korake od (1,1) do (m,n) i onda izbaci onaj sa najvecim zbrojem?
koja je uopce ideja tog dinamickog programiranja?
jasno mi je za fibonaccijeve brojeve
[code:1]fib(1)=1
fib(2)=1
fib(n)=fib(n-2)+fib(n-1)[/code:1]
ovdje bi trebalo biti
[code:1]mis(1,1)=a
mis(1,2)=b
mis(1,3)=c
(...)
mis(m,n)=mis(m-1,n)+mis(m,n)
ili
mis(m,n)=mis(m,n-1)+mis(m,n)
dok ne dodje do (1,1)
obrnuto
i=1
mis(m,n)=mis(x,y) + mis(x+i,y)
ili
mis(m,n)=mis(x,y) + mis(x,y+i)
...while (x<=m) && (y<=n)[/code:1]
van sebe sam... please please help
hvala![/quote]
Također ne slušam kolegij, ali čini mi se da ide ovako:
Kriterij zaustavljanja je naravno kada miš dođe u točku (m,n) a ne kad dođe u (1,1)
ako je u točki (m,n) return(matrica(m,n));
ako je u točki (nešto<m, n) onda može ići samo dolje
ako je u točki (m,nešto<n) onda može ići samo desno
ako nije ništa od navedenog onda ide i desno i dolje.
Naravno sumiraš vrijednosti i uzimaš najveće.
Nest tipa ovoga bi trebalo radit:
int s=0;
if x==m && y==n return matrica[x][y];
else if x==m return(pozovi sa x+1, n);
else if y==n return(pozovi sa m,y+1);
else
{
int a=(pozovi sa x+1,n),b=(pozovi sa m,y+1);
s=s+max(a,b);
return s;
}
Koristeći dinamičko programiranje... Koliko se sjećam to bi bilo da upisuješ u novu globalnu matricu najbolje puteve, dakle ako si od 1,1 do 3,3 dosao i sakupio 20, a nakon toga isao drugim putem i sakupio 10, taj drugi put ne trebas vise razmatrat...tj. tu se već možeš zaustavit. Znači trebao bi kada dođeš u neku točku gledat koliko si sakupio sireva, te to zapisat na to mjesto, slijedeći put gledaš da li si drugim putem sakupio više, ako jesi nastavljaš, ako nisi prekidaš taj put....
Naravno, moguće da se misli na nešto sasvim drugo te da sam u krivu... Ovo ti je za prvu ruku, dok me netko ne ispravi! :D
A za pohlepu nisi pitao, pa neću ni pisat. Ionako smatram da je to najlakše za napisat, objasnit...štogod se traži...
I da ideja dinamičkog programiranja jest da se na uštrb memorije dobije na brzini izvođenja programa. Ja sam to najbolje shvatio na slijedećem primjeru:
recimo da radiš sa faktorijelama. Svaki put kad izračunaš neku faktorijelu spremiš je u polje na njezin indeks. Sad kad bi u nekom djelu programa trebao 20! ne bi morao sve isponova računati nego bi pogledao da li imaš već izračunato, ako imaš super, ako ne, pogledaš koji si zadnji izračunao pa računaš dalje... i naravno prije dođeš do svojeg broja sa manje operacija jer koristiš nešto što si već prije dobio.
Ili isto možeš gledat sa fibonačijevim brojevima... ako ti zatreba 101 fibonačijev broj pogledaš ako imaš već super,ako ne nastaviš od zadnja dva koja si izračunao.
To bi bili ti neki jednostavni primjeri... Nadam se da je pomoglo... i da je točno to što sam pisao.
:P
| Redeemer (napisa): | moze skica rjesenja za zadatke 9 i 10 (vjezbe za drugi kolokvij)
ovo za misa i sir ...
ako krene od (1,1)
onda slijedeci korak je ili (2,1) ili (1,2) ...
(m+1,n) ili (m,n+1)
kako uopce postaviti rekurziju da obilazi apsolutno sve moguce korake od (1,1) do (m,n) i onda izbaci onaj sa najvecim zbrojem?
koja je uopce ideja tog dinamickog programiranja?
jasno mi je za fibonaccijeve brojeve
| Kod: | fib(1)=1
fib(2)=1
fib(n)=fib(n-2)+fib(n-1) |
ovdje bi trebalo biti
| Kod: | mis(1,1)=a
mis(1,2)=b
mis(1,3)=c
(...)
mis(m,n)=mis(m-1,n)+mis(m,n)
ili
mis(m,n)=mis(m,n-1)+mis(m,n)
dok ne dodje do (1,1)
obrnuto
i=1
mis(m,n)=mis(x,y) + mis(x+i,y)
ili
mis(m,n)=mis(x,y) + mis(x,y+i)
...while (x<=m) && (y<=n) |
van sebe sam... please please help
hvala! |
Također ne slušam kolegij, ali čini mi se da ide ovako:
Kriterij zaustavljanja je naravno kada miš dođe u točku (m,n) a ne kad dođe u (1,1)
ako je u točki (m,n) return(matrica(m,n));
ako je u točki (nešto<m, n) onda može ići samo dolje
ako je u točki (m,nešto<n) onda može ići samo desno
ako nije ništa od navedenog onda ide i desno i dolje.
Naravno sumiraš vrijednosti i uzimaš najveće.
Nest tipa ovoga bi trebalo radit:
int s=0;
if x==m && y==n return matrica[x][y];
else if x==m return(pozovi sa x+1, n);
else if y==n return(pozovi sa m,y+1);
else
{
int a=(pozovi sa x+1,n),b=(pozovi sa m,y+1);
s=s+max(a,b);
return s;
}
Koristeći dinamičko programiranje... Koliko se sjećam to bi bilo da upisuješ u novu globalnu matricu najbolje puteve, dakle ako si od 1,1 do 3,3 dosao i sakupio 20, a nakon toga isao drugim putem i sakupio 10, taj drugi put ne trebas vise razmatrat...tj. tu se već možeš zaustavit. Znači trebao bi kada dođeš u neku točku gledat koliko si sakupio sireva, te to zapisat na to mjesto, slijedeći put gledaš da li si drugim putem sakupio više, ako jesi nastavljaš, ako nisi prekidaš taj put....
Naravno, moguće da se misli na nešto sasvim drugo te da sam u krivu... Ovo ti je za prvu ruku, dok me netko ne ispravi! 
A za pohlepu nisi pitao, pa neću ni pisat. Ionako smatram da je to najlakše za napisat, objasnit...štogod se traži...
I da ideja dinamičkog programiranja jest da se na uštrb memorije dobije na brzini izvođenja programa. Ja sam to najbolje shvatio na slijedećem primjeru:
recimo da radiš sa faktorijelama. Svaki put kad izračunaš neku faktorijelu spremiš je u polje na njezin indeks. Sad kad bi u nekom djelu programa trebao 20! ne bi morao sve isponova računati nego bi pogledao da li imaš već izračunato, ako imaš super, ako ne, pogledaš koji si zadnji izračunao pa računaš dalje... i naravno prije dođeš do svojeg broja sa manje operacija jer koristiš nešto što si već prije dobio.
Ili isto možeš gledat sa fibonačijevim brojevima... ako ti zatreba 101 fibonačijev broj pogledaš ako imaš već super,ako ne nastaviš od zadnja dva koja si izračunao.
To bi bili ti neki jednostavni primjeri... Nadam se da je pomoglo... i da je točno to što sam pisao.
|
