Search
 
 
  Engleski
 
 
 
Open in this window (click to change)
Forum@DeGiorgi: Početna
Forum za podršku nastavi na PMF-MO
Login Registracija FAQ Smajlići Članstvo Pretražnik Forum@DeGiorgi: Početna

2.kolokvij pomoć (zadatak)
WWW:

Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 1. godine, preddiplomski studij Matematika -> Programiranje 1 i 2
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
PilotGrip
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 08. 02. 2017. (16:10:52)
Postovi: (7)16
Sarma = la pohva - posuda
= 0 - 0

PostPostano: 12:27 čet, 9. 2. 2017    Naslov: 2.kolokvij pomoć Citirajte i odgovorite

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! Smile

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]
Korisnički profil Pošaljite privatnu poruku
mdoko
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol: muško
Sarma = la pohva - posuda
199 = 237 - 38
Lokacija: Heriot-Watt University, Edinburgh

PostPostano: 17:35 čet, 9. 2. 2017    Naslov: Re: 2.kolokvij pomoć Citirajte i odgovorite

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]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
krilo
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 01. 11. 2016. (14:45:48)
Postovi: (4E)16
Spol: žensko
Sarma = la pohva - posuda
= 5 - 0

PostPostano: 18:12 čet, 9. 2. 2017    Naslov: Citirajte i odgovorite

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. Smile )


[Vrh]
Korisnički profil Pošaljite privatnu poruku
PilotGrip
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 08. 02. 2017. (16:10:52)
Postovi: (7)16
Sarma = la pohva - posuda
= 0 - 0

PostPostano: 21:00 čet, 9. 2. 2017    Naslov: Re: 2.kolokvij pomoć Citirajte i odgovorite

[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]
Korisnički profil Pošaljite privatnu poruku
mdoko
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol: muško
Sarma = la pohva - posuda
199 = 237 - 38
Lokacija: Heriot-Watt University, Edinburgh

PostPostano: 0:20 pet, 10. 2. 2017    Naslov: Citirajte i odgovorite

[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? Kotacici rade 100 na sat

Š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. Ja to stvarno ne znam



_________________
Extraordinary claims require extraordinary evidence. – Carl Sagan
[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
PilotGrip
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 08. 02. 2017. (16:10:52)
Postovi: (7)16
Sarma = la pohva - posuda
= 0 - 0

PostPostano: 8:36 pet, 10. 2. 2017    Naslov: Citirajte i odgovorite

Ma postoji neka formula u skripti preko koje kao rastavljamo polinom za Hornerov. No dobro nisam ju ni shvatio pa nema veze. Bi li mogao rjesiti do kraja onda zadatak da probam shvatiti?
Ma postoji neka formula u skripti preko koje kao rastavljamo polinom za Hornerov. No dobro nisam ju ni shvatio pa nema veze. Bi li mogao rjesiti do kraja onda zadatak da probam shvatiti?


[Vrh]
Korisnički profil Pošaljite privatnu poruku
krilo
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 01. 11. 2016. (14:45:48)
Postovi: (4E)16
Spol: žensko
Sarma = la pohva - posuda
= 5 - 0

PostPostano: 8:44 pet, 10. 2. 2017    Naslov: Citirajte i odgovorite

Š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 Embarassed ) 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? Ja to stvarno ne znam )


[Vrh]
Korisnički profil Pošaljite privatnu poruku
mdoko
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol: muško
Sarma = la pohva - posuda
199 = 237 - 38
Lokacija: Heriot-Watt University, Edinburgh

PostPostano: 15:53 pet, 10. 2. 2017    Naslov: Citirajte i odgovorite

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]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
krilo
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 01. 11. 2016. (14:45:48)
Postovi: (4E)16
Spol: žensko
Sarma = la pohva - posuda
= 5 - 0

PostPostano: 23:49 pet, 10. 2. 2017    Naslov: Citirajte i odgovorite

[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 Tup, tup, tup,...
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? Nuts )
Onda ga, naravno, ne riješim. Cool


[Vrh]
Korisnički profil Pošaljite privatnu poruku
mdoko
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol: muško
Sarma = la pohva - posuda
199 = 237 - 38
Lokacija: Heriot-Watt University, Edinburgh

PostPostano: 0:27 sub, 11. 2. 2017    Naslov: Citirajte i odgovorite

[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]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
krilo
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 01. 11. 2016. (14:45:48)
Postovi: (4E)16
Spol: žensko
Sarma = la pohva - posuda
= 5 - 0

PostPostano: 0:47 sub, 11. 2. 2017    Naslov: Citirajte i odgovorite

[quote]S kojom vrijednosti onda treba započeti račun?[/quote]
Pretpostavljam s nulom.
[code:1]double rezultat=0;
for(k = n; k >= 0; --k) {
rezultat = rezultat * x + a[2 * k] * faktorijel(2 * k + 1);
...[/code:1]

[quote]ako nešto ne stane u npr. double, onda ne stane. Kako ga računaš ti neće pomoći. [/quote] Ovo su već više životne mudrosti :sillyroll: :sunny: Hvala na trudu.
Citat:
S kojom vrijednosti onda treba započeti račun?

Pretpostavljam s nulom.
Kod:
double rezultat=0;
for(k = n; k >= 0; --k) {
     rezultat = rezultat * x + a[2 * k] * faktorijel(2 * k + 1);
...


Citat:
ako nešto ne stane u npr. double, onda ne stane. Kako ga računaš ti neće pomoći.
Ovo su već više životne mudrosti silly + roll Sunny Hvala na trudu.


[Vrh]
Korisnički profil Pošaljite privatnu poruku
mdoko
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol: muško
Sarma = la pohva - posuda
199 = 237 - 38
Lokacija: Heriot-Watt University, Edinburgh

PostPostano: 1:05 sub, 11. 2. 2017    Naslov: Citirajte i odgovorite

[quote="krilo"][quote]S kojom vrijednosti onda treba započeti račun?[/quote]
Pretpostavljam s nulom.
[code:1]double rezultat=0;
for(k = n; k >= 0; --k) {
rezultat = rezultat * x + a[2 * k] * faktorijel(2 * k + 1);
...[/code:1][/quote]
Točno tako.
krilo (napisa):
Citat:
S kojom vrijednosti onda treba započeti račun?

Pretpostavljam s nulom.
Kod:
double rezultat=0;
for(k = n; k >= 0; --k) {
     rezultat = rezultat * x + a[2 * k] * faktorijel(2 * k + 1);
...

Točno tako.



_________________
Extraordinary claims require extraordinary evidence. – Carl Sagan
[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
Prethodni postovi:   
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 1. godine, preddiplomski studij Matematika -> Programiranje 1 i 2 Vremenska zona: GMT + 01:00.
Stranica 1 / 1.

 
Forum(o)Bir:  
Ne možete otvarati nove teme.
Ne možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You cannot attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2002 phpBB Group
Theme created by Vjacheslav Trushkin
HR (Cro) by Ančica Sečan