文章专题 AI工具学习下载问答源码最近更新

PHP

问个有关python的斐波那契的问题

黄舟 2017-04-17 16:39:37

[Python讨论组]

332

def fib1(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        return fib1(n-1) + fib1(n-2)
 
 print fib1(7)

问题是：为什么输入7算出来的是13而不是11，(n-1)+(n-2)不是等于（7-1）+（7-2）吗？13是怎么来的
贴主说fib1的慢，就是因为每次都要计算前面已经算过的项目.这里将上述算法进行稍微改进。怎么看出这段程序会计算已经算过的项目？

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

据说这段会比上面的快，特别是n很大的时候，这段会快很多。为什么这段会快呢？大神解答下

n = int(raw_input())
    if n==0:
        print '0'
    elif n==1:
        print '1'
    else:
        m = (n-1) + (n-2)
    print m

这段和第一段有哪里不一样，为什么这段计算结果不一样

黄舟

人生最曼妙的风景，竟是内心的淡定与从容！

全部回复(3)

ringa_lee2017-04-17 16:41:37 3楼

第一第三问不予回答，自行去恶补 python 语法

第二问：

因为前者是递归调用，调用栈如下：

fib(7) --> fib(6) --> fib(5) --> fib(4) --> fib(3) --> fib(2) --> fib(1) --> fib(2) --> fib(3) --> fib(4) --> fib(5) --> fib(6) --> fib(7)

明眼人都看出有多慢。更何况没有尾递归优化。

而后者，只是从1循环到7，计算次数少了很多。

赞 +0

添加回复

怪我咯2017-04-17 16:41:37 2楼

题主你太逗了，这个是递归

fib1(7) 不是（7-1）+（7-2）

  fib1(7)
= fib1(6) + fib1(5)
= fib1(5) + fib1(4) + fib1(4) + fib1(3)
= fib1(4) + fib1(3) + fib1(3) + fib1(2) + fib1(2) + fib1(1)
= ...

赞 +0

添加回复

大家讲道理2017-04-17 16:41:37 1楼

第一段

def fib1(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        return fib1(n-1) + fib1(n-2) #返回 调用函数
 
 print fib1(7)

这段函数使用递归进行斐波那契的求值，返回 fib1(6) + fib1(5) 那 fib1(6)和 fib1(5)的值会继续反复调用函数本身进行计算，直到求出结果为止。而你后面的

n = int(raw_input())
    if n==0:
        print '0'
    elif n==1:
        print '1'
    else:
        m = (n-1) + (n-2)
    print m

其中区别，自然不用多说了吧，既然说到了递归，第二段代码则是使用了循环，该问题的效率问题可见上面回答，但递归和循环的效率问题不敢妄自回答，自行 Google。

赞 +0

添加回复

专题推荐

更多>

热门话题

热门教程

更多>