題目一：寫(xiě)一個(gè)函數(shù)燎竖，輸入n，求斐波那契（Fibonacci）數(shù)列的第n項(xiàng)呢袱。斐波那契數(shù)列的定義如下：（斐波那契數(shù)列由 0 和 1 開(kāi)始瓢姻，之后的斐波那契數(shù)就是由之前的兩數(shù)相加而得出。
答案需要取模 1e9+7（1000000007）延塑，如計(jì)算初始結(jié)果為：1000000008绣张，請(qǐng)返回 1。）
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
- 遞歸（效率很低的解法）
public int Fib(int n)
{
if (n == 0)
return 0;
if (n == 1)
return 1;
return Fib(n - 1) + Fib(n - 2);
}
- 循環(huán)
public int Fib(int n)
{
if (n < 2)
return n;
var num1 = 0;
var num2 = 1;
var temp = 0;
for (var i = 2; i <= n; i++)
{
temp = (num1+num2) % 1000000007;
num1 = num2;
num2 = temp;
}
return temp;
}
用不同的方法求解斐波那契數(shù)列的時(shí)間效率大不相同关带。第一種基于遞歸的解法雖然直觀但時(shí)間效率很低侥涵，在實(shí)際軟件開(kāi)發(fā)中不會(huì)用這種方法，也不可能得到面試官的青睞。第二種方法把遞歸的算法用循環(huán)實(shí)現(xiàn)芜飘，極大地提高了時(shí)間效率务豺。
