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时会内存溢出。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。