python斐波那契数列的九种思路与多解

2024-07-05 16:09| 来源: 网络整理| 查看: 265

斐波那契数列介绍：

在这里插入图片描述

第一种方式：刚开始学python的程序员 def fib(n): return nth fibonacci number

这个程序可以看出是一个伪代码，定义了函数后，将return翻译一下就是返回第n个斐波那契数列的数值，这也是做程序员必须掌握的吧，首先需要看懂伪码，然后写下自己的伪码，再最后构建真实的代码，这或许比直接写出能运行的代码更加真实，而大部分人却选择了跳过前面两步，最后造成结果就是只能做coder，而不是manager。

第二种方式：有其它编程语法经验的程序员 def fib(n): if n[y,x+y]。在这里，我声明一个二元向量[x,y]T，它通过一个变换得到[y,x+y]T，可以很容易得到变换矩阵是[[1,0],[1,1]]，也就是说：[[1,0],[1,1]]*[x,y]T=[y,x+y]T 令二元矩阵A=[[1,0],[1,1]]，二元向量x=[0,1]T，容易知道Ax的结果就是下一个Fibonacci数值，即： Ax=[fib(1),fib(2)]T 亦有： Ax=[fib(2),fib(3)]T ……………… 以此类推，可以得到： Aⁿx=[fib(n),fib(n-1)]T 也就是说可以通过对二元向量[0,1]T进行n次A变换，从而得到[fib(n),fib(n+1)]T，从而得到fib(n)。在这里定义了一个二元矩阵的相乘函数m1，以及一个在二元向量上的变换m2，然后利用reduce操作完成一个连乘操作得到Aⁿx，最后得到fib(n)。

第九种方式：准备参加ACM比赛的Python程序员 def fib(n): lhm=[[0,1],[1,1]] rhm=[[0],[1]] em=[[1,0],[0,1]] #multiply two matrixes def matrix_mul(lhm,rhm): #initialize an empty matrix filled with zero result=[[0 for i in range(len(rhm[0]))] for j in range(len(rhm))] #multiply loop for i in range(len(lhm)): for j in range(len(rhm[0])): for k in range(len(rhm)): result[i][j]+=lhm[i][k]*rhm[k][j] return result def matrix_square(mat): return matrix_mul(mat,mat) #quick transform def fib_iter(mat,n): if not n: return em elif(n%2): return matrix_mul(mat,fib_iter(mat,n-1)) else: return matrix_square(fib_iter(mat,n/2)) return matrix_mul(fib_iter(lhm,n),rhm)[0][0]

说明：

看过上一个fib函数就比较容易理解这一个版本了，这个版本同样采用了二元变换的方式求fib(n)。不过区别在于这个版本的复杂度是lgn，而上一个版本则是线性的。这个版本的不同之处在于，它定义了一个矩阵的快速求幂操作fib_iter，原理很简单，可以类比自然数的快速求幂方法，所以这里就不多说了。

衍生题：

这是我在pythontip上看到的有一个基础题，题目如下：

斐波那契数列为1,1,2,3,5,8…。数列从第三项起满足，该项的数是其前面两个数之和。现在给你一个正整数n（n < 10000), 请你求出第n个斐波那契数取模20132013的值（斐波那契数列的编号从1开始）。例如： n=1, 则输出：1 n=4, 则输出：3

这里有很多种解法，题目整体的意思很简单，就是当和为20132013问加的最后一个斐波那契数是第几个，这里我将我和我当初想的一样的一种解法放上，当然还有很多种其它更高大上的解法，这里也只是一种，其它的就不说了。

L = [1, 1] while len(L)

【本文地址】

公司简介

联系我们