python 实现斐波那契数列

[zangxixi]

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

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

咦缩进没了....