python 实现斐波那契数列

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐学习书目

› Learn Python the Hard Way

Python Sites

› PyPI - Python Package Index

› http://diveintopython.org/toc/index.html

› Pocoo

值得关注的项目

› PyPy

› Celery

› Jinja2

› Read the Docs

› gevent

› pyenv

› virtualenv

› Stackless Python

› Beautiful Soup

› 结巴中文分词

› Green Unicorn

› Sentry

› Shovel

› Pyflakes

› pytest

Python 编程

› pep8 Checker

Styles

› PEP 8

› Google Python Style Guide

› Code Style from The Hitchhiker's Guide

这是一个创建于 3194 天前的主题，其中的信息可能已经有所发展或是发生改变。

各位 pythoner 们，大家来分享用 python 实现斐波那契数列的不同做法吧！！~\(≧▽≦)/~

契数列

斐波那

Python

Pythoner

59 条回复 • 2016-02-27 22:41:08 +08:00

florije

2016-02-26 15:31:29 +08:00

def fib(n):
a,b = 1,1
for i in range(n-1):
a,b = b,a+b
return a
print fib(5)
先来个最简单的吧~

MyLeoWind

2016-02-26 15:31:48 +08:00 via Android

a, b = b, a+b
这个确实是最简洁的。

kevinyoung

2016-02-26 15:34:01 +08:00

送分题不做

songkaiape

2016-02-26 15:39:40 +08:00

@kevinyoung 有一百个人，分别从 1 一直到 100 。现在有人拿枪从第一个开始枪毙，每枪毙一个跳过一个，一直到一轮完成。接着在活着的人里面再次枪毙第一个，间隔一个再枪毙一个，请问最后活着的是这一百个人里的第几个人？给你个有难度的=。=

1373569162

2016-02-26 15:47:43 +08:00

俺贴个别人总结版的, 有兴趣的看下
http://www.cnblogs.com/figure9/archive/2010/08/30/1812927.html
还有一个求质数的有兴趣的可以实现一下
https://program-think.blogspot.com/2011/12/prime-algorithm-1.html

glchaos

2016-02-26 15:51:39 +08:00

@kevinyoung 不送分的题不会做，就是这么任性

random2case

2016-02-26 15:55:48 +08:00

俺喜欢斐波那契数列，先来一个 rust 写的
fn fibonacci (n:i32) ->i32{
if n<=2 {1} else {fibonacci(n-1)+fibonacci(n-2)}
}
再来一个 scala 写的
object test{
def fibonacci(n:Int):Int={
if (n<2) 1 else fibonacci(n-1)+fibonacci(n-2)
}
}

eote

2016-02-26 15:58:04 +08:00

```
import json
import urllib2
import lxml.etree

html = urllib2.urlopen('https://oeis.org/A000045/list').read()
pre = lxml.etree.HTML(html).xpath('//pre')
rst = json.loads(pre[0].text)

for i in rst:
print(str(i) + '\n')
```

输出前 38 个 Fib

jixiangqd

2016-02-26 16:01:44 +08:00

@songkaiape 这个貌似也没难度啊，直接按字面意思翻译成程序就能跑出结果？
a=[i+1 for i in range(100)]
while len(a)>1:
b=a[:]
for i in range(0,len(a),2):
a.remove(b[i])
print a

jixiangqd

2016-02-26 16:03:37 +08:00

重新贴一下程序
```python
a=[i+1 for i in range(100)]
while len(a)>1:
b=a[:]
for i in range(0,len(a),2):
a.remove(b[i])
print a
```

qiuhanyuan

2016-02-26 16:08:52 +08:00

def fibs(num):
result = [1, 1]
for i in range(num-2):
result.append(result[-1]+result[-2])
return result

Lihz

2016-02-26 16:19:15 +08:00

楼上的都不喜欢用 yield 构建生成器么？如果拿这做面试题，侧重的不在于能否给出答案，而是被面试者能否脑补出不同条件并构建对应方案以及在不同方案下暴露出的编程习惯吧

Lihz

2016-02-26 16:20:55 +08:00

类似的还有素数筛选这种看似简单，但深入而言可挖掘的点是非常多的

fulvaz

2016-02-26 16:25:59 +08:00

斐波那契数列很多结果都可以重复利用, 只需要加个缓存, 就能有非常棒的速度

: )

songkaiape

2016-02-26 16:29:03 +08:00

@jixiangqd 嗯，是不难啊，不过你为什么这样写 a=[i+1 for i in range(100)] ，直接 a=list(range(1,101))不就好了么

songkaiape

2016-02-26 16:30:38 +08:00

@jixiangqd
l=range(1,101)
while len(l)!=1:
l=l[1::2]
print(l[0])
更优雅的解法，当然其实本质上都一样=。=

livc

2016-02-26 16:30:38 +08:00

@songkaiape 约瑟夫环

jixiangqd

2016-02-26 16:32:08 +08:00

@songkaiape 这倒是，- -，随手写的，留了些坏习惯在代码里

mcfog

2016-02-26 16:36:25 +08:00

在 V2EX 要大家贴派森代码简直残忍(つД`)ノ

jixiangqd

2016-02-26 16:40:40 +08:00

@songkaiape 18 楼真是 Pythonic.... 突然发现我还是新手。。。水平惨不忍睹

mikej

2016-02-26 17:16:13 +08:00

@florije return 完了没输出。。

mouer

2016-02-26 17:21:53 +08:00

fib = lambda n : 1 if n <= 2 else fib(n - 1) + fib(n - 2)

florije

2016-02-26 17:22:34 +08:00

@mikej 不好意思，格式都被吃了……写 python 的应该能看出来缩进吧……

tempuseraccount

2016-02-26 17:25:19 +08:00

由此工作中还真有用了 fibonacci 数列的地方。
真使用的话还是最好把值存在数组里直接取。能少算尽量少算

wentian

2016-02-26 17:48:18 +08:00

def fib():
fib1,fib2 = 1, 1
while True:
yield fib1
fib1, fib2 = fib2, fib1+fib2

mikej

2016-02-26 17:50:33 +08:00

@florije 怎样缩进这里都只输出了一个数嘛。。

dofy

2016-02-26 17:52:24 +08:00

可以贴 gist

ipconfiger

2016-02-26 17:55:19 +08:00

print [x[0] for x in [ (a[i][0], a.append((a[i][1], a[i][0]+a[i][1]))) for a in ([[1,1]], ) for i in xrange(100) ]]

一行

RqPS6rhmP3Nyn3Tm

2016-02-26 18:18:18 +08:00 via Android

Python 官网就有，一行搞定

RqPS6rhmP3Nyn3Tm

2016-02-26 18:24:34 +08:00 via Android

来个神经病版的

print '1,1,2,5,7,12,19,31,50'

wellsc

2016-02-26 18:32:53 +08:00

```
def fib(n):
f1 = f2 = 1
for k in range(1, n)
f1, f2 = f2, f2 + f1
return f2
```

bdbai

2016-02-26 19:44:29 +08:00 via iPhone

@random2case 俺不懂 fp ，不过用递归的效率真的好吗？

mailto1587

2016-02-26 20:43:25 +08:00

递归不 memoize 一下？

```
memo = {1: 1, 2: 1}
fib = lambda n: memo.get(n) or memo.setdefault(n, fib(n - 1) + fib(n - 2))
```

这方案的缺陷是，需要慢慢调教它，一下子 fib(5000)肯定会撒娇，需要 fib(1000)、 fib(2000)、 fib(3000)、 fib(4000)、 fib(5000)， Done ！

random2case

2016-02-26 20:46:14 +08:00

@bdbai 尾递归好的多，如 @fulvaz 所说的，加上了缓存，效率也高多了，据说相当于循环。尾递归不会每一次都分配新栈了。但是看着难理解了，幸好 scala 有一个 @tailrec 检查是否是尾递归呢。
def fib_out(n:Int):Int={
@tailrec
def _loop(n:Int,acc1:Int,acc2:Int):Int={
if(n < 2) acc2 else _loop(n-1,acc2,acc1+acc2)
}
_loop(n,1,1)
}
函数式编程是程序员的一个福利吧，如果你喜欢，并且可以因此发挥你的才智，创造，获得快乐。那么你完全可以享用它，同时，函数式编程作为一个福利，你也可以选择拒绝它。

random2case

2016-02-26 20:52:22 +08:00

@mailto1587 把俺写的这个 Int 换成 BigInt,试了下， fib(5000)瞬间出来了， 6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626 ，俺没办法把 fib(100000)贴上来，这装不下。但是也是不到一秒。

happywowwow

2016-02-26 21:12:21 +08:00

@BXIA
你这数列有点奇怪...
1,1,2,3,5,8,13

kevinyoung

2016-02-26 21:13:11 +08:00

@songkaiape 第一次会把奇数编号的去掉，剩下偶数编号的全部编号除以二，再进行这个过程，所以最后剩下的那个肯定是 100 以内最“偶”的那个， 64

shyling

2016-02-26 21:18:46 +08:00

@random2case 要有尾递归优化的尾递归才有用吧=。=， py 嘛~~~~~

kevinyoung

2016-02-26 21:24:44 +08:00

@bdbai 我觉得递归最大的好处是有些问题用递归的语言描述非常简洁，比如快排比如对树进行操作，但这并不总是成立的

回到 python ， python 虽然能递归，但并不会自动做尾递归优化，所以递归算这种东西可能会爆栈，另外函数调用也会造成额外的时间开销，直观的看同样作用的 python 代码，循环的就是比递归的快。所以写 python 的话其实不推荐写递归，而是想办法写成循环好一些

其他的语言另说，比如 Haskell 根本没有循环只能写递归，或者有些语言递归优化的好也可以。

random2case

2016-02-26 21:40:09 +08:00

@shyling python 尾递归是否优化，俺不太清楚，俺只是拿 python 做一些简单的事，对语言本身不了解。但是 scala 确实是对尾递归做过优化的。 https://www.google.com/#q=+scala+tail+recursion ，自行 google 一下吧。

如 @kevinyoung 所说， Haskell 根本没有循环只能写递归。 scala 借鉴了 Haskell 。但是 scala 也可以写循环的。

luobuda

2016-02-26 21:51:47 +08:00

http://www.nayuki.io/page/fast-fibonacci-algorithms

RqPS6rhmP3Nyn3Tm

2016-02-26 22:08:50 +08:00 via Android

@happywowwow 才发现…口算跳步骤习惯了…

bdbai

2016-02-26 22:10:35 +08:00 via iPhone

@kevinyoung @random2case
Python 对尾递归的支持我也不清楚，但我们有 yield 。

zangxixi

2016-02-26 22:13:36 +08:00

@eote 这种角度不错呀，但是要是我要 38 个以上肿么办？

zangxixi

2016-02-26 22:15:04 +08:00

@qiuhanyuan O(∩_∩)O 哈哈~这个也是我第一种写法

random2case

2016-02-26 22:16:24 +08:00

@bdbai 啊，争论哪个语言好永无止境。。。呵呵

zangxixi

2016-02-26 22:33:31 +08:00

@tempuseraccount 有道理，可以用动态规划
@wentian 不会死循环吗亲？

wentian

2016-02-26 22:54:12 +08:00

@zangxixi 不会,但是注意使用方式

递归的写法,如果没有缓存,时间效率太差了. (一行代码肯定酷,但可能也就仅止于此)

zoudm

2016-02-26 23:14:23 +08:00

@songkaiape
@kevinyoung
100 个人结果并不是 64 ，再考虑一下吧。
假如 10 个人，第一轮死了 1 3 5 7 9 ，那么 10 不会死， 10 的下一个人是 2 ，于是死的依次是 2 6 10 ，剩 4 8 ； 10 的下一个是 4 ， 10 死了， 4 不会死，于是 8 死了。答案是 4 。

100 个人答案是 73 （编号从 0 开始是 72 ）
https://en.wikipedia.org/wiki/Josephus_problem

edsgerlin

2016-02-26 23:22:05 +08:00

Y Combinator 写的比较好玩！
https://rosettacode.org/wiki/Y_combinator#Python
>>> Y = lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))
>>> fac = lambda f: lambda n: (1 if n<2 else n*f(n-1))
>>> [ Y(fac)(i) for i in range(10) ]
[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
>>> fib = lambda f: lambda n: 0 if n == 0 else (1 if n == 1 else f(n-1) + f(n-2))
>>> [ Y(fib)(i) for i in range(10) ]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

mailto1587

2016-02-26 23:42:47 +08:00

@random2case Python 不支持尾递归优化，除非做 CPS 变换，还得靠 trampoline 方法才能 work around

```
def trampoline(obj):
while hasattr(obj, '__call__'):
obj = obj()
return obj

def memoize(func):
memo = {}
def wrapper(n, ret=lambda x: x):
if n in memo:
return lambda: ret(memo[n])
def with_value(value):
memo[n] = value
return lambda: ret(value)
return lambda: func(n, with_value)
return wrapper

@memoize
def fib_cps(n, ret):
if n < 2:
return lambda: ret(n)
def with_a(a):
def with_b(b):
return lambda: ret(a + b)
return lambda: fib_cps(n - 1, with_b)
return lambda: fib_cps(n - 2, with_a)

print(trampoline(fib_cps(100000)))
```

恩，递归版本差不多被玩坏了

mailto1587

2016-02-26 23:45:34 +08:00

v2ex 文本功能太渣，放 gist 吧（ https://gist.github.com/mailto1587/827c0140e5775a986ddb ）

ShiHou

2016-02-27 04:50:01 +08:00

kevinyoung

2016-02-27 09:58:06 +08:00

@zoudm 这就是个问题怎么描述的事情，按照 @songkaiape 的说法就是每次从头开始枪毙，是 64 ，按照你的说的最后一个不直接跳过去那就是 73

qiuhanyuan

2016-02-27 10:11:42 +08:00

@zangxixi 哈哈，握爪

shuson

2016-02-27 12:32:40 +08:00 via iPhone

import fib
fib.get(10)

zangxixi

2016-02-27 18:09:50 +08:00

@shuson fib 不是 python 自带包的说

ZRS

2016-02-27 22:40:36 +08:00

还可以考虑用斐波拉契的通项公式嘛
import math
sqrtfive = math.sqrt(5)
def Fibonacci(n):
return sqrtfive/5*(math.pow(((1+sqrtfive)/2),n)-math.pow(((1-sqrtfive)/2),n))
n = 4
while n>=1:
print Fibonacci(n)
n -= 1

ZRS

2016-02-27 22:41:08 +08:00

咦缩进没了....