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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2173 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

return

面试

碰到

ret

29 条回复 • 2018-12-12 15:36:30 +08:00

aheadlead

2018-12-11 21:38:01 +08:00

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

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

rabbbit

2018-12-11 21:42:02 +08:00

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

lhx2008

2018-12-11 21:43:25 +08:00

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

rabbbit

2018-12-11 21:44:49 +08:00

这种才算冷门答案

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

2018-12-11 21:44:58 +08:00

哪儿错了，我觉得没错啊

lhx2008

2018-12-11 21:45:05 +08:00

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

momocraft

2018-12-11 21:48:37 +08:00

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

brainfxxk

2018-12-11 21:49:13 +08:00

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

aheadlead

2018-12-11 21:50:48 +08:00

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

aheadlead

2018-12-11 21:51:17 +08:00

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

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

2018-12-11 21:54:30 +08:00

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

oncewosiwo

2018-12-11 21:54:59 +08:00

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

lhx2008

2018-12-11 21:59:03 +08:00

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

aheadlead

2018-12-11 22:00:56 +08:00

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

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

ppyybb

2018-12-11 22:03:51 +08:00 via iPhone

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

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

2018-12-11 22:18:50 +08:00

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

trait

2018-12-11 22:22:47 +08:00

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

xml123

2018-12-11 22:41:06 +08:00

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

oncewosiwo

2018-12-11 22:43:38 +08:00

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

SingeeKing

2018-12-11 23:16:07 +08:00

from fibonacci import fibo
print(fibo(10))

466730846

2018-12-11 23:45:43 +08:00

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

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

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

2018-12-12 10:28:45 +08:00

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

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

2018-12-12 15:28:24 +08:00 via Android

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

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);