Forum » Šola » Fibonacci in čas računanja
Fibonacci in čas računanja
pikachu004 ::
Pri programiranju smo meli za nalogo narditi program ki bi računal fibonaccijeva števila
in potem v konzoli preverit čas njihovega računanja. preverit smo mogli za:
10 = 1,709s
20 = 1,787s
30 = 2,010s
40 = 5,898s
in potem ugotoviti kolkiko časa bi potrebovalo za št. 100. Vendar se po št. 40 to začne ful zavlačevat.
recimo za: 41 = 8,036s; 42 = 12,025s; 43 = 17,273s; 44 = 26,025s; 45 = 41,356s... Za 53 je potreboval že več kot pol ure.
Zanima me, če kdo ve formulo za izračun časa za število 100? Menda naj bi potreboval ogromno let.
in potem v konzoli preverit čas njihovega računanja. preverit smo mogli za:
10 = 1,709s
20 = 1,787s
30 = 2,010s
40 = 5,898s
in potem ugotoviti kolkiko časa bi potrebovalo za št. 100. Vendar se po št. 40 to začne ful zavlačevat.
recimo za: 41 = 8,036s; 42 = 12,025s; 43 = 17,273s; 44 = 26,025s; 45 = 41,356s... Za 53 je potreboval že več kot pol ure.
Zanima me, če kdo ve formulo za izračun časa za število 100? Menda naj bi potreboval ogromno let.
Primoz ::
Na kakšen način pa to računaš?
V praksi lahko za števila s katerimi lahko normalno operiraš (brez posebnih knjižnic) zadevo vedno izračunaš v konstantnem času.
Fibonacci number - Wikipedia, the free encyclopedia
$F_n=((1+sqrt(5))^n-(1-sqrt(5))^n)/(2^nsqrt(5))$ (napaka se odpravlja)
V praksi lahko za števila s katerimi lahko normalno operiraš (brez posebnih knjižnic) zadevo vedno izračunaš v konstantnem času.
Fibonacci number - Wikipedia, the free encyclopedia
$F_n=((1+sqrt(5))^n-(1-sqrt(5))^n)/(2^nsqrt(5))$ (napaka se odpravlja)
There can be no real freedom without the freedom to fail.
Zgodovina sprememb…
- spremenil: Primoz ()
JanK ::
Nisem mogel verjeti, da je zadeva tako pozresna, pa sem sam probal. Ce racunas iterativno (linearna zahtevnost), gre kot blisk in to vse do overflowa pri $F_{1477}$ (napaka se odpravlja). Ce pa racunas rekurzivno je zadeva res pocasna - zahtevnost rekurzivnega racunanja je eksponentna.
"Think about how stupid the average person is,
then realize that 50% are stupider than that"
-George Carlin
then realize that 50% are stupider than that"
-George Carlin
3p ::
pikachu: ti imaš zgleda šolsko rekurzivno implementacijo, ki za izracun razvije binarno drevo rekurzivnih klicev in je izracunov priblizno 2^n, torej zanj velja O(2^n).
Nerekurzivni algoritem ima zahtevnos O(n) in bo fib(100) izračunal takoj.
Nerekurzivni algoritem ima zahtevnos O(n) in bo fib(100) izračunal takoj.
pikachu004 ::
amm... ja smo delali z rekurzijo.
in bi morali izračunat v kolikem času bi izračunal št. 100 rekurzivno.
naj bi prišlo več 100 miljard let
in bi morali izračunat v kolikem času bi izračunal št. 100 rekurzivno.
naj bi prišlo več 100 miljard let
Pegaz ::
Rekurzivno racunat je nesmisel, ce racunas Fibonaccija. V zanki shranjuj v spremenljivki dve stevili, ki jih imas. Recimo, da imas 3 in 5. Prvo stevilo prepisi z drugim, drugemu pa dodaj prvega.
imagodei ::
Človek dela nalogo. Morda naloga zahteva rekurzijo in ne sme narediti drugače.
- Hoc est qui sumus -
Pegaz ::
Morda ucitelj upa, da se bo kdo spomnil in naredil nalogo se na kaksen drugacen nacin, kot z uporabo rekurzivne funkcije.
Samo zdaj se ne bo "spomnil", saj smo mu ze mi povedali.
Samo zdaj se ne bo "spomnil", saj smo mu ze mi povedali.
Vredno ogleda ...
Tema | Ogledi | Zadnje sporočilo | |
---|---|---|---|
Tema | Ogledi | Zadnje sporočilo | |
» | Python - naloga z računanjemOddelek: Programiranje | 2094 (1571) | ktka |
» | Matematika - FMF (strani: 1 2 )Oddelek: Šola | 10431 (8164) | sherman |
» | Matematika - pomoč (strani: 1 2 3 )Oddelek: Šola | 26926 (23501) | daisy22 |
» | naloga - vesoljska postaja in astronavtOddelek: Šola | 1589 (1365) | Zero0ne |
» | Tridimenzionalni fraktaliOddelek: Novice / Znanost in tehnologija | 5149 (4242) | urban99 |