2.kolokvij pomoć
Select messages from
# through # FAQ
[/[Print]\]

Forum@DeGiorgi -> Programiranje 1 i 2

#1: 2.kolokvij pomoć Autor/ica: PilotGrip PostPostano: 12:27 čet, 9. 2. 2017
    —
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.

#2: Re: 2.kolokvij pomoć Autor/ica: mdokoLokacija: Heriot-Watt University, Edinburgh PostPostano: 17:35 čet, 9. 2. 2017
    —
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.

#3:  Autor/ica: krilo PostPostano: 18:12 čet, 9. 2. 2017
    —
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 )

#4: Re: 2.kolokvij pomoć Autor/ica: PilotGrip PostPostano: 21:00 čet, 9. 2. 2017
    —
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!

#5:  Autor/ica: mdokoLokacija: Heriot-Watt University, Edinburgh PostPostano: 0:20 pet, 10. 2. 2017
    —
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

#6:  Autor/ica: PilotGrip PostPostano: 8:36 pet, 10. 2. 2017
    —
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?

#7:  Autor/ica: krilo PostPostano: 8:44 pet, 10. 2. 2017
    —
Š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 )

#8:  Autor/ica: mdokoLokacija: Heriot-Watt University, Edinburgh PostPostano: 15:53 pet, 10. 2. 2017
    —
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.

#9:  Autor/ica: krilo PostPostano: 23:49 pet, 10. 2. 2017
    —
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

#10:  Autor/ica: mdokoLokacija: Heriot-Watt University, Edinburgh PostPostano: 0:27 sub, 11. 2. 2017
    —
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?".

#11:  Autor/ica: krilo PostPostano: 0:47 sub, 11. 2. 2017
    —
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.

#12:  Autor/ica: mdokoLokacija: Heriot-Watt University, Edinburgh PostPostano: 1:05 sub, 11. 2. 2017
    —
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.



Forum@DeGiorgi -> Programiranje 1 i 2


output generated using printer-friendly topic mod. Vremenska zona: GMT + 01:00.

Stranica 1 / 1.

Powered by phpBB © 2001,2002 phpBB Group
Theme created by Vjacheslav Trushkin