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

[oncewosiwo]

前些天面试碰到一道用递归求斐波那契数列第 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);  //面试的时候只写了函数本身

[aheadlead]

这真的做错了… 你这其实和写个 for loop 没啥区别

其实可以用通项公式啊： https://www.jianshu.com/p/946eb441dce5

[rabbbit]

递归的话,面试官应该是想往下递归,搞个哈希表缓存计算结果
例如
f(10) = f(9) + 10 = f(8) + 9 + 10 ...

[lhx2008]

感觉比标准递归还慢，面试官可能想让你写动归的，通项公式的话，面试官可能会觉得，嗯，你背得很好。

[rabbbit]

这种才算冷门答案

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]

哪儿错了，我觉得没错啊

[lhx2008]

这样写复杂度突破天际啦，传个 1000 可以算好几年

[momocraft]

易知 2x2 矩阵对乘法构成一个幺半群, 然后开始讲快速幂算法, 把对面的时间用光就行了

[brainfxxk]

@lhx2008 复杂度有什么问题？虽然 lz 这代码确实挺烂的

[aheadlead]

@lhx2008 #3 现场给他啪通项公式

[aheadlead]

说错了，推到通项公式……（我刚在想什么 /w\..）

[rabbbit]

搞错了
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]

@rabbbit 这个办法不错，以前刷题的时候看到过😂

[oncewosiwo]

@aheadlead 是临时想了下把循环给翻译成递归了

[lhx2008]

@brainfxxk 看错了，这应该是类似一种尾递归的写法，复杂度没问题

[aheadlead]

@oncewosiwo #13 这没啥意义啊...

@lhx2008 #14 不知道他这是啥具体语言…如果是 php 的话，貌似都没有尾递归优化

[ppyybb]

n=1 和 n=2 答案就不对

[CatcherO]

const fb = n => (n===1 || n===2) ? 1 : fb(n-1)+fb(n-2)
我也练习一下

[katsusan]

你这个是尾递归的写法吧，php 编译器有优化的话不会爆栈，直接用 f(n)=f(n-1)+f(n-2)的话有爆栈风险并且有重复计算。可以用闭包把重复计算的部分缓存起来，用空间换时间，理论上应该相当于直接正向计算 f(1),f(2),..,f()。

[trait]

Dasgupta,Papadimitriou, Vazirani 版本 algorithm 前言讲的就是 fibonacci，从暴力递归到矩阵和楼上的(sqrt5+1)/2 方程式，推荐去看看，以算法思想分类讲述，比市面上大多数算法书千篇一律的排序之类起手不知高到哪里去了

[xml123]

通项公式要算无理数的精确幂，不适合计算机吧，还不如递推的方案，一般还是矩阵幂二分加速吧。

[oncewosiwo]

@trait 好的，我找时间去看看

[SingeeKing]

from fibonacci import fibo
print(fibo(10))

[466730846]

算法无误，只是在面试这个大背景下显得很弱~
emmmm 提一句，递归算法本身的可读性就比较差，这题应该是使用迭代算法吧~

[zjp]

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

还是 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]

prev = 0; curr = 1
prev , curr == curr, curr+preav

[exonuclease]

可能是想要这样的？
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]

https://blog.crayygy.com/14599905787744.html

[Fate810]

function get_fb($n){
if($n==1 || $n==2){
return 1;
}
return get_fb($n-1)+get_fb($n-2);
}
echo get_fb(10);