专栏首页Python小屋三种Fibonacci数列第n项计算方法及其优劣分析

三种Fibonacci数列第n项计算方法及其优劣分析

感谢国防科技大学刘万伟老师和中国传媒大学胡凤国两位老师提供的思路,文章作者不能超过8个字符,我的名字就写个姓吧,名字不写了^_^。另外,除了本文讨论的三种方法,之前的文章中还讨论了另外几种方法,详见相关阅读第一篇。

def fibo4(n):

'''递推法

适用于任意大小的n

使用生成器函数

速度快,无误差'''

def nested():

a, b = 1, 1

while True:

yield a

a, b = b, a+b

# 创建生成器对象

temp = nested()

# 获取前n-1项

for i in range(n-1):

next(temp)

# 返回第n项

return next(temp)

def fibo5(n):

'''通项公式法,速度也不错

涉及实数运算,会有误差,

n越大,误差越大,

n大到一定程度会崩溃'''

z = 5**0.5

u = (1+z) / 2

v = (1-z) / 2

return int((u**n - v**n)/(u-v))

from sympy import sqrt, Symbol, simplify

def fibo6(n):

'''通项公式法,速度快

通过符号计算库的简化策略,

弥补了实数运算引入的误差'''

c1 = ((1+sqrt(5))/2)

c2 = ((1-sqrt(5))/2)

c3 = sqrt(5)

k = Symbol("k")

f = (c1**k-c2**k)/c3

return simplify(f.subs(k, n))

n = 50

print(fibo4(n))

print(fibo5(n))

print(fibo6(n))

当n=50时,运行结果为:

12586269025

12586269025

12586269025

当n=80时,运行结果如下,注意开始fibo5有误差了:

23416728348467685

23416728348467744

23416728348467685

当n=200时,运行结果如下,误差越来越大了:

280571172992510140037611932413038677189525

280571172992512015699912586503521287798784

280571172992510140037611932413038677189525

当n=8000时,fibo4和fibo6仍然正常工作,而fibo5在n=1500左右时就已经无法工作了,代码崩溃。

Traceback (most recent call last):

File "C:/Python36/fibonacci.py", line 43, in <module>

print(fibo5(n))

File "C:/Python36/fibonacci.py", line 27, in fibo5

return int((u**n - v**n)/(u-v))

OverflowError: (34, 'Result too large')

本文分享自微信公众号 - Python小屋(Python_xiaowu),作者:刘万伟,胡凤国,董

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-10-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python计算整数阶乘的几种方法比较

    问题本身很简单,主要是通过这个小问题来演示Python的一些用法,例如测试代码运行时间、函数嵌套定义等等。 from time import time from...

    Python小屋屋主
  • Python利用Spark并行处理框架批量判断素数

    方法一: from pyspark import SparkConf, SparkContext conf = SparkConf().setAppName(...

    Python小屋屋主
  • Python+SQLite开发无界面版通信录管理系统

    本文重点在于演示Python对SQLite数据库的操作,以及命令行式菜单的工作原理和实现。 首先使用SQLite Database Browser创建SQLit...

    Python小屋屋主
  • 斗地主算法

           不得不承认,算法搁置了一些时间,代码的风格下降了好多!  贴上一个曹点多多且丑的代码!  Orz...  题目要求:      编码:3表示3点 ...

    Gxjun
  • 【剑指offer】二维数组查找

    在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个...

    ConardLi
  • LeetCode 468. 验证IP地址

    IPv4 地址由十进制数和点来表示,每个地址包含4个十进制数,其范围为 0 - 255, 用(".")分割。比如,172.16.254.1;

    Michael阿明
  • Android使用Volley实现上传文件功能

    private File mSelectedPictureFile; mSelectedPictureFile是一个File文件,参数名是file

    砸漏
  • 排序(Sort) 原

    排序是计算机程序设计中的一种重要操作。如果数据能够根据某种规则排序,就能大大挺高数据处理的算法效率。

    云飞扬
  • Leetcode: Valid Parentheses

    题目: Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ...

    卡尔曼和玻尔兹曼谁曼
  • LeetCode 79,明明是走迷宫问题,为什么不能用宽搜呢?

    今天是LeetCode专题第48篇文章,我们一起来看看LeetCode当中的第79题,搜索单词(Word Search)。

    TechFlow-承志

扫码关注云+社区

领取腾讯云代金券