题目一：写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列的定义如下：（斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 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);
}
- 循环
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;
}
用不同的方法求解斐波那契数列的时间效率大不相同。第一种基于递归的解法虽然直观但时间效率很低，在实际软件开发中不会用这种方法，也不可能得到面试官的青睐。第二种方法把递归的算法用循环实现，极大地提高了时间效率。
