题目：斐波那契数列为：1，1，2，3，5，8…，求第n项？

初步分析

设an为斐波那契数列。a1=a2=1;（n<=2）an=a(n-1) + a(n-2);(n>=2)

本章总结

【小总结】

1.【尽量不用递归】

2.【利用数据结构】

3.【动态规划】

4.【位运算】

【详细总结】

以下代码因不同算法而时间复杂度不同个人归类为不同版本，总结如下。

1.尽量不要用递归，纵使好看，但由于递归在内存中使用的堆栈的方式，自然是浪费空间。

2.利用数据结构，数组，哈希表等优化算法。

3.以下利用到了动态规划的滚动数组。

4.用位运算来代替乘法、除法以及取模。

5.有数学公式用数学公式@.@…

详细代码

using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;using System.Diagnostics;namespace Fibonacci_Sequence{class Program{/// <summary>/// 垃圾递归fun1/// </summary>/// <param name="n">数值n</param>/// <returns>第n项的值</returns>static int fun1(int n){if (n == 1 || n == 2) return 1;else return fun1(n - 1) + fun1(n - 2);}/// <summary>/// 数组存储/// </summary>/// <param name="n">数值n</param>/// <returns>第n项的值</returns>static int fun2(int n){if (n == 1 || n == 2)return 1;else{int[] array = new int[n + 1];array[1] = array[2] = 1;for (int i = 3; i < n + 1; i++){array[i] = array[i - 1] + array[i - 2];}return array[n];}}/// <summary>/// 滚动数组简单版1/// </summary>/// <param name="n">数值n</param>/// <returns>第n项的值</returns>static int fun3(int n){if (n == 1 || n == 2)return 1;else{int[] array = new int[2];array[0] = array[1] = 1;for (int i = 2; i < n; i++){array[1] = array[0] + array[1];array[0] = array[1] - array[0];}return array[1];}}/// <summary>/// 滚动数组简单版2/// </summary>/// <param name="n">数值n</param>/// <returns>第n项的值</returns>static int fun4(int n){if (n == 1 || n == 2)return 1;else{int[] array = new int[2];array[0] = array[1] = 1;for (int i = 2; i < n; i++){array[i % 2] = array[(i-1) % 2] + array[(i - 2) % 2];}return array[(n+1) % 2];//或//for (int i = 3; i <= n; i++)//{// array[i % 2] = array[(i - 1) % 2] + array[(i - 2) % 2];//}//return array[n % 2];}}/// <summary>/// 滚动数组逻辑与版本/// </summary>/// <param name="n">数值n</param>/// <returns>第n项的值</returns>static int fun5(int n){if (n == 1 || n == 2)return 1;else{int[] array = new int[2];array[0] = array[1] = 1;for (int i = 3; i <= n; i++){array[i & 1] = array[(i - 1) & 1] + array[(i - 2) & 1];}return array[n & 1];}}static void Main(string[] args){int n = int.Parse(Console.ReadLine().ToString());//获取数据nConsole.WriteLine("fun1用时间" + getCostTime(fun1, n)+"\n");//输出耗费时长Console.WriteLine("fun1用时间" + getCostTime(fun2, n) + "\n");//输出耗费时长Console.WriteLine("fun1用时间" + getCostTime(fun3, n) + "\n");//输出耗费时长Console.WriteLine("fun1用时间" + getCostTime(fun4, n) + "\n");//输出耗费时长Console.WriteLine("fun1用时间" + getCostTime(fun5, n) + "\n");//输出耗费时长Console.ReadLine();}/// <summary> /// 获取此方法的耗费时间 /// </summary>/// <param name="function">方法</param>/// <param name="n">数值</param>/// <returns>耗费时间</returns>static long getCostTime(Func<int, int> function, int n){Stopwatch sw = new Stopwatch();sw.Start();Console.WriteLine("值：" +function(n));sw.Stop();return sw.ElapsedMilliseconds;}}}