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

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