V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Jakesoft
V2EX  ›  PHP

我是这么实现斐波那契数列的

  •  
  •   Jakesoft · 2017-01-03 16:21:15 +08:00 · 6129 次点击
    这是一个创建于 2863 天前的主题,其中的信息可能已经有所发展或是发生改变。

    实习时面试面到这个问题,当时还不知道斐波那契数列,讲给同学听时,他说,这不就是斐波那契数列吗?! (尴尬脸)

    然后这是我面试的回答:

    $total = [0, 1];
    
    for ($i = 2; $i < 100; $i++)
    {
    	$total[] = $total[$i - 1] + $total[$i - 2];
    }
    

    今天看到别人(书本)的实现,需要定义几个变量来交换当前值、上一个值,感觉好麻烦。

    还有我的代码应该没啥问题吧

    第 1 条附言  ·  2017-01-03 19:51:17 +08:00
    感谢大家提供的不同的思路和看法,本来只是一个秀代码的帖子,竟然引发了诸多讨论。

    我没有怎么在意内存消耗、时间复杂度的问题,看来这方面确实还需要学习一个啊。

    @loggerhead 的文章让我大开眼界,谢谢!
    48 条回复    2017-01-05 11:24:28 +08:00
    laoyuan
        1
    laoyuan  
       2017-01-03 16:30:47 +08:00
    新年刚开始又来黑 PHP 。。总之不用递归都是好的
    superYy
        2
    superYy  
       2017-01-03 16:35:04 +08:00
    性能低!应该创建一个缓冲数组存贮之前的值
    misaka19000
        3
    misaka19000  
       2017-01-03 16:36:05 +08:00 via Android
    还行,不过不是非得用数组吧
    GPIO
        4
    GPIO  
       2017-01-03 16:45:20 +08:00
    中学学数列的时候都会讲到斐波那契数列的啊,你是不是当时没好好听课。。。
    superYy
        5
    superYy  
       2017-01-03 16:48:49 +08:00
    @superYy 没仔细看,之前说错了
    gisonrg
        6
    gisonrg  
       2017-01-03 17:02:00 +08:00 via iPhone
    不用数组只用两个变量可以省空间→_→
    mrgeneral
        7
    mrgeneral  
       2017-01-03 17:17:06 +08:00
    算法没啥问题啊。

    前面的存下来没啥意义, echo 输出了吧,换成俩变量,节省空间。
    SteveLee
        8
    SteveLee  
       2017-01-03 17:26:25 +08:00 via iPhone
    矩阵快速 mi
    dtfm
        9
    dtfm  
       2017-01-03 17:46:16 +08:00 via Android   ❤️ 1
    fib 不应该这样么? a, b = b , a+b
    em2046
        10
    em2046  
       2017-01-03 17:49:34 +08:00
    没毛病
    为啥不用递归呢
    PS :递归也可以不是 O(2^n)
    akira
        11
    akira  
       2017-01-03 18:04:57 +08:00
    没问题。只是当 N 比较大的时候,会略尴尬
    q397064399
        12
    q397064399  
       2017-01-03 18:09:32 +08:00
    @em2046 空间复杂度为 O(2^n) 递归过深,直接爆栈,所以才有了 stackoverflow.com
    q397064399
        13
    q397064399  
       2017-01-03 18:12:10 +08:00
    @em2046 递归调用每一次 call ,按照计算机的函数堆栈模型,栈帧要向下延伸,然后栈容量不够用的时候,就直接爆了
    q397064399
        14
    q397064399  
       2017-01-03 18:13:45 +08:00
    一般问菲波那切数列的话,都会接着问 栈溢出的问题,
    如果不知道函数递归调用过深导致的爆栈问题,就会略显尴尬了
    loggerhead
        15
    loggerhead  
       2017-01-03 18:18:16 +08:00   ❤️ 6
    可以看看我这篇文章——求 Fibonacci 数列的 N 种算法: https://loggerhead.me/posts/qiu-fibonacci-shu-lie-de-n-chong-suan-fa.html
    xjp
        16
    xjp  
       2017-01-03 18:25:44 +08:00 via iPhone
    没有问题
    assad
        17
    assad  
       2017-01-03 18:25:47 +08:00
    import numpy

    def mm_fib(n):
    return (numpy.matrix([[2,1],[1,1]])**(n//2))[0,(n+1)%2]

    [mm_fib(i) for i in range(20)]
    Kilerd
        18
    Kilerd  
       2017-01-03 18:35:11 +08:00
    @loggerhead

    > 重复平方技术也可以用在求 Fibonacci 数上。

    可行吗?? 我想了一下,好像没有什么思路。 求指点。
    loggerhead
        19
    loggerhead  
       2017-01-03 18:39:55 +08:00
    @Kilerd 文章中有写。比如: 2^8 = 2^4 * 2^4 就只用算一次 2^4 和一次乘法,时间复杂度降到了 O(logn)
    Contextualist
        20
    Contextualist  
       2017-01-03 18:43:08 +08:00 via iPad
    @Kilerd 文章中下面的矩阵乘法和代数方法就是“重复平方”(其实就是乘法结合律)的具体实现
    raysonx
        21
    raysonx  
       2017-01-03 18:45:21 +08:00
    话说如果只是要求求出某一个 Fibonacci 数而不是整个数列的话,可以直接用公式在 O(1)的时间内求得。
    xiaopc
        22
    xiaopc  
       2017-01-03 18:58:05 +08:00 via Android
    @Kilerd 线性递推先构造出矩阵,然后用矩阵乘法结合律降次
    SplendentDraco
        23
    SplendentDraco  
       2017-01-03 19:00:09 +08:00 via Android
    我记得高一时上课时无聊吧这玩意儿通项公式求出来了。。😂
    choury
        24
    choury  
       2017-01-03 19:02:57 +08:00
    @raysonx 公式里面全是无理数,计算机直接算不好吧
    Kilerd
        25
    Kilerd  
       2017-01-03 19:06:41 +08:00
    @loggerhead 重复平方,我懂。

    @Contextualist @xiaopc GET 到了。 矩阵方法确实神奇。 至于代数方法,感觉是像是把矩阵方法拆开些而已。

    完蛋了,现在看博客都专心不了了。
    chuanqirenwu
        26
    chuanqirenwu  
       2017-01-03 19:09:52 +08:00
    这个面试比较蛋疼,他是要考察你什么呢?斐波拉契数列的定义?还是高效的代码实现?
    Cbdy
        27
    Cbdy  
       2017-01-03 19:15:37 +08:00
    @raysonx 我想了一下没想出来怎么在 O(1)时间内求出来。通项是无理数,比如 n 很大,算出来的精度就很可疑了。有什么好方法吗? O(1)
    blackjar
        28
    blackjar  
       2017-01-03 19:15:38 +08:00
    @q397064399 尾递归打开优化 没区别
    Jakesoft
        29
    Jakesoft  
    OP
       2017-01-03 19:38:30 +08:00
    @GPIO 可能是忘记了吧,不过大学确实很少上课。。。
    h4x3rotab
        30
    h4x3rotab  
       2017-01-03 19:40:01 +08:00 via iPhone
    @Cbdy 快速矩阵幂, O(logn)
    Jakesoft
        31
    Jakesoft  
    OP
       2017-01-03 19:42:18 +08:00
    @chuanqirenwu 应该是如何实现“后面一个数等于前两个数之和”吧,至于如何高效实现我还需要花点功夫。
    manongvpn
        32
    manongvpn  
       2017-01-03 19:45:22 +08:00
    会 Google ,你就离大牛近了一步。
    bdbai
        33
    bdbai  
       2017-01-03 20:06:04 +08:00 via Android
    @loggerhead 弱弱问一下,你的博客文章中矩阵为什么乘在向量的右边?
    CFM880
        34
    CFM880  
       2017-01-03 20:17:51 +08:00
    看下 sicp 里面就有,树形递归和线性迭代,书上讲两种过程的优缺点说的很清楚
    j5shi
        35
    j5shi  
       2017-01-03 20:21:53 +08:00 via iPhone
    @q397064399 这么浅显的问题要是面试官顺着你的思路真的问了那只能恭喜你局面被你控制了😄
    loggerhead
        36
    loggerhead  
       2017-01-03 20:35:47 +08:00
    @bdbai 这不是矩阵乘法吗? 1x2 乘以 2x2 的矩阵 = 1x2 的矩阵。你可以看看这个: http://www.ruanyifeng.com/blog/2015/09/matrix-multiplication.html
    owt5008137
        37
    owt5008137  
       2017-01-03 21:09:19 +08:00 via Android
    用矩阵,斐波那契的复杂度是 O ( log ( n ))
    ZRS
        38
    ZRS  
       2017-01-03 21:20:33 +08:00
    用通项公式...
    q397064399
        39
    q397064399  
       2017-01-04 08:15:44 +08:00
    @j5shi 我会说很多程序员 并不知道 程序堆栈这回事么?
    longhao
        40
    longhao  
       2017-01-04 09:21:56 +08:00 via iPhone
    @q397064399 尝试尾递归呢
    q397064399
        41
    q397064399  
       2017-01-04 09:31:07 +08:00
    @longhao 主要看汇编层面的优化吧,毕竟生成机器码,底层是怎么运作的,高级语言很难解释清楚
    一般是不推荐使用过深的递归,
    MayLava
        42
    MayLava  
       2017-01-04 11:03:30 +08:00
    说到斐波那契数列,大家肯定记得“生兔子问题”。题目很绕。

    一只小兔子,出生三个月变大兔子,变成大兔子后每个月生一只小兔子;
    小兔子三个月后也能变成大兔子开始生小兔子。
    问 n 个月后一共有几只兔子。

    我完全被搞蒙了——这尼玛什么鬼。
    我还觉得这题目有歧义啊,比如说长成大兔子的当月就能生小兔子吗还是下个月才能生小兔子。
    你想啊,这个月长成大兔子,难道不需要怀胎一个月吗?
    然后生兔子我们是不是按一半男一半女算?两只兔子一个月生一只才对吧?
    然后我还在想兔子真的繁殖能力这么强吗?

    然后我画了一下午“生兔子”的图。
    然后我还用了各种奇怪的方法模拟兔子成长过程什么的,总之这题没写出来。

    后来才知道这就是斐波那契数列。迭代 a, b = b, a + b 就行了。
    然后我就觉得,要考斐波那契就老老实实的说你要考斐波那契,我会就是会,不会我就学。
    求你不要搞些奇奇怪怪的描述来忽悠人了😂😂😂😂
    bdbai
        43
    bdbai  
       2017-01-04 18:22:32 +08:00 via Android
    @loggerhead 按照阮老师的写法,变换矩阵乘在向量左边的,高中数学书上也这么写......
    loggerhead
        44
    loggerhead  
       2017-01-04 19:58:03 +08:00
    @bdbai 没搞懂你什么意思……矩阵乘法不满足交换律的,所以如果我写反了,那么我就写错了,但是我仔细看了看,好像没问题啊……
    bdbai
        45
    bdbai  
       2017-01-04 20:23:01 +08:00 via Android
    @loggerhead 抱歉我看错了,原来是横着写的😂
    loggerhead
        46
    loggerhead  
       2017-01-04 21:44:02 +08:00   ❤️ 1
    @bdbai 哈哈😂
    yzhen123
        47
    yzhen123  
       2017-01-05 08:53:53 +08:00
    @MayLava 这种题目考察的是语言理解能力,这么 简单的描述都没看懂,以后读产品经理的需求怎么办?(手动滑稽
    ryd994
        48
    ryd994  
       2017-01-05 11:24:28 +08:00
    @blackjar fib 要求 n-1 和 n-2 ,不是尾递归
    如果是存在尾递归,则必然可以重写为循环,因为编译器就是这么干的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1059 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 33ms · UTC 22:43 · PVG 06:43 · LAX 14:43 · JFK 17:43
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.