van.teme.1mikij,
Bravo...
Molim vas ucutite!
Pozdrav Miki
van.teme.2kvelkovski,
>> Jeste da nam je Norton Guide cesto jedini izvor INFS, ali, dok u njemu se
^^^^
Ako je INFS = INFORMATIONS onda je pogresno, zbog toga sto rec
information u engleskom jeziku nema mnozinu (kao furniture, advice...).
Pozdrav, Kire
van.teme.3kaza,
Ne znam da li ovo pripada ovdje ali negdje moram da ispricam ovu
pricu.
Vecina vjerovatno zna za Fibonacijev niz. Ako se ne varam bilo je i
nekih pitalicna slicnu temu.
Elem Fibonacijev niz se uzima obicno za primjer koristenja rekurzije
pa to otprilike ovako izgleda:
double fib(double x)
{
if(x<2) return(1);
return(fib(x-1)+fib(x-2));
}
medjutim ova funkcija lijepo radi za male brojeve ali ako hocemo
izracunati recimo 100-ti ili nedaj boze 200-ti clan eto belaja. Moze
ali je to dobro pred godisnji odmor sve pripremiti i kada se vratimo
gle cuda, racunar izracunao.
Ja sam kopao po matematickim alatima iz teske artiljerije i provlacio
Fibonacijev niz kroz razne transformacije da bi dobio jednu veoma
glupu formulu (glupu samo na prvi pogled) koja rjesava pronalazenje
clana fibonacijevog niza veoma brzo, da ne kazem trenutno. A formula
u C sintaksi glasi:
double p=sqrt(5);┐Ě▀
fi=(pow((1+p),(i+1))-pow((1-p),(i+1)))/(p*pow(2,(i+1)));
i ova formula izracunava i-ti clan niza, a nije rekurzivna.
Glupo izgleda ali radi.
Sada mene zanima da li neko poznaje ima li negdje u matematickim
literaturama da se spominje ova formula ili sam je ja otkrio.
Ako ne postoji onda, ako se slazete, da je nazovemo Kaziceva formula
za izracunavanje Fibonacijevog niza.
Uvjek sam bio ljubomoran na raju po kojoj se daju imena formula.
Pozdrav KAZA
van.teme.4madamov,
Evo malo teorije iz matematike o nalaženju formule za izračunavanje n-tog
člana niza datog rekurentno preko svoja dva prethodna člana. Tj., neka je dat
niz rekurentno formulom:
Xn = p*Xn-1 + q*Xn-2
i sa početnim vrednostima:
X0 = a, X1 = b
Nađimo korene kvadratne jednačine: t^2 - p*t - q = 0.
Označimo alfa=t1, beta=t2, ukoliko je t1<>t2. Tada je formula za n-ti
član niza:
Xn = A*alfa^n + B*beta^n (1)
Označimo sa alfa=t1=t2 ukoliko je t1=t2. Formula glasi:
Xn = A*alfa^n + n*B*alfa^n (2)
Koeficijente A i B nalazimo rešavanjem sistema jednačina sa dve nepoznate
pomoću početnih vrednosti, tj. za prvi slučaj:
a = A + B
b = alfa*A + beta*B
a za drugi slučaj:
a = A
b = alfa*A + alfa*B
Formula za nalaženje n-tog člana niza je tada data sa (1) ili sa (2).
Na primeru Fibonačijevog niza to znači sledeće:
X0 = X1 = 1, Xn = Xn-1 + Xn-2 => p=q=1
pa kvadratna jednačina glasi: t^2 - t - 1 = 0 čiji su koreni:
alfa = t1 = (1+sqrt(5))/2
beta = t2 = (1-sqrt(5))/2
pa zamenom u sistem (1), jer je t1<>t2, dobijamo:
A = (beta-1)/(beta-alfa) B = (1-alfa)/(beta-alfa)
Lako se pokazuje:
beta-1 = -alfa, 1-alfa = beta i beta-alfa= -sqrt(5)
tj.
A = alfa/sqrt(5) B = -beta/sqrt(5)
pa je formula za n-ti član Fibonačijevog niza:
Xn = ( alfa^(n+1) - beta^(n+1) ) / sqrt(5)
tj. u punom obliku:
Xn = ( (1+sqrt(5))^(n+1) - (1-sqrt(5))^(n+1) ) / sqrt(5)*2^(n+1)
Kao što vidiš, dobijena formula je identična tvojoj formuli i nije ni
najmanje glupa.
van.teme.5kaza,
Hvala na iscrpnom odgovoru, nisam ovo ranije vidjeo a ja sam do
nesretne formule dosao preko Z transformacije.
Uz to izvini sto sam formulu nazvao glupom cini se kao da te je to
naljutilo ali stvarno glupo izgleda kada formula u kojoj figurisu
clanovi poput korjen iz 5, vraca rezultat koji je cjeli broj.
Pozdrav KAZA
van.teme.6nenadp,
<<Elem Fibonacijev niz se uzima obicno za primjer koristenja rekurzije
<<pa to otprilike ovako izgleda:
Ova me je prica podsetila na predavanje koje je drzo
profesor Jozo Dujmovic. Kada je objasnjavao rekurzivno
definisane funkcije spomenuo je da se izracunavanje
Fibonaccijevih brojeva rekurzijom cesto navodi kao primer
primene rekurzivnog poziva funkcije a onda nam pokazo kolko
je to lose, evo par crtica:
Naprimer , za racunar VAX-11/750 i VAX-11 Pascal V1.3-116
moze se eksperimentalno pokazati da vazi:
n
T(n)=0.088 * g [msec] ; g=1.618
gde je T(n) vreme rekurzivnog izracunavanja Fibonaccijevog
broja. Sto daje T(32)=7 minuta procesorskog vremena!!!
Radi poredjena na istoj masini vreme izvrsavanja nerekurzivnog
programa iznosi:
T(n)=0.0143*n+0.062 [msec]
odnosno T(32)=0.52 msec.
<< Xn = ( (1+sqrt(5))^(n+1) - (1-sqrt(5))^(n+1) ) / sqrt(5)*2^(n+1)
<< Kao sto vidis, dobijena formula je identicna tvojoj formuli i nije ni
<< najmanje glupa. [od madamov]
Potpuno se slazem da formula nije "glupa" i proizilazi iz
teorije diferencnih jednacina sto je MADAMOV lepo izveo i dokazao.
Samo ima tu jedan problem, ta jednacina nije pogodna za programiranje
zato sto treba izracunati SQRT(5) a to je ograniceno tacnoscu sa
kojom doticni racunar raspolaze. Dakle brzo ali za velike brojeve
netacno.
Pozdrav ,Nenad
P.S. Po onoj narodnoj nemoz imat i jare i pare :))))))))
van.teme.7madamov,
Ma nisam se ja uopšte naljutio. Samo sam na kraju poruke konstatovao da
se određenim, teorijski i matematički zasnovanim, metodom dolazi do, formuli
koju si ti dobio, ekvivalentne formule i da takve formule ne mogu biti "glupa".
van.teme.8madamov,
Potpuno si u pravu. Međutim, pored tačnosti rezultata ( mada se kao
rezultat formule dobija ceo broj ) tu je i dalje problem brzine ( iako bi
brzina trebalo da bude veća primenom ove formule od brzine rešenja primenom
rekurzivnog metoda ), kao i problem povezivanja floating point biblioteke u
slučaju kad program koji koristi ovu formulu nigde na drugom mestu nema potrebu
za floating point funkcijama i brojevima osim kad izračunava vrednost formule
za konkretno n. Sređivanjem i transformisanjem formule bi se, verovatno, mogao
izbaciti sqrt(5), ali bi se u tom slučaju dobilo nešto vrlo slično klasičnom
rešenju pomoću petlje. A tada je na samom programeru da izvaga šta je brže i
šta troši manje memorije, pa da donese odluku šta da koristi. To se svodi na
tvoj P.S., a to je da ne može i jare i pare, ili modernija varijanta za ženski
svet: ne možeš se j*****, a da ti ne uđe. B)
van.teme.9dveselinovic,
Goddamn, Paya the Telecomms Man!
32XDVV
van.teme.12maleksic,
>> Pozdrav,
>> Bulajaja
********
:))))))))))))
Jeli, a zasto se ti lazno introduciras to vini?
van.teme.14kvelkovski,
>> Da li neko ima programcic koji na EGA karti postavlja nasa slova
>> po YUSCII rasporedu. Imao sam ovo i obrisao jer mi nije trebalo :((
Ja sam danas nesto nasao, a ti vidi da li vredi.
Kupe
yuega.zipvan.teme.15kvelkovski,
Ko mi maznu poruku 27.24 !@#$%^&**()(*&%#!
Kupe
van.teme.16alexa,
> Ko mi maznu poruku 27.24 !Ž#$%Č&**()(*&%#!
???
van.teme.17dejanr,
>> Ko mi maznu poruku 27.24 !@#$%^&**()(*&%#!
Niko je nije "maznuo", premeštena je u temu razno.
U van.teme ne treba VI da šaljete poruke, mi ih ponekad premestimo
tamo ako neko totalno promaši konferenciju i/ili temu a poruka ipak
nije za brisanje. Možda bi tema van.teme trebala da bude read only.