|
[quote="mew_17"](a) Opisite rijecima neki pohlepni algoritam i objasnite zasto je pohlepan. Dokazite da algoritam uvijek nade minimalan broj sekundi ili konstruirajte kontraprimjer.[/quote]
Npr. u svakom koraku nadji [tex]\min\arg_k\{ \max\{ x_k, x_{k+1} \} \}[/tex], tj. nadji [tex]k[/tex] za koji je vrijeme racunanja najmanje.
Protuprimjer optimalnosti: [tex]19+17+17+19 = 72[/tex]
Algoritam: [tex]19+17+17+19 = 19+(17+17)+19 = 19+34+19 = (19+34)+19 = 53+19 = 72[/tex] (vrijeme: [tex]17+34+53 = 104[/tex])
Optimalno: [tex]19+17+17+19 = (19+17)+17+19 = 36+17+19 = 36+(17+19) = 36+36 = 72[/tex] (vrijeme: [tex]19+19+36 = 74[/tex])
[quote="mew_17"](b) Neka je M(p; q) minimalan broj sekundi da bi se izracunao zbroj a[p]+a[p+1]+...+a[q]. Napisite rekurzivnu formulu za M(p; q). Zatim, koristeci dinamicko programiranje, napisite funkciju int M(int p, int q) koja pozvana sa M(0, n-1) vraca minimalan broj sekundi za izracunavanje zbroja a[0]+a[1]+...+a[n-1]. Pretpostavite da je a globalna varijabla.[/quote]
[tex]M(p; q) = \min_k \{ M(p; k) + \max\{a_k, a_{k+1} \} + M(k+1; q) \}.[/tex]
| mew_17 (napisa): | | (a) Opisite rijecima neki pohlepni algoritam i objasnite zasto je pohlepan. Dokazite da algoritam uvijek nade minimalan broj sekundi ili konstruirajte kontraprimjer. |
Npr. u svakom koraku nadji [tex]\min\arg_k\{ \max\{ x_k, x_{k+1} \} \}[/tex], tj. nadji [tex]k[/tex] za koji je vrijeme racunanja najmanje.
Protuprimjer optimalnosti: [tex]19+17+17+19 = 72[/tex]
Algoritam: [tex]19+17+17+19 = 19+(17+17)+19 = 19+34+19 = (19+34)+19 = 53+19 = 72[/tex] (vrijeme: [tex]17+34+53 = 104[/tex])
Optimalno: [tex]19+17+17+19 = (19+17)+17+19 = 36+17+19 = 36+(17+19) = 36+36 = 72[/tex] (vrijeme: [tex]19+19+36 = 74[/tex])
| mew_17 (napisa): | | (b) Neka je M(p; q) minimalan broj sekundi da bi se izracunao zbroj a[p]+a[p+1]+...+a[q]. Napisite rekurzivnu formulu za M(p; q). Zatim, koristeci dinamicko programiranje, napisite funkciju int M(int p, int q) koja pozvana sa M(0, n-1) vraca minimalan broj sekundi za izracunavanje zbroja a[0]+a[1]+...+a[n-1]. Pretpostavite da je a globalna varijabla. |
[tex]M(p; q) = \min_k \{ M(p; k) + \max\{a_k, a_{k+1} \} + M(k+1; q) \}.[/tex]
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.  |
