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

面试碰到求斐波那契数列第 n 项

  •  
  •   oncewosiwo · 2018-12-11 21:33:18 +08:00 · 4311 次点击
    这是一个创建于 2174 天前的主题,其中的信息可能已经有所发展或是发生改变。

    前些天面试碰到一道用递归求斐波那契数列第 n 项的题目,写了个非标准答案,结果被认为做错了😓

    function fb($a,$b,$n){
        $c = $a+$b;
        if($n>0){
            return fb($b,$c,--$n);
        }
        return $c;
    }
    
    $n = 10;
    $ret = fb(1,1,$n-3);  //面试的时候只写了函数本身
    
    29 条回复    2018-12-12 15:36:30 +08:00
    aheadlead
        1
    aheadlead  
       2018-12-11 21:38:01 +08:00
    这真的做错了… 你这其实和写个 for loop 没啥区别

    其实可以用通项公式啊: https://www.jianshu.com/p/946eb441dce5
    rabbbit
        2
    rabbbit  
       2018-12-11 21:42:02 +08:00
    递归的话,面试官应该是想往下递归,搞个哈希表缓存计算结果
    例如
    f(10) = f(9) + 10 = f(8) + 9 + 10 ...
    lhx2008
        3
    lhx2008  
       2018-12-11 21:43:25 +08:00
    感觉比标准递归还慢,面试官可能想让你写动归的,通项公式的话,面试官可能会觉得,嗯,你背得很好。
    rabbbit
        4
    rabbbit  
       2018-12-11 21:44:49 +08:00   ❤️ 2
    这种才算冷门答案

    var climbStairs = function (n) {
    let sqrt5 = Math.sqrt(5);
    let result = (Math.pow(((1 + sqrt5) / 2), n + 1) - Math.pow(((1 - sqrt5) / 2), n + 1)) / sqrt5;
    return Number(result.toFixed());
    };
    casparchen
        5
    casparchen  
       2018-12-11 21:44:58 +08:00
    哪儿错了,我觉得没错啊
    lhx2008
        6
    lhx2008  
       2018-12-11 21:45:05 +08:00
    这样写复杂度突破天际啦,传个 1000 可以算好几年
    momocraft
        7
    momocraft  
       2018-12-11 21:48:37 +08:00   ❤️ 1
    易知 2x2 矩阵对乘法构成一个幺半群, 然后开始讲快速幂算法, 把对面的时间用光就行了
    brainfxxk
        8
    brainfxxk  
       2018-12-11 21:49:13 +08:00
    @lhx2008 复杂度有什么问题?虽然 lz 这代码确实挺烂的
    aheadlead
        9
    aheadlead  
       2018-12-11 21:50:48 +08:00
    @lhx2008 #3 现场给他啪通项公式
    aheadlead
        10
    aheadlead  
       2018-12-11 21:51:17 +08:00
    说错了,推到通项公式……(我刚在想什么 /w\..)
    rabbbit
        11
    rabbbit  
       2018-12-11 21:53:06 +08:00
    搞错了
    f(10) = f(9) + 10 = f(8) + 9 + 10 ...
    -->
    应该是想要这种解法
    f(0) = 0
    f(1) = 1
    f(2) = f(0) + f(1)
    f(3) = f(1) + f(2)

    f(n) = f(n - 2) + f(n - 1)
    oncewosiwo
        12
    oncewosiwo  
    OP
       2018-12-11 21:54:30 +08:00
    @rabbbit 这个办法不错,以前刷题的时候看到过😂
    oncewosiwo
        13
    oncewosiwo  
    OP
       2018-12-11 21:54:59 +08:00
    @aheadlead 是临时想了下把循环给翻译成递归了
    lhx2008
        14
    lhx2008  
       2018-12-11 21:59:03 +08:00
    @brainfxxk 看错了,这应该是类似一种尾递归的写法,复杂度没问题
    aheadlead
        15
    aheadlead  
       2018-12-11 22:00:56 +08:00
    @oncewosiwo #13 这没啥意义啊...

    @lhx2008 #14 不知道他这是啥具体语言…如果是 php 的话,貌似都没有尾递归优化
    ppyybb
        16
    ppyybb  
       2018-12-11 22:03:51 +08:00 via iPhone   ❤️ 1
    n=1 和 n=2 答案就不对
    CatcherO
        17
    CatcherO  
       2018-12-11 22:15:58 +08:00 via Android
    const fb = n => (n===1 || n===2) ? 1 : fb(n-1)+fb(n-2)
    我也练习一下
    katsusan
        18
    katsusan  
       2018-12-11 22:18:50 +08:00
    你这个是尾递归的写法吧,php 编译器有优化的话不会爆栈,直接用 f(n)=f(n-1)+f(n-2)的话有爆栈风险并且有重复计算。可以用闭包把重复计算的部分缓存起来,用空间换时间,理论上应该相当于直接正向计算 f(1),f(2),..,f()。
    trait
        19
    trait  
       2018-12-11 22:22:47 +08:00   ❤️ 1
    Dasgupta,Papadimitriou, Vazirani 版本 algorithm 前言讲的就是 fibonacci,从暴力递归到矩阵和楼上的(sqrt5+1)/2 方程式,推荐去看看,以算法思想分类讲述,比市面上大多数算法书千篇一律的排序之类起手不知高到哪里去了
    xml123
        20
    xml123  
       2018-12-11 22:41:06 +08:00
    通项公式要算无理数的精确幂,不适合计算机吧,还不如递推的方案,一般还是矩阵幂二分加速吧。
    oncewosiwo
        21
    oncewosiwo  
    OP
       2018-12-11 22:43:38 +08:00
    @trait 好的,我找时间去看看
    SingeeKing
        22
    SingeeKing  
       2018-12-11 23:16:07 +08:00
    from fibonacci import fibo
    print(fibo(10))
    466730846
        23
    466730846  
       2018-12-11 23:45:43 +08:00
    算法无误,只是在面试这个大背景下显得很弱~
    emmmm 提一句,递归算法本身的可读性就比较差,这题应该是使用迭代算法吧~
    zjp
        24
    zjp  
       2018-12-11 23:45:50 +08:00
    @rabbbit 来个更冷门的...

    public int Fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    boolean even = n % 2 == 0;
    int k = even ? n / 2 : (n + 1) / 2;
    int fib1 = Fibonacci(k);
    int fib0 = Fibonacci(k - 1);
    return even ? (fib1 + fib0 * 2) * fib1 : fib1 * fib1 + fib0 * fib0;
    }
    }
    arzterk
        25
    arzterk  
       2018-12-12 09:05:24 +08:00
    还是 haskell 的直观,和伪代码没区别:
    fib :: (Num a1, Num a, Eq a1) => a1 -> a
    fib n
    | (n == 0) = a
    | (n == 1) = b
    | otherwise = fib (n - 1) + fib (n - 2)
    where a = 1; b = 1

    更简单的写法是用 lazy infinite list :
    fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
    取前 n 个就是
    take n fibs

    编译器自动 cps,速度也不慢
    5yyy
        26
    5yyy  
       2018-12-12 10:28:45 +08:00
    prev = 0; curr = 1
    prev , curr == curr, curr+preav
    exonuclease
        27
    exonuclease  
       2018-12-12 14:52:17 +08:00
    可能是想要这样的?
    vector<unsigned long long> fib(int n)
    {
    vector<unsigned long long> vec(n);
    for (int i = 0; i < n; i++)
    {
    if (i <= 1)
    {
    vec[i] = 1;
    }
    else
    {
    vec[i] = vec[i - 1] + vec[i - 2];
    }
    }
    return std::move(vec);
    }
    crayygy
        28
    crayygy  
       2018-12-12 15:28:24 +08:00 via Android
    Fate810
        29
    Fate810  
       2018-12-12 15:36:30 +08:00
    function get_fb($n){
    if($n==1 || $n==2){
    return 1;
    }
    return get_fb($n-1)+get_fb($n-2);
    }
    echo get_fb(10);
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2851 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 14:11 · PVG 22:11 · LAX 06:11 · JFK 09:11
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.