Jump to content
Sign in to follow this  
Webz

Fibonacci recursion demo PY. ( GIF )

Recommended Posts

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

Edited by sharkyz

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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

 

  • Upvote 2

Share this post


Link to post
Share on other sites

 

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 by sharkyz

Share this post


Link to post
Share on other sites
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 ? :))

Share this post


Link to post
Share on other sites

@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 by sharkyz
  • Upvote 1

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this  

×
×
  • Create New...