前些天面试碰到一道用递归求斐波那契数列第 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); //面试的时候只写了函数本身
1
aheadlead 2018-12-11 21:38:01 +08:00
|
2
rabbbit 2018-12-11 21:42:02 +08:00
递归的话,面试官应该是想往下递归,搞个哈希表缓存计算结果
例如 f(10) = f(9) + 10 = f(8) + 9 + 10 ... |
3
lhx2008 2018-12-11 21:43:25 +08:00
感觉比标准递归还慢,面试官可能想让你写动归的,通项公式的话,面试官可能会觉得,嗯,你背得很好。
|
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()); }; |
5
casparchen 2018-12-11 21:44:58 +08:00
哪儿错了,我觉得没错啊
|
6
lhx2008 2018-12-11 21:45:05 +08:00
这样写复杂度突破天际啦,传个 1000 可以算好几年
|
7
momocraft 2018-12-11 21:48:37 +08:00 1
易知 2x2 矩阵对乘法构成一个幺半群, 然后开始讲快速幂算法, 把对面的时间用光就行了
|
10
aheadlead 2018-12-11 21:51:17 +08:00
说错了,推到通项公式……(我刚在想什么 /w\..)
|
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) |
12
oncewosiwo OP @rabbbit 这个办法不错,以前刷题的时候看到过😂
|
13
oncewosiwo OP @aheadlead 是临时想了下把循环给翻译成递归了
|
15
aheadlead 2018-12-11 22:00:56 +08:00
|
16
ppyybb 2018-12-11 22:03:51 +08:00 via iPhone 1
n=1 和 n=2 答案就不对
|
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)
我也练习一下 |
18
katsusan 2018-12-11 22:18:50 +08:00
你这个是尾递归的写法吧,php 编译器有优化的话不会爆栈,直接用 f(n)=f(n-1)+f(n-2)的话有爆栈风险并且有重复计算。可以用闭包把重复计算的部分缓存起来,用空间换时间,理论上应该相当于直接正向计算 f(1),f(2),..,f()。
|
19
trait 2018-12-11 22:22:47 +08:00 1
Dasgupta,Papadimitriou, Vazirani 版本 algorithm 前言讲的就是 fibonacci,从暴力递归到矩阵和楼上的(sqrt5+1)/2 方程式,推荐去看看,以算法思想分类讲述,比市面上大多数算法书千篇一律的排序之类起手不知高到哪里去了
|
20
xml123 2018-12-11 22:41:06 +08:00
通项公式要算无理数的精确幂,不适合计算机吧,还不如递推的方案,一般还是矩阵幂二分加速吧。
|
21
oncewosiwo OP @trait 好的,我找时间去看看
|
22
SingeeKing 2018-12-11 23:16:07 +08:00
from fibonacci import fibo
print(fibo(10)) |
23
466730846 2018-12-11 23:45:43 +08:00
算法无误,只是在面试这个大背景下显得很弱~
emmmm 提一句,递归算法本身的可读性就比较差,这题应该是使用迭代算法吧~ |
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; } } |
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,速度也不慢 |
26
5yyy 2018-12-12 10:28:45 +08:00
prev = 0; curr = 1
prev , curr == curr, curr+preav |
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); } |
28
crayygy 2018-12-12 15:28:24 +08:00 via Android
|
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); |