python 实现斐波那契数列

[zangxixi]

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

[florije]

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

[MyLeoWind]

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

[kevinyoung]

送分题不做

[songkaiape]

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

[1373569162]

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

[glchaos]

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

[random2case]

俺喜欢斐波那契数列，先来一个 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]

```
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]

@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]

重新贴一下程序
```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]

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

[Lihz]

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

[Lihz]

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

[fulvaz]

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

: )

[songkaiape]

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

[songkaiape]

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

[livc]

@songkaiape 约瑟夫环

[jixiangqd]

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

[mcfog]

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

[jixiangqd]

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

[mikej]

@florije return 完了没输出。。

[mouer]

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

[florije]

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

[tempuseraccount]

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

[wentian]

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

[mikej]

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

[dofy]

可以贴 gist

[ipconfiger]

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]

Python 官网就有，一行搞定

[RqPS6rhmP3Nyn3Tm]

来个神经病版的

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

[wellsc]

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

[bdbai]

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

[mailto1587]

递归不 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]

@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]

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

[happywowwow]

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

[kevinyoung]

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

[shyling]

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

[kevinyoung]

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

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

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

[random2case]

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

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

[luobuda]

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

[RqPS6rhmP3Nyn3Tm]

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

[bdbai]

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

[zangxixi]

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

[zangxixi]

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

[random2case]

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

[zangxixi]

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

[wentian]

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

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

[zoudm]

@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]

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]

@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]

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

[ShiHou]

<script src="https://gist.github.com/Lyken17/5bffba48807fea6efd77.js"></script>

[kevinyoung]

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

[qiuhanyuan]

@zangxixi 哈哈，握爪

[shuson]

import fib
fib.get(10)

[zangxixi]

@shuson fib 不是 python 自带包的说

[ZRS]

还可以考虑用斐波拉契的通项公式嘛
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]

咦缩进没了....