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 | 26930 (23505) | daisy22 |
| » | naloga - vesoljska postaja in astronavtOddelek: Šola | 1591 (1367) | Zero0ne |
| » | Tridimenzionalni fraktaliOddelek: Novice / Znanost in tehnologija | 5149 (4242) | urban99 |