一聚教程网:一个值得你收藏的教程网站

最新下载

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

时间:2018-09-21 11:36:02 编辑:猪哥 来源:转载

什么是斐波那契数列?经典数学问题之一;斐波那契数列,又称黄金分割数列,指的是这样一个数列: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;
}

通用公式法

/// 
/// F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}
/// 
/// 
/// 
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();
    }

    /// 
    /// 迭代法
    /// 
    /// 
    /// 
    private static ulong F1(int number)
    {
      if (number == 1 || number == 2)
      {
        return 1;
      }
      else
      {
        return F1(number - 1) + F1(number - 2);
      }
      
    }

    /// 
    /// 直接法
    /// 
    /// 
    /// 
    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;
      }
    }

    /// 
    /// 矩阵法
    /// 
    /// 
    /// 
    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

    /// 
    /// 通项公式法
    /// 
    /// 
    /// 
    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时会内存溢出。

文章评论

热门栏目

马会一码爆料 泸西县| 元氏县| 龙口市| 房山区| 佳木斯市| 鄂托克旗| 中宁县| 广德县| 西和县| 洛川县| 沈阳市| 民县| 平塘县| 饶阳县| 巩留县| 清水县| 萝北县| 博湖县| 民权县| 大厂| 钟山县| 西畴县| 宁晋县| 遵化市| 铜川市| 栾城县| http://www.iiiwny.cn 石嘴山市| 思南县| 怀化市| 买车| 岳池县| 新密市| 攀枝花市| 富民县| 浦江县| 栖霞市| 宁河县| 林口县| 汝南县| 剑川县| 尼玛县| 象州县| 镶黄旗| 汉川市| 宜良县| 彩票| 阿坝县| 北川| 花垣县| 墨竹工卡县| 嵊州市| 南康市| 肥西县| 河曲县| 阳江市| http://www.jbzhii.cn 小金县| 莱州市| 甘孜县| 巴马| 罗城| 包头市| 肇源县| 华安县| 沙田区| 五家渠市| 富民县| 平利县| 五华县| 花莲县| 苏尼特右旗| 泗水县| 托克逊县| 太仆寺旗| 毕节市| 商南县| 广东省| 上杭县| 长武县| 道真| 楚雄市| 井研县| 河南省| 铜鼓县| 阿拉善盟| 晋州市| 安陆市| 龙江县| 永丰县| 青州市| http://bqhcpf.cn 罗定市| 洛扎县| 深圳市| 青河县| 柞水县| 甘德县| 金溪县| 安化县| 林芝县| 洛浦县| 克什克腾旗| 十堰市| 保靖县| 赣州市| 射阳县| 宿松县| 彭山县| 大洼县| 常德市| 乡城县| 财经| 凤山市| 南城县| 大兴区| 汾阳市| 祥云县| 明星| 乌海市| 金川县| http://zaihpy.cn 攀枝花市| 黑河市| 双流县| 新巴尔虎右旗| 自治县| 全椒县| 德令哈市| 温州市| 邢台县| 布尔津县| 镇原县| 台东县| 炉霍县| 岳西县| 镇坪县| 来凤县| 巴青县| 余姚市| 遂溪县| 体育| 会东县| 元朗区| 克拉玛依市| 松江区| 阿鲁科尔沁旗| 定远县| 陆丰市| 北安市| 南部县| http://www.nrxgqh.cn 哈巴河县| 海淀区| 乐昌市| 德江县| 沈丘县| 高密市| 苏尼特右旗| 关岭| 无棣县| 白沙| 新绛县| 兴海县| 迁西县| 甘德县| 樟树市| 抚州市| 水城县| 白水县| 子洲县| 肥城市| 闸北区| 保定市| 巴塘县| 剑阁县| 嘉禾县| 新和县| 阿图什市| 登封市| http://heLxht.cn 柏乡县| 巩留县| 铅山县| 文安县| 泰安市| 云梦县| 肃宁县| 新丰县| 云浮市| 那曲县| 宝应县| 雷州市| 玉屏| 塔城市| 沾益县| 无棣县| 金堂县|