一、题目：斐波那契数列
题目：写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列的定义如下：
二、效率很低的解法
很多C/C++/C#/Java语言教科书在讲述递归函数的时候，大多都会用Fibonacci作为例子，因此我们会对这种解法烂熟于心：
public static long FibonacciRecursively(uint n)
{
if (n <= )
{
return ;
}
if (n == )
{
return ;
} return FibonacciRecursively(n - ) + FibonacciRecursively(n - );
}
上述递归的解法有很严重的效率问题，通过求解第10项的调用过程图来分析：
从上图中不难发现：在这棵树中有很多结点是重复的，而且重复的结点数会随着n的增大而急剧增加，这意味计算量会随着n的增大而急剧增大。事实上，用递归方法计算的时间复杂度是以n的指数的方式递增的。
三、实用循环的解法
改进的方法并不复杂。上述递归代码之所以慢是因为重复的计算太多，我们只要想办法避免重复计算就行了。这里的办法是从下往上计算，首先根据f(0)和f(1)算出f(2)，再根据f(1)和f(2)算出f(3)……依此类推就可以算出第n项了。很容易理解，这种思路的时间复杂度是O(n)。
public static long FibonacciIteratively(uint n)
{
int[] result = { , };
if (n < )
{
return result[n];
} long fibNMinusOne = ;
long fibNMinusTwo = ;
long fibN = ; for (uint i = ; i <= n; i++)
{
fibN = fibNMinusOne + fibNMinusTwo; fibNMinusTwo = fibNMinusOne;
fibNMinusOne = fibN;
} return fibN;
}
四、单元测试
（1）单元测试用例
[TestMethod]
public void FibonacciTest1()
{
Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(),);
} [TestMethod]
public void FibonacciTest2()
{
Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(), );
} [TestMethod]
public void FibonacciTest3()
{
Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(), );
} [TestMethod]
public void FibonacciTest4()
{
Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(), );
} [TestMethod]
public void FibonacciTest5()
{
Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(), );
} [TestMethod]
public void FibonacciTest6()
{
Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(), );
} [TestMethod]
public void FibonacciTest7()
{
Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(), );
} [TestMethod]
public void FibonacciTest8()
{
Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(), );
} [TestMethod]
public void FibonacciTest9()
{
Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(), );
} [TestMethod]
public void FibonacciTest10()
{
Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(), );
} [TestMethod]
public void FibonacciTest11()
{
Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(), );
} [TestMethod]
public void FibonacciTest12()
{
Assert.AreEqual(FibonaaciHelper.FibonacciIteratively(), );
}
（2）单元测试结果
①测试通过结果
②代码覆盖率