用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的计算机编程入门语言。

时间: 2016-03-23

php实现斐波那契数列的简单写法

斐波那契数列是非常常见的一类数列,其数学定义为:F0=1,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*).本文就用php来简单实现斐波那契数列,代码十分简洁易懂,如下所示: <?php $arr[1] = 1; for($i = 2;$i < 100;$i++) { $arr[$i] = $arr[$i-1] + $arr[$i-2]; } echo join(",",$arr);//将数组合并为一个字符串输出 ?> 至此就实现了Fn=F(n-

C++输出斐波那契数列的两种实现方法

定义: 斐波那契数列指的是这样一个数列:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...这个数列从第三项开始,每一项都等于前两项之和. 以输出斐波那契数列的前20项为例: 方法一:比较标准的做法,是借助第三个变量实现的. 复制代码 代码如下: #include<iostream>  using namespace std;int main(){    int f1=0,f2=1,t,n=1;    cout<<"数列第1个

C语言使用普通循环方法和递归求斐波那契序列示例代码

复制代码 代码如下: #include <stdio.h> int fac(int x); int main(void){    int n;    scanf("%d", &n);    if (n == 1 || n == 2)        printf("1\n");    else if (n == 3)        printf("2\n");    else    {        int last = 1; 

java实现斐波那契数列的3种方法

先说说为什么写这个吧,这个完全是由去阿里巴巴面试引起的一次惨目忍睹的血案.去面试的时候,由于面试前天晚上11点钟才到阿里巴巴指定面试城市,找到旅馆住下基本都1点多,加上晚上完全没有睡好,直接导致第二天面试效果很不好(对于那些正在找工作的大虾们不要向小虾一下悲剧,提前做好准备还是很重要滴),面试大概进行了一个多小时(面试结束回去的时候基本走路都快睡着了,悲催!!),面试快结束的时候面试官问的我问题就是关于费波那西数列,当时头脑完全浆糊,只知道要设置三个变量或者用List先初始化,当写到for循环的

c#斐波那契数列(Fibonacci)(递归,非递归)实现代码

//Main 复制代码 代码如下: using System;using System.Collections.Generic;using System.Linq;using System.Text; namespace Fibonacci{    class Program    {        static void Main(string[] args)        {            Console.WriteLine("Would you like to know which

求斐波那契(Fibonacci)数列通项的七种实现方法

一:递归实现使用公式f[n]=f[n-1]+f[n-2],依次递归计算,递归结束条件是f[1]=1,f[2]=1.二:数组实现空间复杂度和时间复杂度都是0(n),效率一般,比递归来得快.三:vector<int>实现时间复杂度是0(n),时间复杂度是0(1),就是不知道vector的效率高不高,当然vector有自己的属性会占用资源.四:queue<int>实现当然队列比数组更适合实现斐波那契数列,时间复杂度和空间复杂度和vector<int>一样,但队列太适合这里了,

php处理斐波那契数列非递归方法

我自己构思了下,实际上程序来解决这个事情,就是一个偏移量的问题.首先看数列::1.1.2.3.5.8.13.21.34数列的下一个数是前2个数字之和,以此类推. 程序处理的话,实际上就是一个FOR语句,传统FOR语句是for($i=1;$i;$count,$i++),这里的偏移量是$i=$i+1.如果处理这个数列的话,这个偏移量就不是1了,是前1个数字.那么当你for的时候,一个变量记录上一个数字,另外一个记录当前数字,偏移量为这上一个数字,然后在循环中重新赋值,将上一个数字记录成当然循环值,以

python求斐波那契数列示例分享

复制代码 代码如下: def getFibonacci(num): res=[0,1] a=0 b=1 for x in range(0,num):  if x==a+b:   res.append(x)   a,b=b,a+b return res res=getFibonacci(1000)print(res) #递归a=[0,1]qian=0def fibna(num,qian): print(num) he=num+qian if he<1000:  a.append(he)  qian

python实现斐波那契数列的方法示例

介绍 斐波那契数列,又称黄金分割数列,指的是这样一个数列:0.1.1.2.3.5.8.13.21.--在数学上,斐波纳契数列以如下递归的方法定义: F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*) . 1. 元组实现 fibs = [0, 1] for i in range(8): fibs.append(fibs[-2] + fibs[-1]) 这能得到一个在指定范围内的斐波那契数列的列表. 2. 迭代器实现 class Fibs: def __init__

python实现斐波那契递归函数的方法

本文以一个简单的实例讲述了python实现斐波那契数列数列递归函数的方法,代码精简易懂.分享给大家供大家参考之用. 主要函数代码如下: def fab(n): if n==1: return 1 if n==0: return 0 else: result=int(fab(n-1))+int(fab(n-2)) return result 测试代码如下: for i in range(10): print fab(i) 希望本文所述对大家Python程序设计的学习有所帮助.

利用Python实现斐波那契数列的方法实例

今天我们来使用Python实现递归算法求指定位数的斐波那契数列 首先我们得知道斐波那契数列是什么? 斐波那契数列又叫兔子数列 斐波那契数列就是一个数列从第三项开始第三项的值是第一项和第二项的和依次类推 其次我们再来看递归算法是什么? 递归就是如果函数(子程序)包含了对其自身的调用,该函数就是递归的 话不多说上案例: 第一种方法:不使用递归算法 #首先定义一个新的列表来储存最后的结果 new_list = [] # 然后让用户输入指定位数 my_put = int(input("请输入使用递归算法

Python打印斐波拉契数列实例

本文实例讲述了Python打印斐波拉契数列的方法.分享给大家供大家参考.具体实现方法如下: #打印斐波拉契数列 #!/usr/bin/python def feibolaqi(n): if n == 0 or n == 1: return n else: return feibolaqi(n-1) + feibolaqi(n-2) num = int(raw_input('please input a int:')) if num >= 0: print 'feibolaqi(%d) is %d

使用python求斐波那契数列中第n个数的值示例代码

斐波那契数列(Fibonacci sequence),又称黄金分割数列.因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为"兔子数列",指的是这样一个数列:1.1.2.3.5.8.13.21.34.--在数学上,斐波纳契数列以如下被以递归的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*) 求斐波那契数列中第n个数的值:1,1,2,3,5,8,13,21,34- 方法一:用for循

如何使用Python实现斐波那契数列

斐波那契数列(Fibonacci)最早由印度数学家Gopala提出,而第一个真正研究斐波那契数列的是意大利数学家 Leonardo Fibonacci,斐波那契数列的定义很简单,用数学函数可表示为: 数列从0和1开始,之后的数由前两个数相加而得出,例如斐波那契数列的前10个数是:0, 1, 1, 2, 3, 5, 8, 13, 21, 34. 用 Python 实现斐波那契数列常见的写法有三种,各算法的执行效率也有很大差别,在面试中也会偶尔会被问到,通常面试的时候不是让你简单的用递归写写就完了,

java数学归纳法非递归求斐波那契数列的方法

本文实例讲述了java数学归纳法非递归求斐波那契数列的方法.分享给大家供大家参考.具体如下: Integer能表示的最大值为 2147483647 大概是21.4亿,这里没有考虑溢出情况(当size为983时就会溢出)! import java.util.List; import java.util.ArrayList; /** * @author jxqlovejava * 斐波那契数列 */ public class Fibonacci { public static List<Intege

JAVA递归与非递归实现斐波那契数列

斐波那契数列(Fibonacci sequence),又称黄金分割数列.因数学家列昂纳多·斐波那契(Leonardoda Fibonacci[1] )以兔子繁殖为例子而引入,故又称为"兔子数列",指的是这样一个数列:0.1.1.2.3.5.8.13.21.34.--在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*)在现代物理.准晶体结构.化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1963起