C#实现斐波那契数列的几种方法整理

什么是斐波那契数列？经典数学问题之一；斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……想必看到这个数列大家很容易的就推算出来后面好几项的值，那么到底有什么规律，简单说，就是前两项的和是第三项的值，用递归算法计第50位多少。

这个数列从第3项开始，每一项都等于前两项之和。

斐波那契数列：｛1,1,2,3,5,8,13,21...｝

递归算法，耗时最长的算法，效率很低。

public static long CalcA(int n)
{
 if (n <= 0) return 0;
 if (n <= 2) return 1;
 return checked(CalcA(n - 2) + CalcA(n - 1));
}

通过循环来实现

public static long CalcB(int n)
{
 if (n <= 0) return 0;
 var a = 1L;
 var b = 1L;
 var result = 1L;
 for (var i = 3; i <= n; i++)
 {
   result = checked(a + b);
   a = b;
   b = result;
 }
 return result;
}

通过循环的改进写法

public static long CalcC(int n)
{
 if (n <= 0) return 0;
 var a = 1L;
 var b = 1L;
 for (var i = 3; i <= n; i++)
 {
   b = checked(a + b);
   a = b - a;
 }
 return b;
}

通用公式法

/// <summary>
/// F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public static long CalcD(int n)
{
 if (n <= 0) return 0;
 if (n <= 2) return 1; //加上，可减少运算。
 var a = 1 / Math.Sqrt(5);
 var b = Math.Pow((1 + Math.Sqrt(5)) / 2, n);
 var c = Math.Pow((1 - Math.Sqrt(5)) / 2, n);
 return checked((long)(a * (b - c)));
}

其他方法

using System;
using System.Diagnostics;

namespace Fibonacci
{
 class Program
 {
   static void Main(string[] args)
   {
     ulong result;

int number = 10;
     Console.WriteLine("************* number={0} *************", number);

Stopwatch watch1 = new Stopwatch();
     watch1.Start();
     result = F1(number);
     watch1.Stop();
     Console.WriteLine("F1({0})=" + result + " 耗时：" + watch1.Elapsed, number);

Stopwatch watch2 = new Stopwatch();
     watch2.Start();
     result = F2(number);
     watch2.Stop();
     Console.WriteLine("F2({0})=" + result + " 耗时：" + watch2.Elapsed, number);

Stopwatch watch3 = new Stopwatch();
     watch3.Start();
     result = F3(number);
     watch3.Stop();
     Console.WriteLine("F3({0})=" + result + " 耗时：" + watch3.Elapsed, number);

Stopwatch watch4 = new Stopwatch();
     watch4.Start();
     double result4 = F4(number);
     watch4.Stop();
     Console.WriteLine("F4({0})=" + result4 + " 耗时：" + watch4.Elapsed, number);

Console.WriteLine();

Console.WriteLine("结束");
     Console.ReadKey();
   }

/// <summary>
   /// 迭代法
   /// </summary>
   /// <param name="number"></param>
   /// <returns></returns>
   private static ulong F1(int number)
   {
     if (number == 1 || number == 2)
     {
       return 1;
     }
     else
     {
       return F1(number - 1) + F1(number - 2);
     }

}

/// <summary>
   /// 直接法
   /// </summary>
   /// <param name="number"></param>
   /// <returns></returns>
   private static ulong F2(int number)
   {
     ulong a = 1, b = 1;
     if (number == 1 || number == 2)
     {
       return 1;
     }
     else
     {
       for (int i = 3; i <= number; i++)
       {
         ulong c = a + b;
         b = a;
         a = c;
       }
       return a;
     }
   }

/// <summary>
   /// 矩阵法
   /// </summary>
   /// <param name="n"></param>
   /// <returns></returns>
   static ulong F3(int n)
   {
     ulong[,] a = new ulong[2, 2] { { 1, 1 }, { 1, 0 } };
     ulong[,] b = MatirxPower(a, n);
     return b[1, 0];
   }

#region F3
   static ulong[,] MatirxPower(ulong[,] a, int n)
   {
     if (n == 1) { return a; }
     else if (n == 2) { return MatirxMultiplication(a, a); }
     else if (n ％ 2 == 0)
     {
       ulong[,] temp = MatirxPower(a, n / 2);
       return MatirxMultiplication(temp, temp);
     }
     else
     {
       ulong[,] temp = MatirxPower(a, n / 2);
       return MatirxMultiplication(MatirxMultiplication(temp, temp), a);
     }
   }

static ulong[,] MatirxMultiplication(ulong[,] a, ulong[,] b)
   {
     ulong[,] c = new ulong[2, 2];
     for (int i = 0; i < 2; i++)
     {
       for (int j = 0; j < 2; j++)
       {
         for (int k = 0; k < 2; k++)
         {
           c[i, j] += a[i, k] * b[k, j];
         }
       }
     }
     return c;
   }
   #endregion

/// <summary>
   /// 通项公式法
   /// </summary>
   /// <param name="n"></param>
   /// <returns></returns>
   static double F4(int n)
   {
     double sqrt5 = Math.Sqrt(5);
     return (1/sqrt5*(Math.Pow((1+sqrt5)/2,n)-Math.Pow((1-sqrt5)/2,n)));
   }
 }
}

OK，就这些了。用的long类型来存储结果，当n>92时会内存溢出。

来源：https://www.jianshu.com/p/31b783e3eb46