python实现斐波拉契数列的看法

最近由于有算法的课程，自己动手用 python写了几个小的算法，今天先说下第一个Fibonacci（斐波拉契数列）。

废话不多说先给大家看源码。

import timeit
start = timeit.default_timer()
#查找溢出大小
def fib():
    n, a, b, c = 0, 1, 1, 2
    while a < 2147483647:
           (a,b) = (b,c)
           (c,n) = (a+b,n+1)
           print(n)
    print("溢出大小为："+ str(n))
    return "done"
print(fib())
end = timeit.default_timer()
print("消耗时间为： " + str(end-start))
#溢出大小的时间
start1 = timeit.default_timer()
def findfibs(max):
    q,w,e = 1,1,2
    m = 0
    while m < max - 1:
        (q,w) = (w,e)
        (e,m) = (q+w,m+1)
        print(q)
    return "done"
print(findfibs(46))
end1 = timeit.default_timer()
print("溢出时间为：" + str(end1 - start1))
#递归求斐波数
def maxfib(l):
    if l == 0 :
        return l
    elif l <= 2:
        return 1
    return maxfib(l-1) + maxfib(l-2)

print("最大fibo数为：" + str(maxfib(10)))

先说第一个fib()这个函数，应该很容易看出来它的功能，计算当第几个数的时候会发生溢出，并且计算时间。

先说时间吧，有些朋友不太会用一些库，http://www.jb51.net/article/108778.htm推荐这个大神写的。

程序执行时间=cpu时间 + io时间 + 休眠或者等待时间。这句话很重要，虽然这个程序运行时间很短，对于io时间或休眠时间需求很短或者不需要，但是程序要是考虑精确时间的话，还是有细微的差距的。后面我还会写一个线程计时的程序给大家看。

说完了时间，其实我在刚开始写的时候是有bug的，bug在那里呢？

a < 2147483647:

python是不会溢出的：

在python2.7中，表示整数的有int和long两个类型。int类型和C++的int类似，都是一个固定位数的数；long则是一个理论上可以存储无限大数的数据类型。当你的数大到可能溢出时，python就会机智的帮你转换成long，这样就避免了溢出。而python3之后整数只有一个可以放任意大数的int了。可是无论哪种，都是采用了特殊的方法实现了不会溢出的大整数。

作者：知乎用户
链接：https://www.zhihu.com/question/28232557/answer/40535953
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

一开始我一门心思的想去看看这个数到底多大，一个搞cpp的同学，不到一秒就知道了。。。。

我还要等好久。。。

后来越等越纳闷，数列都好几百万了，

后来查了一下，才发现这个。。。

细心的人会发现为什么是2147483647

这是是我给他设的边界

32位操作系统中的整数最大值。

下面说第二个

第二个函数是求到第46个的时候需要多少时间，其余不多解释。

下面说第三个

用递归求fibo数，递归是一个很普通的。

我有一些学弟很不理解递归，在我的理解来看就是：

自己解决自己

这句话怎么理解呢

我看了下知乎上对递归的理解

知乎真的是人才的海洋

递归的话，就一句话，递归太深，堆栈溢出，每一次解决这个问题就要有一个堆栈，就像我在我的程序中写到的，如果你要解决3，就要把这个3拆成1.2，继续调用这个方法。

才疏学浅，希望指点

python实现斐波拉契数列的看法

相关推荐