如何使用Python实现斐波那契Fibonacci函数
这篇文章主要介绍了如何使用Python实现斐波那契Fibonacci函数相关资料,需要的朋友可以参考下
Fibonacci斐波那契数列,很简单,就是一个递归嘛,学任何编程语言可能都会做一下这个。
最近在玩Python,在粗略的看了一下Learning Python和Core Python之后,偶然发现网上有个帖子Python程序员的进化写的很有意思。于是打算仿照一篇,那篇帖子用了十余种方法完成一个阶乘函数,我在这里会用九种不同的风格写出一个Fibonacci函数。
要求很简单,输入n,输出第n个Fibonacci数,n为正整数
下面是这九种不同的风格:
1)第一次写程序的Python程序员:
def fib(n):
return nth fibonacci number说明:
第一次写程序的人往往遵循人类语言的语法而不是编程语言的语法,就拿我一个编程很猛的哥们来说,他写的第一个判断闰年的程序,里面直接是这么写的:如果year是闰年,输出year是闰年,否则year不是闰年。
2)刚学Python不久的的C程序员:
def fib(n):#{
if n<=2 :
return 1;
else:
return fib(n-1)+fib(n-2);
#}说明:
在刚接触Python时,用缩进而非大括号的方式来划分程序块这种方式我是很不适应的,而且每个语句后面没有结束符,所以每次写完一个Python函数之后干的第一件事一般就是一边注释大括号,一边添加漏掉的冒号。
3)懒散的Python程序员:
def fib(n):
return 1 and n<=2 or fib(n-1)+fib(n-2)说明:
看了Learning Python之后,才知道Python没有三元操作符?,不过鉴于Python里bool值比较特殊(有点像C,非零即真,非空即真),再加上Python的逻辑语句也是支持短路求值(Short-Circuit Evaluation)的,这就可以写出一个仿?语句出来。
4)更懒的Python程序员:
fib=lambda n:1 if n<=2 else fib(n-1)+fib(n-2)说明:
lambda关键字我曾在C#和Scheme里面用过,Python里面的lambda比C#里简便,并很像Scheme里的用法,所以很快就适应了。在用Python Shell声明一些小函数时经常用这种写法。
5)刚学完数据结构的Python程序员:
def fib(n):
x,y=0,1
while(n):
x,y,n=y,x+y,n-1
return x说明:
前面的Fibonacci函数都是树形递归的实现,哪怕是学一点算法就应该知道这种递归的低效了。在这里从树形递归改为对应的迭代可以把效率提升不少。
Python的元组赋值特性是我很喜欢的一个东东,这玩意可以把代码简化不少。举个例子,以前的tmp=a;a=b;b=tmp;可以直接用一句a,b=b,a实现,既简洁又明了。
6)正在修SICP课程的Python程序员:
def fib(n):
def fib_iter(n,x,y):
if n==0 : return x
else : return fib_iter(n-1,y,x+y)
return fib_iter(n,0,1)说明:
在这里我使用了Scheme语言中很常见的尾递归(Tail-recursion)写法。Scheme里面没有迭代,但可以用不变量和尾递归来模拟迭代,从而实现相同的效果。不过我还不清楚Python有没有对尾递归做相应的优化,回头查一查。
PS:看过SICP的同学,一眼就能看出,这个程序其实就是SICP第一章里的一个例子。
7)好耍小聪明的Python程序员:
fib=lambda n,x=0,y=1:x if not n else f(n-1,y,x+y)说明:
基本的逻辑和上面的例子一样,都是尾递归写法。主要的区别就是利用了Python提供的默认参数和三元操作符,从而把代码简化至一行。至于默认参数,学过C++的同学都知道这玩意,至于C#4.0也引入了这东东。
8)刚修完线性代数的Python程序员:
def fib(n):
def m1(a,b):
m=[[],[]]
m[0].append(a[0][0]*b[0][0]+a[0][1]*b[1][0])
m[0].append(a[0][0]*b[0][1]+a[0][1]*b[1][1])
m[1].append(a[1][0]*b[0][0]+a[1][1]*b[1][0])
m[1].append(a[1][0]*b[1][0]+a[1][1]*b[1][1])
return m
def m2(a,b):
m=[]
m.append(a[0][0]*b[0][0]+a[0][1]*b[1][0])
m.append(a[1][0]*b[0][0]+a[1][1]*b[1][0])
return m
return m2(reduce(m1,[[[0,1],[1,1]] for i in range(n)]),[[0],[1]])[0]说明:
这段代码就不像之前的代码那样清晰了,所以先介绍下原理(需要一点线性代数知识):
首先看一下之前的迭代版本的Fibonacci函数,很容易可以发现存在一个变换:y->x, x+y->y。换一个角度,就是[x,y]->[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)。
9)准备参加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,原理很简单,可以类比自然数的快速求幂方法,所以这里就不多说了。
PS:虽然说是ACM版本,不过说实话我从来没参加过那玩意,毕竟自己算法太水了,那玩意又太高端??只能在这里YY一下鸟~
python中,最基本的那种递归(如下fib1)效率太低了,只要n数字大了运算时间就会很长;而通过将计算的指保存到一个dict中,后面计算时直接拿来使用,这种方式成为备忘(memo),如下面的fib2函数所示,则会发现效率大大提高。
在n=10以内时,fib1和fab2运行时间都很短看不出差异,但当n=40时,就太明显了,fib1运行花了35秒,fab2运行只花费了0.00001秒。
n=40时,输出如下:
jay@jay-linux:~/workspace/python.git/py2014$ python fibonacci.py
2014-10-16 16:28:35.176396
fib1(40)=102334155
2014-10-16 16:29:10.479953
fib2(40)=102334155
2014-10-16 16:29:10.480035这两个计算Fibonacci数列的函数,如下:https://github.com/smilejay/python/blob/master/py2014/fibonacci.py
import datetime
def fib1(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib1(n - 1) + fib1(n - 2)
known = {0: 0, 1: 1}
def fib2(n):
if n in known:
return known[n]
res = fib2(n - 1) + fib2(n - 2)
known[n] = res
return res
if __name__ == '__main__':
n = 40
print(datetime.datetime.now())
print('fib1(%d)=%d' % (n, fib1(n)))
print(datetime.datetime.now())
print('fib2(%d)=%d' % (n, fib2(n)))
print(datetime.datetime.now())后记:
由于刚学习Python没多久,所以对其各种特性的掌握还不够熟练。与其说是我在用Python写程序,倒不如说我是在用C,C++,C#或是Scheme来写程序。至于传说中的Pythonic way,我现在还没有什么体会,毕竟还没用Python写过什么真正的程序。
Learning Python和Core Python都是不错的Python入门书籍,前者更适合没有编程基础的人阅读。
Python是最好的初学编程入门语言,没有之一。所以它可以取代Scheme成为MIT的计算机编程入门语言。
python3.11这个版本怎么使用?
你可以直接在python官网中根据你自己使用的电脑系统差别,下载python3.11版本安装在自己的电脑上使用,python3的版本其实差别不大,可以通过阅读官方文档辨析各个版本的差别,在使用上不太需要关注小版本。
新手怎么学习python?
我们将学习的过程划分为4个阶段,每个阶段学习对应的内容,具体的学习顺序如下:Python学习顺序:①Python软件开发基础 掌握计算机的构成和工作原理 会使用Linux常用工具 熟练使用Docker的基本命令 建立Python开发环境,并使用print输出 使用Python完成字符串的各种操作 使用Python re模块进行程序设计 使用Python创建...
电脑上安装python后怎么使用
windows系统打开命令提示符,Linux系统打开终端,输入Python即可进入Python交互环境。如果提示错误,就输入Python3,这是版本的问题。
在python中如何使用注释
python中的注释有多种,有单行注释,多行注释,批量注释,中文注释也是常用的。一、python单行注释符号(#):井号(#)常被用作单行注释符号,在代码中使用#时,它右边的任何数据都会被忽略,当做是注释。print 1 #输出1,#号右边的内容在执行的时候是不会被输出的。二、批量、多行注释符号:在python中...
如何在电脑中安装python
有的朋友需要在电脑中使用python,今天小编就跟大家分享一下如何在电脑中安装python。具体如下:1. 首先我们在电脑中找到安装包,安装包的后缀需要是“.exe”的。2. 然后我们勾选这个安装包,并点击下载选项。3. 当下载完成之后我们在本地中找到这个安装包。4. 对安装包进行双击,5. 双击之后会打开...
使用python需要安装哪些软件
《Python 3.9.7软件》百度网盘资源免费下载:链接: https:\/\/pan.baidu.com\/s\/1BY60FGfwL3exK7xOooF_nw ?pwd=nhfc 提取码: nhfc Python 3.9.7最新正式版是一种面向对象、直译式计算机程序设计语言,也是一种功能强大而完善的通用型语言,已经具有十多年的发展历史,成熟且稳定。python具有非常简捷...
如何使用Python问题,怎么解决
为了正确处理多语言文本,Python在2.0版后引入了Unicode字符串。从那时起,Python语言中的字符串就分为两种:一种是2.0版之前就已经使用很久的传统Python字符串,一种则是新的Unicode字符串。在Python语言中,一般的解决办法是使用unicode()内建函数对一个传统Python字符串进行“解码”,得到一个Unicode...
结合实际谈谈python在财务基础工作中的应用
2、以及使用NumPy库进行数值计算和统计分析。自动化报表生成:Python可以结合Excel或其他表格处理软件,实现财务报表的自动生成。通过编写Python脚本,可以定期从数据库中提取数据,然后根据预设的模板和格式生成报表,大大提高了工作效率。3、此外,还可以使用Python的图表库(如Matplotlib、Seaborn等)对数据进行...
python如何自学
学习python主要有自学和报班学习两种方式。具体学的顺序如下:①Python软件开发基础 掌握计算机的构成和工作原理 会使用Linux常用工具 熟练使用Docker的基本命令 建立Python开发环境,并使用print输出 使用Python完成字符串的各种操作 使用Python re模块进行程序设计 使用Python创建文件、访问、删除文件 掌握import ...
在Python3.6里装了tensorflow,怎么在Python10中使用?
为了在 Python 3.10 中使用 Python 3.6 中安装的 TensorFlow,需要将 TensorFlow 从 Python 3.6 中导出,并在 Python 3.10 中导入。具体步骤如下:1. 在 Python 3.6 中安装 TensorFlow。2. 打开命令提示符或终端窗口,进入 Python 3.6 的安装路径(通常为 `C:\\Program Files\\Python36\\` 或...
白哪力基: 代码如下: # 获取斐波那契数列 def get_Fibonacci(count): fib = [] # 如果输入个数小于1,则错误,返回0 if count<1: print('count is not valid, should be more than 0') return 0 # 如果输入个数为1 elif count == 1: fib = [1] # 如果输入个数为2 elif count =...
龙山区13251453778: 斐波那契数列用python怎么表示 - ?
白哪力基: 斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13,特别指出:第0项是0,第1项是第一个1.从第三项开始,每一项都等于前两项之和.Python 实现斐波那契数列代码如下:# -*- coding: UTF-8 -*-# Filename : test.py# author by : www....
龙山区13251453778: python编程,斐波那契数列? - ?
白哪力基: 婓波那契数列(前两个数的和是第三个数) def fib(num): fibs=[0,1] #num=input('请输入婓波那契数列中的数据个数:') for i in range(int(num)-2): fibs.append(fibs[-2]+fibs[-1]) print(fibs) print(fibs[-2]) fib(10)
龙山区13251453778: 如何在python环境中生成斐波那契数列 - ?
白哪力基: def fib(limit):n, a, b = 0, 0, 1while n < limit:yield ba, b = b, a + bn += 1
龙山区13251453778: python怎么写斐波那契数列 - ?
白哪力基: 斐波那契数列非常pythonic的写法是:1 2 3 4 5 6 7# -*- coding:utf-8 -*- deffibs(num):a=b=1fori inrange(num):yieldaa,b=b,a+b printlist(fibs(10))
龙山区13251453778: python递归求斐波那契数列前10项 - ?
白哪力基: 你好,很高兴为你解答.根据斐波那契数列F(n)=F(n-1)+F(n-2),当n=1和n=2时,F(n)=1,可以利用函数+if分支结构编写递归程序,求出斐波那契数列前10项.具体代码如下: 求斐波那契数列前10项
龙山区13251453778: python写斐波那契数列 - ?
白哪力基: 如果你是3.0以上版本,你的print语法就是错的,应该是print(fib(10)) 另外,你这个函数的结果也并不是返回的数列
龙山区13251453778: Python用递归函数得到斐波那契数列前20项 注意:要定义函数,运行结果是列表 - ?
白哪力基: def Fibonacci(n): if n == 1: return 1 dic = [-1 for i in xrange(n)] dic[0], dic[1] = 1, 1 helper(n-1, dic) linesize = 5 file=open('Fibonacci.txt', 'w') for loop in range(len(dic)/linesize): line = [] for i in range(linesize): line.append(dic[i + linesize * loop]) file.write...
龙山区13251453778: 怎么样在python中表示部分斐波那契数列 - ?
白哪力基: 1 2 3 4 5 6 7deffib_n(n):a, b =0, 1result =[]fori inrange(n):result.append(b)a, b =b, a+breturnresult
龙山区13251453778: Python解决斐波那契数列的问题 - ?
白哪力基: 这个是函数的地柜调用. 当fib(5)执行过程,n = 5 进入else处理 递归调用Fib(n - 1) + Fib(n - 2) 这里n 是5,返回"Fib(4) + Fib(3)"的值. Fib(4): Fib(4)调用,Fib(n - 1) + Fib(n - 2) 这里n 是4,返回"Fib(3) + Fib(2)"的值 Fib(3) 调用,Fib(n - 1) + ...