斐波那契数列:{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)));
- }
OK, 就这些了. 用的 long 类型来存储结果, 当 n>92 时会内存溢出.
来源: http://www.jianshu.com/p/31b783e3eb46