鱼C论坛

 找回密码
 立即注册
查看: 4370|回复: 15

[技术交流] 斐波那契(Fibonacci)数列通项公式

[复制链接]
发表于 2016-10-1 19:28:45 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
斐波那契(Fibonacci)数列通项公式
F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}

此公式理论上是正确的,但由于 float类型 的精度还不够,所以程序算出来的结果会有误差。
如果把公式展开计算,得出的结果就是正确的。

所以,一下这个 Fib()函数在 0 ~ 71 范围内的结果是正确的。
  1. >>> def Fib(n):
  2.         s=5**(1/2) # √5
  3.         return int((1/s)*(((1+s)/2)**n - ((1-s)/2)**n))

  4. >>> print([Fib(i) for i in range(10)])
  5. [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2016-10-2 10:51:05 | 显示全部楼层
利用 decimal 大数计算模块,可以提高到第 122 项。

  1. from decimal import Decimal as dcm

  2. def Fib_Dec(n):
  3.     s = dcm(5).sqrt() # √5
  4.     fib = ((1/s)*(((1+s)/2)**n - ((1-s)/2)**n))
  5.     return int(fib.to_integral())

  6. print(122, Fib_Dec(122))
复制代码

结果:
  1. 122  14028366653498915298923761
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-10-2 11:59:29 | 显示全部楼层
SixPy 发表于 2016-10-2 10:51
利用 decimal 大数计算模块,可以提高到第 122 项。

结果:

又学会一招,我看了首贴,也想到用Decimal,但仍是在n=72后出现误差,看来还是得用Decimal的自己的取整方法
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2016-10-2 12:26:15 | 显示全部楼层
本帖最后由 SixPy 于 2016-10-2 12:28 编辑
SixPy 发表于 2016-10-2 10:51
利用 decimal 大数计算模块,可以提高到第 122 项。

结果:


调整精度到 50 ,可以提高到第 226 项。

  1. from decimal import Decimal as dcm,\
  2.                     getcontext as cntxt

  3. def Fib_Dec(n):
  4.     if n>122: cntxt().prec=50 # 调整精度
  5.     s = dcm(5).sqrt() # √5
  6.     fib = ((1/s)*(((1+s)/2)**n - ((1-s)/2)**n))
  7.     return int(fib.to_integral())

  8. print(226, Fib_Dec(226))
复制代码

结果:
  1. 226   76159080909572301618801306271765994056795952743
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2016-10-2 12:47:03 | 显示全部楼层
冬雪雪冬 发表于 2016-10-2 11:59
又学会一招,我看了首贴,也想到用Decimal,但仍是在n=72后出现误差,看来还是得用Decimal的自己的取整方 ...

你测试一下,迭代法 和 公式法 哪一个速度快?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-10-2 12:59:16 | 显示全部楼层
SixPy 发表于 2016-10-2 12:47
你测试一下,迭代法 和 公式法 哪一个速度快?

还是迭代快些,毕竟只用到整数运算,我测试了仅算n=226和从0到226
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2016-10-2 13:07:39 | 显示全部楼层
冬雪雪冬 发表于 2016-10-2 12:59
还是迭代快些,毕竟只用到整数运算,我测试了仅算n=226和从0到226

迭代法
  1. def fib_itr(n):
  2.     if n<0: return None
  3.     if n<=1: return (0,1)[n]
  4.     a,b = 0,1
  5.     for i in range(n-1):
  6.         a, b = b, a+b
  7.     return b
复制代码


嗯,按说 公式法 是直接算出来的。
而 迭代法 还有循环。
搞不懂~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-10-2 15:16:58 From FishC Mobile | 显示全部楼层
但其实加法运算速度对计算机来说是最快的,尤其是对大数来说,加法比次方和根号运算快得多~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2016-10-3 18:52:43 | 显示全部楼层
用矩阵乘法 实现的 fib数列算法,可以算到 第93项。
uint64 是64位无符号整型,numpy 提供的最大整数类型。
  1. # 矩阵乘法
  2. import numpy as np

  3. def MatrixPower(n): # 矩阵的幂运算
  4.     Matx = np.array([[1,1],[1,0]],np.uint64)
  5.     if n == 1:
  6.         mat = Matx
  7.     elif n%2 == 0 : # 偶数
  8.         mat = MatrixPower(n / 2) # 递归
  9.         mat = np.dot(mat, mat) # 幂运算
  10.     elif n%2 == 1 : # 奇数
  11.         mat = MatrixPower((n-1) / 2) # 递归
  12.         mat = np.dot(mat, mat) # 幂运算
  13.         mat = np.dot(mat, Matx)
  14.     return mat

  15. def Fib_matx(n): # 计算Fibnacci的第n项
  16.     if n<0: return None
  17.     if n<2: return (0,1)[n]
  18.     fib_matrix = MatrixPower(n-1)
  19.     return fib_matrix[0,0]

  20. print(93, Fib_matx(93))
复制代码

结果:
  1. 93  12200160415121876738
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2016-10-3 20:32:23 | 显示全部楼层
用List模拟 矩阵
不用numpy模块,就自己实现一个 矩阵乘法 函数。
由于没有了数据类型的限制,python 自动用大数运算进行计算,
算到第几项,就看电脑内存有多大了~

  1. #用List模拟 矩阵

  2. def MatDot(matA, matB): # 矩阵乘法
  3.     mat_rslt = [[1,1],[1,0]]  
  4.     mat_rslt[0][0] = matA[0][0] * matB[0][0] + matA[0][1] * matB[1][0]
  5.     mat_rslt[0][1] = matA[0][0] * matB[0][1] + matA[0][1] * matB[1][1]
  6.     mat_rslt[1][0] = matA[1][0] * matB[0][0] + matA[1][1] * matB[1][0]
  7.     mat_rslt[1][1] = matA[1][0] * matB[0][1] + matA[1][1] * matB[1][1]
  8.     return mat_rslt

  9. def MatrixPower_ls(n): # 矩阵的幂运算
  10.     Matx = [[1,1],[1,0]]
  11.     if n == 1:
  12.         mat = Matx
  13.     elif n%2 == 0 : # 偶数
  14.         mat = MatrixPower_ls(n / 2) # 递归
  15.         mat = MatDot(mat, mat) # 幂运算
  16.     elif n%2 == 1 : # 奇数
  17.         mat = MatrixPower_ls((n-1) / 2) # 递归
  18.         mat = MatDot(mat, mat) # 幂运算
  19.         mat = MatDot(mat, Matx)
  20.     return mat

  21. def Fib_matx_ls(n): # 计算Fibnacci的第n项
  22.     if n<0: return None
  23.     if n<2: return (0,1)[n]
  24.     fib_matrix = MatrixPower_ls(n-1)
  25.     return fib_matrix[0][0]

  26. print(300, Fib_matx_ls(300))
复制代码

结果:
  1. 300  222232244629420445529739893461909967206666939096499764990979600
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-10-3 20:50:44 | 显示全部楼层
我比较喜欢列表法算,感觉比迭代法更快,因为不用每次交换3个数字进行运算,代码也更 简洁。
  1. 226 76159080909572301618801306271765994056795952743
  2. [Finished in 0.4s]
复制代码

  1. Fib = [1,1]
  2. def getFib(num):
  3.         for i in range(2,int(num)):
  4.                 Fib.append(Fib[-2]+Fib[-1])
  5.         return Fib[-1]
  6. print(226,getFib(226))
复制代码


评分

参与人数 1鱼币 +5 收起 理由
SixPy + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-10-3 20:54:50 | 显示全部楼层
本帖最后由 SixPy 于 2016-10-3 21:17 编辑

列表法算到100000项也只有1.4秒(手机上)
  1. 100000 2597406934722172416615503402127591541488048…………4355609970015699780289236362349895374653428746875
  2. [Finished in 1.6s]
复制代码

点评

列了太多无意义数字,影响观看,帮你删了中间大部分。  发表于 2016-10-3 21:21
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2016-10-3 21:05:09 | 显示全部楼层
jerryxjr1220 发表于 2016-10-3 20:50
我比较喜欢列表法算,感觉比迭代法更快,因为不用每次交换3个数字进行运算,代码也更 简洁。

列表占用内存多~
 7楼 的迭代法 只用了 a、b 两个变量,空间复杂度很小的。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-10-3 22:16:25 | 显示全部楼层
SixPy 发表于 2016-10-3 21:05
列表占用内存多~
 7楼 的迭代法 只用了 a、b 两个变量,空间复杂度很小的。

嗯,也是有道理。
看使用的环境,各有利弊。
列表的好处是保留了所有计算结果,下次还能从列表调用计算过的值。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2016-10-3 22:50:18 | 显示全部楼层
jerryxjr1220 发表于 2016-10-3 22:16
嗯,也是有道理。
看使用的环境,各有利弊。
列表的好处是保留了所有计算结果,下次还能从列表调用计算 ...

那就用 这个 生成器。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 06:36

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表