| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
PilotGrip
Forumaš(ica)
Pridružen/a: 08. 02. 2017. (16:10:52)
Postovi: (7)16
|
 Postano: 12:27 čet, 9. 2. 2017 Naslov: 2.kolokvij pomoć |
    |
|
|
Pozdrav! :)
Imam pitanje vezano za zadatak iz 2014./15. iz drugog kolokvija. (http://degiorgi.math.hr/prog1/kolokviji/p1-kolokvij-1415-2.pdf)
Radi se o 4. zadataku gdje treba primjeniti Hornerov algoritam. Znam jednostavne zadatke rješiti preko Hornerovog algoritma, ali ovako kompliciranije ne znam i ne shvaćam rješenje, pa ako bi mi mogao netko objasniti što i kako?
Evo rješenje:
#include <stdio.h>
double horner(double a[], int n, double x)
{
double p=0, q=0, fakt=1, y;
int i;
[b]
for(i=1; i<=2*n+3; i++)
fakt*=i; /*[/b]izracunamo linearno vrijednost pocetnog faktorijela, a onda cemo ga
samnjivati u hornerovoj petlji.*/
[b] y=3*x;[/b] /*polinome rastavimo na dva dijela i ocito (3^k)(x^k)=(3x)^k pa vrijednost drugog
polinoma racunamo u tocki y=3*x*/
for(i=n; i>=0; i--){
[b] fakt/=(2*i+3)*(2*i+2);
p=p*x+a[2*i]*fakt;[/b]
q=q*y-a[2*(n-i)+1];
}
return p+q;
}
Podebljanije stvari pogotovo ne razumijem.
Pozdrav! 
Imam pitanje vezano za zadatak iz 2014./15. iz drugog kolokvija. (http://degiorgi.math.hr/prog1/kolokviji/p1-kolokvij-1415-2.pdf)
Radi se o 4. zadataku gdje treba primjeniti Hornerov algoritam. Znam jednostavne zadatke rješiti preko Hornerovog algoritma, ali ovako kompliciranije ne znam i ne shvaćam rješenje, pa ako bi mi mogao netko objasniti što i kako?
Evo rješenje:
#include <stdio.h>
double horner(double a[], int n, double x)
{
double p=0, q=0, fakt=1, y;
int i;
for(i=1; i⇐2*n+3; i++)
fakt*=i; /*izracunamo linearno vrijednost pocetnog faktorijela, a onda cemo ga
samnjivati u hornerovoj petlji.*/
y=3*x; /*polinome rastavimo na dva dijela i ocito (3^k)(x^k)=(3x)^k pa vrijednost drugog
polinoma racunamo u tocki y=3*x*/
for(i=n; i>=0; i–){
fakt/=(2*i+3)*(2*i+2);
p=p*x+a[2*i]*fakt;
q=q*y-a[2*(n-i)+1];
}
return p+q;
}
Podebljanije stvari pogotovo ne razumijem.
|
|
| [Vrh] |
|
mdoko
Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol: 
Lokacija: Heriot-Watt University, Edinburgh
|
| Postano: 17:35 čet, 9. 2. 2017 Naslov: Re: 2.kolokvij pomoć |
|
|
|
Za ubuduće, please piši kodove unutar [tt][co[i][/i]de]...[/co[i][/i]de][/tt]. Ovako:
[code:1]double horner(double a[], int n, double x)
{
double p=0, q=0, fakt=1, y;
int i;
for(i=1; i<=2*n+3; i++)
fakt*=i; /*izracunamo linearno vrijednost pocetnog faktorijela, a onda cemo ga smanjivati u hornerovoj petlji.*/
y=3*x; /*polinome rastavimo na dva dijela i ocito (3^k)(x^k)=(3x)^k pa vrijednost drugog polinoma racunamo u tocki y=3*x*/
for(i=n; i>=0; i--){
fakt/=(2*i+3)*(2*i+2);
p=p*x+a[2*i]*fakt;
q=q*y-a[2*(n-i)+1];
}
return p+q;
}[/code:1]
U zadatku treba izračunati vrijednost izraza [tex]P_n(x) = \sum\limits_{k=0}^{n}\left(a_{2k}(2k+1)! - a_{2(n-k)+1}3^k\right)x^k[/tex].
Očito je [tex]P_n(x) = \sum\limits_{k=0}^{n}a_{2k}(2k+1)!x^k - \sum\limits_{k=0}^{n}a_{2(n-k)+1}(3x)^k[/tex], što znači da [tex]P_n(x)[/tex] možemo računati kao [tex]P_n(x) = A_n(x) - B_n(3x)[/tex], pri čemu je [tex]A_n(x) = \sum\limits_{k=0}^{n}a_{2k}(2k+1)!x^k[/tex], a [tex]B_n(x) = a_{2(n-k)+1}3^kx^k[/tex].
Izrazi [tex]A_n(x)[/tex] i [tex]B_n(3x)[/tex] se lako izračunavaju pomoću Hornerovog algoritma.
Ovo bi trebalo razjasniti što se je mislilo pod "polinome rastavimo na dva dijela" i zašto jednog izračunavamo u [i]x[/i], a drugog u [i]3x[/i].
Preostalo je još pitanje oko optimizacije programa pametnijim računanjem faktorijela, ali ne bih još ulazio u to. Prvo trebaš moći rijeešiti zadatak bez hvatanja bonus bodova, a onda se kreni hrvati sa zahtjevnijim problemima.
Ako ti još uvijek nije jasno kako riješiti zadatak (u varijanti za 15 bodova), onda pitaj za dodatna pojašnjenja. Ako uspiješ i interesira te kako uhvatiti još onih dodatnih 5 bodova, onda ćemo se upustiti u ostatak diskusije.
Za ubuduće, please piši kodove unutar [code]...[/code]. Ovako:
| Kod: | double horner(double a[], int n, double x)
{
double p=0, q=0, fakt=1, y;
int i;
for(i=1; i<=2*n+3; i++)
fakt*=i; /*izracunamo linearno vrijednost pocetnog faktorijela, a onda cemo ga smanjivati u hornerovoj petlji.*/
y=3*x; /*polinome rastavimo na dva dijela i ocito (3^k)(x^k)=(3x)^k pa vrijednost drugog polinoma racunamo u tocki y=3*x*/
for(i=n; i>=0; i--){
fakt/=(2*i+3)*(2*i+2);
p=p*x+a[2*i]*fakt;
q=q*y-a[2*(n-i)+1];
}
return p+q;
} |
U zadatku treba izračunati vrijednost izraza [tex]P_n(x) = \sum\limits_{k=0}^{n}\left(a_{2k}(2k+1)! - a_{2(n-k)+1}3^k\right)x^k[/tex].
Očito je [tex]P_n(x) = \sum\limits_{k=0}^{n}a_{2k}(2k+1)!x^k - \sum\limits_{k=0}^{n}a_{2(n-k)+1}(3x)^k[/tex], što znači da [tex]P_n(x)[/tex] možemo računati kao [tex]P_n(x) = A_n(x) - B_n(3x)[/tex], pri čemu je [tex]A_n(x) = \sum\limits_{k=0}^{n}a_{2k}(2k+1)!x^k[/tex], a [tex]B_n(x) = a_{2(n-k)+1}3^kx^k[/tex].
Izrazi [tex]A_n(x)[/tex] i [tex]B_n(3x)[/tex] se lako izračunavaju pomoću Hornerovog algoritma.
Ovo bi trebalo razjasniti što se je mislilo pod "polinome rastavimo na dva dijela" i zašto jednog izračunavamo u x, a drugog u 3x.
Preostalo je još pitanje oko optimizacije programa pametnijim računanjem faktorijela, ali ne bih još ulazio u to. Prvo trebaš moći rijeešiti zadatak bez hvatanja bonus bodova, a onda se kreni hrvati sa zahtjevnijim problemima.
Ako ti još uvijek nije jasno kako riješiti zadatak (u varijanti za 15 bodova), onda pitaj za dodatna pojašnjenja. Ako uspiješ i interesira te kako uhvatiti još onih dodatnih 5 bodova, onda ćemo se upustiti u ostatak diskusije.
_________________
Extraordinary claims require extraordinary evidence. – Carl Sagan
|
|
| [Vrh] |
|
krilo
Forumaš(ica)
Pridružen/a: 01. 11. 2016. (14:45:48)
Postovi: (4E)16
Spol: 
|
| Postano: 18:12 čet, 9. 2. 2017 Naslov: |
|
|
|
E hvala PilotGripu što je načeo temu, mene zanima isti zadatak. Oni su u rješenjima program napisali ovako (direktno copy-pasteano):
[code:1]double horner(int n, double t[], double x)
{
int i;
unsigned f=1;
double p=0, b;
b=x-2;
for(i=n; i>=0; i--){
p=p*b+t[i]*f;
f*=n-i+1; /*s ovim racunamo faktorijele linearnom slozenoscu*/
}
return p;
}[/code:1]
Meni samo nije jasno kako su oni došli do [tt]p=p*b+t[i]*f[/tt] i [tt]f*=n-i+1[/tt]. Probala sam raspisati, ali ništa smisleno od toga svega. (Ako ti se da razjašnjavati, bilo bi super; ako ne, ne sekiraj se, vjerojatno neće toga sutra biti u kolokviju. :) )
E hvala PilotGripu što je načeo temu, mene zanima isti zadatak. Oni su u rješenjima program napisali ovako (direktno copy-pasteano):
| Kod: | double horner(int n, double t[], double x)
{
int i;
unsigned f=1;
double p=0, b;
b=x-2;
for(i=n; i>=0; i--){
p=p*b+t[i]*f;
f*=n-i+1; /*s ovim racunamo faktorijele linearnom slozenoscu*/
}
return p;
} |
Meni samo nije jasno kako su oni došli do p=p*b+t[i]*f i f*=n-i+1. Probala sam raspisati, ali ništa smisleno od toga svega. (Ako ti se da razjašnjavati, bilo bi super; ako ne, ne sekiraj se, vjerojatno neće toga sutra biti u kolokviju. )
|
|
| [Vrh] |
|
PilotGrip
Forumaš(ica)
Pridružen/a: 08. 02. 2017. (16:10:52)
Postovi: (7)16
|
| Postano: 21:00 čet, 9. 2. 2017 Naslov: Re: 2.kolokvij pomoć |
|
|
|
[quote="mdoko"]
U zadatku treba izračunati vrijednost izraza [tex]P_n(x) = \sum\limits_{k=0}^{n}\left(a_{2k}(2k+1)! - a_{2(n-k)+1}3^k\right)x^k[/tex].
Očito je [tex]P_n(x) = \sum\limits_{k=0}^{n}a_{2k}(2k+1)!x^k - \sum\limits_{k=0}^{n}a_{2(n-k)+1}(3x)^k[/tex], što znači da [tex]P_n(x)[/tex] možemo računati kao [tex]P_n(x) = A_n(x) - B_n(3x)[/tex], pri čemu je [tex]A_n(x) = \sum\limits_{k=0}^{n}a_{2k}(2k+1)!x^k[/tex], a [tex]B_n(x) = a_{2(n-k)+1}3^kx^k[/tex].
Izrazi [tex]A_n(x)[/tex] i [tex]B_n(3x)[/tex] se lako izračunavaju pomoću Hornerovog algoritma.
Ovo bi trebalo razjasniti što se je mislilo pod "polinome rastavimo na dva dijela" i zašto jednog izračunavamo u [i]x[/i], a drugog u [i]3x[/i].
Ako ti još uvijek nije jasno kako riješiti zadatak (u varijanti za 15 bodova), onda pitaj za dodatna pojašnjenja. .[/quote]
Hvala! Jel bi mogao jos dodatno pojasniti ostatak rjesenja? Mislim da znam kako bih krenuo, ali ne bih znao dovrsiti i neke stvari mi nisu jasne pri nastavku tog zadatka. Npr. Mi rastavljamo polinom na vise dijelova. Npr. F(n)=n, h(x)=x, r(x)=?, a(g[i])=?
Hvala!
| mdoko (napisa): |
U zadatku treba izračunati vrijednost izraza [tex]P_n(x) = \sum\limits_{k=0}^{n}\left(a_{2k}(2k+1)! - a_{2(n-k)+1}3^k\right)x^k[/tex].
Očito je [tex]P_n(x) = \sum\limits_{k=0}^{n}a_{2k}(2k+1)!x^k - \sum\limits_{k=0}^{n}a_{2(n-k)+1}(3x)^k[/tex], što znači da [tex]P_n(x)[/tex] možemo računati kao [tex]P_n(x) = A_n(x) - B_n(3x)[/tex], pri čemu je [tex]A_n(x) = \sum\limits_{k=0}^{n}a_{2k}(2k+1)!x^k[/tex], a [tex]B_n(x) = a_{2(n-k)+1}3^kx^k[/tex].
Izrazi [tex]A_n(x)[/tex] i [tex]B_n(3x)[/tex] se lako izračunavaju pomoću Hornerovog algoritma.
Ovo bi trebalo razjasniti što se je mislilo pod "polinome rastavimo na dva dijela" i zašto jednog izračunavamo u x, a drugog u 3x.
Ako ti još uvijek nije jasno kako riješiti zadatak (u varijanti za 15 bodova), onda pitaj za dodatna pojašnjenja. . |
Hvala! Jel bi mogao jos dodatno pojasniti ostatak rjesenja? Mislim da znam kako bih krenuo, ali ne bih znao dovrsiti i neke stvari mi nisu jasne pri nastavku tog zadatka. Npr. Mi rastavljamo polinom na vise dijelova. Npr. F(n)=n, h(x)=x, r(x)=?, a(g[i])=?
Hvala!
|
|
| [Vrh] |
|
mdoko
Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol:
Lokacija: Heriot-Watt University, Edinburgh
|
| Postano: 0:20 pet, 10. 2. 2017 Naslov: |
|
|
|
[quote="PilotGrip"]Npr. Mi rastavljamo polinom na vise dijelova. Npr. F(n)=n, h(x)=x, r(x)=?, a(g[i])=?[/quote]
Sad mi ništa nije jasno. Što su F, h, r, a, g? :grebgreb:
Što uopće znači "mi rastavljamo polinom na više djelova"? Kakvih djelova? Koji "mi"?
[quote="krilo"]E hvala PilotGripu što je načeo temu, mene zanima isti zadatak. Oni su u rješenjima program napisali ovako (direktno copy-pasteano):
[code:1]double horner(int n, double t[], double x)
{
int i;
unsigned f=1;
double p=0, b;
b=x-2;
for(i=n; i>=0; i--){
p=p*b+t[i]*f;
f*=n-i+1; /*s ovim racunamo faktorijele linearnom slozenoscu*/
}
return p;
}[/code:1]
Meni samo nije jasno kako su oni došli do [tt]p=p*b+t[i]*f[/tt] i [tt]f*=n-i+1[/tt]. Probala sam raspisati, ali ništa smisleno od toga svega.[/quote]
Koji zadatak? Ovo mi nikako ne izgleda kao rješenje zadatka o kojem smo raspravljali u prethodnim postovima.
[quote]Ako ti se da razjašnjavati, bilo bi super; ako ne, ne sekiraj se, vjerojatno neće toga sutra biti u kolokviju.[/quote]
Rado bih pomogao, ali uopće mi nije jasno što je pitanje, a još manje što vama dvoma nije jasno. :neznam:
| PilotGrip (napisa): | | Npr. Mi rastavljamo polinom na vise dijelova. Npr. F(n)=n, h(x)=x, r(x)=?, a(g[i])=? |
Sad mi ništa nije jasno. Što su F, h, r, a, g? 
Što uopće znači "mi rastavljamo polinom na više djelova"? Kakvih djelova? Koji "mi"?
| krilo (napisa): | E hvala PilotGripu što je načeo temu, mene zanima isti zadatak. Oni su u rješenjima program napisali ovako (direktno copy-pasteano):
| Kod: | double horner(int n, double t[], double x)
{
int i;
unsigned f=1;
double p=0, b;
b=x-2;
for(i=n; i>=0; i--){
p=p*b+t[i]*f;
f*=n-i+1; /*s ovim racunamo faktorijele linearnom slozenoscu*/
}
return p;
} |
Meni samo nije jasno kako su oni došli do p=p*b+t[i]*f i f*=n-i+1. Probala sam raspisati, ali ništa smisleno od toga svega. |
Koji zadatak? Ovo mi nikako ne izgleda kao rješenje zadatka o kojem smo raspravljali u prethodnim postovima.
| Citat: | | Ako ti se da razjašnjavati, bilo bi super; ako ne, ne sekiraj se, vjerojatno neće toga sutra biti u kolokviju. |
Rado bih pomogao, ali uopće mi nije jasno što je pitanje, a još manje što vama dvoma nije jasno. 
_________________
Extraordinary claims require extraordinary evidence. – Carl Sagan
|
|
| [Vrh] |
|
PilotGrip
Forumaš(ica)
Pridružen/a: 08. 02. 2017. (16:10:52)
Postovi: (7)16
|
|
| [Vrh] |
|
krilo
Forumaš(ica)
Pridružen/a: 01. 11. 2016. (14:45:48)
Postovi: (4E)16
Spol:
|
| Postano: 8:44 pet, 10. 2. 2017 Naslov: |
|
|
|
Što je PilotGrip mislio je sljedeće: u vsegovoj skripti iz prog1 (malo bedasto od nas pretpostaviti da ju imaš doma :oops: ) piše da ako imamo neki polinom oblika [dtex]p(x) = r(x) \sum_{i=0}^{f(n)}a_{g(i)}h(x)^î,[/dtex] onda (šablonski) Hornerov algoritam izgleda ovako:[code:1]int p=0;
for (i=f(n); i>=0; i--)
{
p = p*h(x) + a[g(i)];
p* = r(x);
} [/code:1]
gdje je p zapravo [tex]p(x)[/tex] vrijednost koju tražimo. Tako je puno lakše računati ako, naravno, znamo svesti polinom na traženi oblik. Što se rješenja tiče, stavili su samo jedno, valjda za sve grupe, pa je i moguće da ovo gornje nije rješenje našeg zadatka. (Al opet, kak da to znam kad ne znam riješiti zadatak? :neznam: )
Što je PilotGrip mislio je sljedeće: u vsegovoj skripti iz prog1 (malo bedasto od nas pretpostaviti da ju imaš doma  ) piše da ako imamo neki polinom oblika [dtex]p(x) = r(x) \sum_{i=0}^{f(n)}a_{g(i)}h(x)^î,[/dtex] onda (šablonski) Hornerov algoritam izgleda ovako: | Kod: | int p=0;
for (i=f(n); i>=0; i--)
{
p = p*h(x) + a[g(i)];
p* = r(x);
} |
gdje je p zapravo [tex]p(x)[/tex] vrijednost koju tražimo. Tako je puno lakše računati ako, naravno, znamo svesti polinom na traženi oblik. Što se rješenja tiče, stavili su samo jedno, valjda za sve grupe, pa je i moguće da ovo gornje nije rješenje našeg zadatka. (Al opet, kak da to znam kad ne znam riješiti zadatak? )
|
|
| [Vrh] |
|
mdoko
Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol:
Lokacija: Heriot-Watt University, Edinburgh
|
| Postano: 15:53 pet, 10. 2. 2017 Naslov: |
|
|
|
Ok, sad mi je jasno. Nije problem u zadatku, nego ste vas dvoje zbunjeni oko Hornerovog algoritma i onda krene pristup preko nekakve šablone, što naravno nikad nije dobro. Sažeto u stihove, [i]"Tko nije drvo razumeo prvo,
pa tek onda sadio, taj nije ništa uradio... I, shvatit će, kad-tad, da ne zna šta je hlad."[/i]
Prema tome, da vidimo kako radi Hormerov algoritam.
Evo, npr. imamo polinom [tex]p(x) = 4x^3 + 7x^2 + 2x + 42[/tex] i netko nam zada neki [tex]\alpha\in\mathbb{R}[/tex] i traži da izračunamo [tex]p(\alpha)[/tex]. To možemo izračunati ovako:
Prvo krenemo s vodećim koeficijentom. To je 4.
Onda vrijednost iz prethodnog koraka pomnožimo s [tex]\alpha[/tex] i dodamo sljedeći koeficijent. Sada imamo [tex]4\alpha+7[/tex].
Onda vrijednost iz prethodnog koraka pomnožimo s [tex]\alpha[/tex] i dodamo sljedeći koeficijent. Sada imamo [tex](4\alpha+7)\alpha + 2 = 4\alpha^2 + 7\alpha + 2[/tex].
Onda vrijednost iz prethodnog koraka pomnožimo s [tex]\alpha[/tex] i dodamo sljedeći koeficijent. Sada imamo [tex](4\alpha^2 + \alpha + 2)\alpha + 42 = 4\alpha^3 + 7\alpha^2 + 2\alpha + 42[/tex].
Sada kad smo iskoristili sve koeficijente, znamo da je traženi rezultat [tex]p(\alpha) = 4\alpha^3 + 7\alpha^2 + 2\alpha + 42[/tex].
Da bude još jasnije, pogledajmo kako se računa za neki konkretni [tex]\alpha[/tex]. Izračunajmo npr. p(2).
Prvo krenemo s vodećim koeficijentom. To je 4.
Onda vrijednost iz prethodnog koraka pomnožimo s 2 i dodamo sljedeći koeficijent. Sada imamo 4 * 2+7 = 21.
Onda vrijednost iz prethodnog koraka pomnožimo s 2 i dodamo sljedeći koeficijent. Sada imamo 21 * 2 + 7 = 49.
Onda vrijednost iz prethodnog koraka pomnožimo s 2 i dodamo sljedeći koeficijent. Sada imamo 49 * 2 + 42 = 140.
Sada kad smo iskoristili sve koeficijente, znamo da je traženi rezultat p(2) = 140.
Nadam se da je sada jasno kako radi [u]i zašto funkcionira[/u] Hornerov algoritam. Ako nije, please pitajte za daljna pojašnjenja.
Ajmo sada na zadatak iz originalnog posta. Zadatak traži da napišemo funkciju koja će računati vrijednost od [tex]P_n(x) = \sum\limits_{k=0}^{n}\left(a_{2k}(2k+1)! - a_{2(n-k)+1}3^k\right)x^k[/tex] u proizvoljno određenoj točki, pri čemu su [tex]a_0,a_1,\ldots,a_{2n+1}[/tex] unaprijed zadani.
Kad malo pojednostavnimo gornji izraz vidimo da je [tex]P_n(x) = A_n(x) - B_n(x)[/tex], pri čemu je [tex]A_n(x) = \sum\limits_{k=0}^{n}a_{2k}(2k+1)!x^k[/tex], a [tex]B_n(x) = \sum\limits_{k=0}^{n}a_{2(n-k)+1}3^kx^k[/tex].
Sada možemo napisati traženu funkciju.
[code:1]/* Prvo dvije pomocne funkcije.
* Racunamo u double-ovima, jer je to tip u kojem se trazi rezultat u zadatku.
*/
/* Funkcija koja racuna 3^n. Funkcija pretpostavlja da je n >= 0. */
double potencija_od_3(int n) {
double rezutat = 1;
for( ; n > 0; --n) rezultat = rezultat * 3;
return rezultat;
}
/* Funkcija koja racuna n!. Funkcija pretpostavlja da je n >= 0. */
double faktorijel(int n) {
double rezultat = 1;
int i;
for (i = 1; i <= n; ++i) rezultat = rezultat * i;
return rezlutat;
}
/* Hornerovim algoritmom razunamo vrijednost polinoma A_n u tocki x.
Funkcija pretpostavlja da niz a sadrzi unaprijed zadane vrijednosti za a_0, a_1, ..., a_{2n+1} */
double A(double a[], int n, double x) {
int k;
double rezultat = a[2 * n] * faktorijel(2 * n + 1); /* Krenemo s vodecim koeficijentom. */
for(k = n -1; k >= 0; --k) {
double koeficijent = a[2 * k] * faktorijel(2 * k + 1); /* Koeficijent koji je sada na redu. */
rezultat = rezultat * x + koeficijent; /* Vrijednost iz prethodnog koraka pomnozimo s x i dodamo koeficijent. */
}
return rezultat; /* Na kraju vratimo izracunatu vrijednost. */
}
/* Hornerovim algoritmom razunamo vrijednost polinoma B_n u tocki x.
Funkcija pretpostavlja da niz a sadrzi unaprijed zadane vrijednosti za a_0, a_1, ..., a_{2n+1} */
double B(double a[], int n, double x) {
int k;
double rezultat = a[1] * potencija_od_3(n); /* Krenemo s vodecim koeficijentom. */
for(k = n -1; k >= 0; --k) {
double koeficijent = a[2 * (n - k)] * potencija_od_3(k); /* Koeficijent koji je sada na redu. */
rezultat = rezultat * x + koeficijent; /* Vrijednost iz prethodnog koraka pomnozimo s x i dodamo koeficijent. */
}
return rezultat; /* Na kraju vratimo izracunatu vrijednost. */
}
/* Konacno mozemo napisati funkciju koja se trazi u zadatku.
Funkcija pretpostavlja da niz a sadrzi unaprijed zadane vrijednosti za a_0, a_1, ..., a_{2n+1} */
double P(double a[], int n, double x) {
return A(a, n, x) - B(a, n, x);
}[/code:1]
Ovaj se zadatak može riješiti i puno efikasnije (bez da se u svakom koraku funkcije [tt]A[/tt] vrti petlja za izračunavanje faktorijela; bez da se u svakom koraku funkcije [tt]B[/tt] vrti petlja za izračunavanje odgovarajuće potencije od 3). U ovom se krije onih dodatnih 5 bodova u zadatku, ali n zamarajte se time dok niste u mogućnosti riješiti zadatak bez da se zamarate efikasnošću programa.
Što god vam nije jasno, pitajte.
Ok, sad mi je jasno. Nije problem u zadatku, nego ste vas dvoje zbunjeni oko Hornerovog algoritma i onda krene pristup preko nekakve šablone, što naravno nikad nije dobro. Sažeto u stihove, "Tko nije drvo razumeo prvo,
pa tek onda sadio, taj nije ništa uradio... I, shvatit će, kad-tad, da ne zna šta je hlad."
Prema tome, da vidimo kako radi Hormerov algoritam.
Evo, npr. imamo polinom [tex]p(x) = 4x^3 + 7x^2 + 2x + 42[/tex] i netko nam zada neki [tex]\alpha\in\mathbb{R}[/tex] i traži da izračunamo [tex]p(\alpha)[/tex]. To možemo izračunati ovako:
Prvo krenemo s vodećim koeficijentom. To je 4.
Onda vrijednost iz prethodnog koraka pomnožimo s [tex]\alpha[/tex] i dodamo sljedeći koeficijent. Sada imamo [tex]4\alpha+7[/tex].
Onda vrijednost iz prethodnog koraka pomnožimo s [tex]\alpha[/tex] i dodamo sljedeći koeficijent. Sada imamo [tex](4\alpha+7)\alpha + 2 = 4\alpha^2 + 7\alpha + 2[/tex].
Onda vrijednost iz prethodnog koraka pomnožimo s [tex]\alpha[/tex] i dodamo sljedeći koeficijent. Sada imamo [tex](4\alpha^2 + \alpha + 2)\alpha + 42 = 4\alpha^3 + 7\alpha^2 + 2\alpha + 42[/tex].
Sada kad smo iskoristili sve koeficijente, znamo da je traženi rezultat [tex]p(\alpha) = 4\alpha^3 + 7\alpha^2 + 2\alpha + 42[/tex].
Da bude još jasnije, pogledajmo kako se računa za neki konkretni [tex]\alpha[/tex]. Izračunajmo npr. p(2).
Prvo krenemo s vodećim koeficijentom. To je 4.
Onda vrijednost iz prethodnog koraka pomnožimo s 2 i dodamo sljedeći koeficijent. Sada imamo 4 * 2+7 = 21.
Onda vrijednost iz prethodnog koraka pomnožimo s 2 i dodamo sljedeći koeficijent. Sada imamo 21 * 2 + 7 = 49.
Onda vrijednost iz prethodnog koraka pomnožimo s 2 i dodamo sljedeći koeficijent. Sada imamo 49 * 2 + 42 = 140.
Sada kad smo iskoristili sve koeficijente, znamo da je traženi rezultat p(2) = 140.
Nadam se da je sada jasno kako radi i zašto funkcionira Hornerov algoritam. Ako nije, please pitajte za daljna pojašnjenja.
Ajmo sada na zadatak iz originalnog posta. Zadatak traži da napišemo funkciju koja će računati vrijednost od [tex]P_n(x) = \sum\limits_{k=0}^{n}\left(a_{2k}(2k+1)! - a_{2(n-k)+1}3^k\right)x^k[/tex] u proizvoljno određenoj točki, pri čemu su [tex]a_0,a_1,\ldots,a_{2n+1}[/tex] unaprijed zadani.
Kad malo pojednostavnimo gornji izraz vidimo da je [tex]P_n(x) = A_n(x) - B_n(x)[/tex], pri čemu je [tex]A_n(x) = \sum\limits_{k=0}^{n}a_{2k}(2k+1)!x^k[/tex], a [tex]B_n(x) = \sum\limits_{k=0}^{n}a_{2(n-k)+1}3^kx^k[/tex].
Sada možemo napisati traženu funkciju.
| Kod: | /* Prvo dvije pomocne funkcije.
* Racunamo u double-ovima, jer je to tip u kojem se trazi rezultat u zadatku.
*/
/* Funkcija koja racuna 3^n. Funkcija pretpostavlja da je n >= 0. */
double potencija_od_3(int n) {
double rezutat = 1;
for( ; n > 0; --n) rezultat = rezultat * 3;
return rezultat;
}
/* Funkcija koja racuna n!. Funkcija pretpostavlja da je n >= 0. */
double faktorijel(int n) {
double rezultat = 1;
int i;
for (i = 1; i <= n; ++i) rezultat = rezultat * i;
return rezlutat;
}
/* Hornerovim algoritmom razunamo vrijednost polinoma A_n u tocki x.
Funkcija pretpostavlja da niz a sadrzi unaprijed zadane vrijednosti za a_0, a_1, ..., a_{2n+1} */
double A(double a[], int n, double x) {
int k;
double rezultat = a[2 * n] * faktorijel(2 * n + 1); /* Krenemo s vodecim koeficijentom. */
for(k = n -1; k >= 0; --k) {
double koeficijent = a[2 * k] * faktorijel(2 * k + 1); /* Koeficijent koji je sada na redu. */
rezultat = rezultat * x + koeficijent; /* Vrijednost iz prethodnog koraka pomnozimo s x i dodamo koeficijent. */
}
return rezultat; /* Na kraju vratimo izracunatu vrijednost. */
}
/* Hornerovim algoritmom razunamo vrijednost polinoma B_n u tocki x.
Funkcija pretpostavlja da niz a sadrzi unaprijed zadane vrijednosti za a_0, a_1, ..., a_{2n+1} */
double B(double a[], int n, double x) {
int k;
double rezultat = a[1] * potencija_od_3(n); /* Krenemo s vodecim koeficijentom. */
for(k = n -1; k >= 0; --k) {
double koeficijent = a[2 * (n - k)] * potencija_od_3(k); /* Koeficijent koji je sada na redu. */
rezultat = rezultat * x + koeficijent; /* Vrijednost iz prethodnog koraka pomnozimo s x i dodamo koeficijent. */
}
return rezultat; /* Na kraju vratimo izracunatu vrijednost. */
}
/* Konacno mozemo napisati funkciju koja se trazi u zadatku.
Funkcija pretpostavlja da niz a sadrzi unaprijed zadane vrijednosti za a_0, a_1, ..., a_{2n+1} */
double P(double a[], int n, double x) {
return A(a, n, x) - B(a, n, x);
} |
Ovaj se zadatak može riješiti i puno efikasnije (bez da se u svakom koraku funkcije A vrti petlja za izračunavanje faktorijela; bez da se u svakom koraku funkcije B vrti petlja za izračunavanje odgovarajuće potencije od 3). U ovom se krije onih dodatnih 5 bodova u zadatku, ali n zamarajte se time dok niste u mogućnosti riješiti zadatak bez da se zamarate efikasnošću programa.
Što god vam nije jasno, pitajte.
_________________
Extraordinary claims require extraordinary evidence. – Carl Sagan
|
|
| [Vrh] |
|
krilo
Forumaš(ica)
Pridružen/a: 01. 11. 2016. (14:45:48)
Postovi: (4E)16
Spol:
|
| Postano: 23:49 pet, 10. 2. 2017 Naslov: |
|
|
|
[quote] nego ste vas dvoje zbunjeni oko Hornerovog algoritma[/quote] Blago rečeno :wacky:
Stihoklepstvo - prva liga.
[code:1]double rezultat = a[2 * n] * faktorijel(2 * n + 1); /* Krenemo s vodecim koeficijentom. */
for(k = n -1; k >= 0; --k) {
double koeficijent = a[2 * k] * faktorijel(2 * k + 1); /* Koeficijent koji je sada na redu. */
rezultat = rezultat * x + koeficijent;[/code:1]
Jel možemo mi i vodeći član staviti u petlju (počnemo od [tt]k=n[/tt], čisto opažanje)?
Ja sam mislila da tu treba biti samo jedna bućkuriš-funkcija koja bi iščarobirala oba polinoma... ali ima ovo tvoje i više nego smisla.
Meni je općenito malo [i]glupo[/i] računati faktorijele na "običan" način jer nam stalno govore da će uskoro taj broj postati prevelik, pa si odmah zacrtam u glavi da na takav način ne valja rješavati takve zadatke (after all, kaj imam od programa koji ne radi; ako neće raditi za sve, kak to može biti dobar program/dobro riješen zadatak? :nuts2: )
Onda ga, naravno, ne riješim. 8)
| Citat: | | nego ste vas dvoje zbunjeni oko Hornerovog algoritma |
Blago rečeno 
Stihoklepstvo - prva liga.
| Kod: | double rezultat = a[2 * n] * faktorijel(2 * n + 1); /* Krenemo s vodecim koeficijentom. */
for(k = n -1; k >= 0; --k) {
double koeficijent = a[2 * k] * faktorijel(2 * k + 1); /* Koeficijent koji je sada na redu. */
rezultat = rezultat * x + koeficijent; |
Jel možemo mi i vodeći član staviti u petlju (počnemo od k=n, čisto opažanje)?
Ja sam mislila da tu treba biti samo jedna bućkuriš-funkcija koja bi iščarobirala oba polinoma... ali ima ovo tvoje i više nego smisla.
Meni je općenito malo glupo računati faktorijele na "običan" način jer nam stalno govore da će uskoro taj broj postati prevelik, pa si odmah zacrtam u glavi da na takav način ne valja rješavati takve zadatke (after all, kaj imam od programa koji ne radi; ako neće raditi za sve, kak to može biti dobar program/dobro riješen zadatak?  )
Onda ga, naravno, ne riješim. 
|
|
| [Vrh] |
|
mdoko
Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol:
Lokacija: Heriot-Watt University, Edinburgh
|
| Postano: 0:27 sub, 11. 2. 2017 Naslov: |
|
|
|
[quote="krilo"]Stihoklepstvo - prva liga.[/quote]
Source: [url]https://www.youtube.com/watch?v=4e_YzraLFRI[/url]
[quote]Jel možemo mi i vodeći član staviti u petlju (počnemo od [tt]k=n[/tt], čisto opažanje)?[/quote]
Može. S kojom vrijednosti onda treba započeti račun?
[quote]Ja sam mislila da tu treba biti samo jedna bućkuriš-funkcija koja bi iščarobirala oba polinoma...[/quote]
Od čarobiranja nikad koristi.
[quote]Meni je općenito malo [i]glupo[/i] računati faktorijele na "običan" način jer nam stalno govore da će uskoro taj broj postati prevelik[/quote]
Taj će broj brzo postati prevelik bez obzira na koji način ga računaš. Uvijek računaš isti broj, pa ako nešto ne stane u npr. [tt]double[/tt], onda ne stane. Kako ga računaš ti neće pomoći.
[quote]after all, kaj imam od programa koji ne radi; ako neće raditi za sve, kak to može biti dobar program/dobro riješen zadatak?[/quote]
Na uvodnim kursevima programiranja poanta je u konstrukciji kvalitetnog algoritma. Kasnije ćeš razbijati glavu problemima tipa "koliko velike brojeve ja stvarno mogu prikazati i što ako mi treba veći?".
| krilo (napisa): | | Stihoklepstvo - prva liga. |
Source: https://www.youtube.com/watch?v=4e_YzraLFRI
| Citat: | | Jel možemo mi i vodeći član staviti u petlju (počnemo od k=n, čisto opažanje)? |
Može. S kojom vrijednosti onda treba započeti račun?
| Citat: | | Ja sam mislila da tu treba biti samo jedna bućkuriš-funkcija koja bi iščarobirala oba polinoma... |
Od čarobiranja nikad koristi.
| Citat: | | Meni je općenito malo glupo računati faktorijele na "običan" način jer nam stalno govore da će uskoro taj broj postati prevelik |
Taj će broj brzo postati prevelik bez obzira na koji način ga računaš. Uvijek računaš isti broj, pa ako nešto ne stane u npr. double, onda ne stane. Kako ga računaš ti neće pomoći.
| Citat: | | after all, kaj imam od programa koji ne radi; ako neće raditi za sve, kak to može biti dobar program/dobro riješen zadatak? |
Na uvodnim kursevima programiranja poanta je u konstrukciji kvalitetnog algoritma. Kasnije ćeš razbijati glavu problemima tipa "koliko velike brojeve ja stvarno mogu prikazati i što ako mi treba veći?".
_________________
Extraordinary claims require extraordinary evidence. – Carl Sagan
|
|
| [Vrh] |
|
krilo
Forumaš(ica)
Pridružen/a: 01. 11. 2016. (14:45:48)
Postovi: (4E)16
Spol:
|
|
| [Vrh] |
|
mdoko
Forumaš(ica)
Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol:
Lokacija: Heriot-Watt University, Edinburgh
|
|
| [Vrh] |
|
|
Hvala na trudu.