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
zangxixi
V2EX  ›  Python

python 实现斐波那契数列

  •  
  •   zangxixi · 2016-02-26 15:19:41 +08:00 via Android · 8169 次点击
    这是一个创建于 3191 天前的主题,其中的信息可能已经有所发展或是发生改变。
    各位 pythoner 们,大家来分享用 python 实现斐波那契数列的不同做法吧!!~\(≧▽≦)/~
    59 条回复    2016-02-27 22:41:08 +08:00
    florije
        1
    florije  
       2016-02-26 15:31:29 +08:00   ❤️ 1
    def fib(n):
    a,b = 1,1
    for i in range(n-1):
    a,b = b,a+b
    return a
    print fib(5)
    先来个最简单的吧~
    MyLeoWind
        2
    MyLeoWind  
       2016-02-26 15:31:48 +08:00 via Android
    a, b = b, a+b
    这个确实是最简洁的。
    kevinyoung
        3
    kevinyoung  
       2016-02-26 15:34:01 +08:00
    送分题不做
    songkaiape
        4
    songkaiape  
       2016-02-26 15:39:40 +08:00
    @kevinyoung 有一百个人,分别从 1 一直到 100 。现在有人拿枪从第一个开始枪毙,每枪毙一个跳过一个, 一直到一轮完成。接着在活着的人里面再次枪毙第一个,间隔一个再枪毙一个,请问最后活着的是这一百个人里的第几个人?给你个有难度的=。=
    1373569162
        5
    1373569162  
       2016-02-26 15:47:43 +08:00   ❤️ 1
    俺贴个别人总结版的, 有兴趣的看下
    http://www.cnblogs.com/figure9/archive/2010/08/30/1812927.html
    还有一个求质数的有兴趣的可以实现一下
    https://program-think.blogspot.com/2011/12/prime-algorithm-1.html
    glchaos
        6
    glchaos  
       2016-02-26 15:51:39 +08:00
    @kevinyoung 不送分的题不会做,就是这么任性
    random2case
        7
    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
        8
    eote  
       2016-02-26 15:58:04 +08:00   ❤️ 1
    ```
    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
        9
    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
        10
    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
        11
    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
        12
    Lihz  
       2016-02-26 16:19:15 +08:00   ❤️ 1
    楼上的都不喜欢用 yield 构建生成器么?如果拿这做面试题,侧重的不在于能否给出答案,而是被面试者能否脑补出不同条件并构建对应方案以及在不同方案下暴露出的编程习惯吧
    Lihz
        13
    Lihz  
       2016-02-26 16:20:55 +08:00
    类似的还有素数筛选这种看似简单,但深入而言可挖掘的点是非常多的
    fulvaz
        14
    fulvaz  
       2016-02-26 16:25:59 +08:00
    斐波那契数列很多结果都可以重复利用, 只需要加个缓存, 就能有非常棒的速度

    : )
    songkaiape
        15
    songkaiape  
       2016-02-26 16:29:03 +08:00
    @jixiangqd 嗯,是不难啊,不过你为什么这样写 a=[i+1 for i in range(100)] ,直接 a=list(range(1,101))不就好了么
    songkaiape
        16
    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
        17
    livc  
       2016-02-26 16:30:38 +08:00
    @songkaiape 约瑟夫环
    jixiangqd
        18
    jixiangqd  
       2016-02-26 16:32:08 +08:00
    @songkaiape 这倒是,- -,随手写的,留了些坏习惯在代码里
    mcfog
        19
    mcfog  
       2016-02-26 16:36:25 +08:00   ❤️ 2
    在 V2EX 要大家贴派森代码简直残忍(つД`)ノ
    jixiangqd
        20
    jixiangqd  
       2016-02-26 16:40:40 +08:00
    @songkaiape 18 楼真是 Pythonic.... 突然发现我还是新手。。。水平惨不忍睹
    mikej
        21
    mikej  
       2016-02-26 17:16:13 +08:00
    @florije return 完了没输出。。
    mouer
        22
    mouer  
       2016-02-26 17:21:53 +08:00
    fib = lambda n : 1 if n <= 2 else fib(n - 1) + fib(n - 2)
    florije
        23
    florije  
       2016-02-26 17:22:34 +08:00
    @mikej 不好意思,格式都被吃了……写 python 的应该能看出来缩进吧……
    tempuseraccount
        24
    tempuseraccount  
       2016-02-26 17:25:19 +08:00
    由此工作中还真有用了 fibonacci 数列的地方。
    真使用的话还是最好把值存在数组里直接取。能少算尽量少算
    wentian
        25
    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
        26
    mikej  
       2016-02-26 17:50:33 +08:00
    @florije 怎样缩进这里都只输出了一个数嘛。。
    dofy
        27
    dofy  
       2016-02-26 17:52:24 +08:00
    可以贴 gist
    ipconfiger
        28
    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
        29
    RqPS6rhmP3Nyn3Tm  
       2016-02-26 18:18:18 +08:00 via Android
    Python 官网就有,一行搞定
    RqPS6rhmP3Nyn3Tm
        30
    RqPS6rhmP3Nyn3Tm  
       2016-02-26 18:24:34 +08:00 via Android
    来个神经病版的

    print '1,1,2,5,7,12,19,31,50'
    wellsc
        31
    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
        32
    bdbai  
       2016-02-26 19:44:29 +08:00 via iPhone
    @random2case 俺不懂 fp ,不过用递归的效率真的好吗?
    mailto1587
        33
    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
        34
    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
        35
    random2case  
       2016-02-26 20:52:22 +08:00
    @mailto1587 把俺写的这个 Int 换成 BigInt,试了下, fib(5000)瞬间出来了, 6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626 ,俺没办法把 fib(100000)贴上来,这装不下。但是也是不到一秒。
    happywowwow
        36
    happywowwow  
       2016-02-26 21:12:21 +08:00
    @BXIA
    你这数列有点奇怪...
    1,1,2,3,5,8,13
    kevinyoung
        37
    kevinyoung  
       2016-02-26 21:13:11 +08:00
    @songkaiape 第一次会把奇数编号的去掉,剩下偶数编号的全部编号除以二,再进行这个过程,所以最后剩下的那个肯定是 100 以内最“偶”的那个, 64
    shyling
        38
    shyling  
       2016-02-26 21:18:46 +08:00
    @random2case 要有尾递归优化的尾递归才有用吧=。=, py 嘛~~~~~
    kevinyoung
        39
    kevinyoung  
       2016-02-26 21:24:44 +08:00
    @bdbai 我觉得递归最大的好处是有些问题用递归的语言描述非常简洁,比如快排比如对树进行操作,但这并不总是成立的

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

    其他的语言另说,比如 Haskell 根本没有循环只能写递归,或者有些语言递归优化的好也可以。
    random2case
        40
    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
        41
    luobuda  
       2016-02-26 21:51:47 +08:00
    RqPS6rhmP3Nyn3Tm
        42
    RqPS6rhmP3Nyn3Tm  
       2016-02-26 22:08:50 +08:00 via Android
    @happywowwow 才发现…口算跳步骤习惯了…
    bdbai
        43
    bdbai  
       2016-02-26 22:10:35 +08:00 via iPhone
    @kevinyoung @random2case
    Python 对尾递归的支持我也不清楚,但我们有 yield 。
    zangxixi
        44
    zangxixi  
    OP
       2016-02-26 22:13:36 +08:00
    @eote 这种角度不错呀,但是要是我要 38 个以上肿么办?
    zangxixi
        45
    zangxixi  
    OP
       2016-02-26 22:15:04 +08:00
    @qiuhanyuan O(∩_∩)O 哈哈~这个也是我第一种写法
    random2case
        46
    random2case  
       2016-02-26 22:16:24 +08:00
    @bdbai 啊,争论哪个语言好永无止境。。。呵呵
    zangxixi
        47
    zangxixi  
    OP
       2016-02-26 22:33:31 +08:00
    @tempuseraccount 有道理,可以用动态规划
    @wentian 不会死循环吗亲?
    wentian
        48
    wentian  
       2016-02-26 22:54:12 +08:00
    @zangxixi 不会,但是注意使用方式

    递归的写法,如果没有缓存,时间效率太差了. (一行代码肯定酷,但可能也就仅止于此)
    zoudm
        49
    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
        50
    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
        51
    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
        52
    mailto1587  
       2016-02-26 23:45:34 +08:00
    v2ex 文本功能太渣,放 gist 吧( https://gist.github.com/mailto1587/827c0140e5775a986ddb
    ShiHou
        53
    ShiHou  
       2016-02-27 04:50:01 +08:00
    kevinyoung
        54
    kevinyoung  
       2016-02-27 09:58:06 +08:00
    @zoudm 这就是个问题怎么描述的事情,按照 @songkaiape 的说法就是每次从头开始枪毙,是 64 ,按照你的说的最后一个不直接跳过去那就是 73
    qiuhanyuan
        55
    qiuhanyuan  
       2016-02-27 10:11:42 +08:00
    @zangxixi 哈哈,握爪
    shuson
        56
    shuson  
       2016-02-27 12:32:40 +08:00 via iPhone
    import fib
    fib.get(10)
    zangxixi
        57
    zangxixi  
    OP
       2016-02-27 18:09:50 +08:00
    @shuson fib 不是 python 自带包的说
    ZRS
        58
    ZRS  
       2016-02-27 22:40:36 +08:00   ❤️ 1
    还可以考虑用斐波拉契的通项公式嘛
    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
        59
    ZRS  
       2016-02-27 22:41:08 +08:00
    咦缩进没了....
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3366 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 00:45 · PVG 08:45 · LAX 16:45 · JFK 19:45
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.