Fibonacci recursion demo PY. ( GIF )

[Webz]

https://blog.penjee.com/wp-content/uploads/2015/06/fibonacci-recursion-demonstration-animation-python.gif

Edited April 5, 2016 by Webz

[Byte-ul]

14 minutes ago, Webz said:

https://blog.penjee.com/wp-content/uploads/2015/06/fibonacci-recursion-demonstration-animation-python.gif

Cum crezi ca e mai bine sa implementezi acest algoritm? Recursiv sau iterativ?

[sharkyz]

Pentru performanta probabil iterativ , in unele cazuri un algoritm recursiv este convertit in format iterativ de compiler.

Edited April 5, 2016 by sharkyz

[Webz]

1 hour ago, Byte-ul said:

Cum crezi ca e mai bine sa implementezi acest algoritm? Recursiv sau iterativ?

 

 

Nu stiu d-astea man , scuze.

[tjt]

4 hours ago, Byte-ul said:

Cum crezi ca e mai bine sa implementezi acest algoritm? Recursiv sau iterativ?

Recursiv, dar utilizezi un cache ca sa salvezi rezultatele.

Astfel la o apelare ulterioara timpul de executie scade foarte mult xD.

[hades]

D.p.d.v al timpului de rulare, asta ar fii cea mai buna metoda de a calcula o serie fibonnaci in python:

def moloz(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

 

[sharkyz]

 

def fib(n):
    v1, v2, v3 = 1, 1, 0
    for rec in bin(n)[3:]:
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec=='1':    v1, v2, v3 = v1+v2, v1, v2
    return v2

 

Edited April 5, 2016 by sharkyz

[Webz]

On 4/5/2016 at 2:11 AM, sharkyz said:

 

def fib(n):
    v1, v2, v3 = 1, 1, 0
    for rec in bin(n)[3:]:
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec=='1':    v1, v2, v3 = v1+v2, v1, v2
    return v2

 

 

 

Asta-i metoda tricky ?

[sharkyz]

@Webz Il aveam in gists. Este unul dintre cele mai performante. Incearca cu un 1.000.000 la metoda simpla si metoda tricky.

 

Pe laptopul meu differenta este:

fib       0.0944411754608 sec

moloz  13.828804969800 sec

Edited April 11, 2016 by sharkyz