static void Main(string[] args) { //斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”。 //指的是这样一个数列:1、1、2、3、5、8、13、21、34、……,这个数列从第3项开始,每一项都等于前两项之和。 //递推公式:F(n)=F(n-1)+F(n-2) //求第30个数是什么? int n = 30; //方法一:递归解决,递归时存在重复计算的情况,所以当 N 超过50时就会出现很慢的情况,性能不好。 Console.WriteLine(Fib_1(n)); //方法二:数组解决,保存计算结果,避免重复计算,性能比上面递归解决方案好。 Console.WriteLine(Fib_2(n)); //方法三:循环解决,不需要操作数组,性能比上面数组解决方案好。 Console.WriteLine(Fib_3(n)); Console.ReadKey(); } //方法一:递归解决,递归时存在重复计算的情况,所以当 N 超过50时就会出现很慢的情况,性能不好。 static int Fib_1(int num) { if (num <= 0) return 0; else if (num >= 1 && num <= 2) return 1; else return Fib_1(num - 1) + Fib_1(num - 2); } //方法二:数组解决,保存计算结果,避免重复计算,性能比上面递归解决方案好。 static long Fib_2(int num) { if (num <= 0) { return 0; } else if (num >= 1 && num <= 2) { return 1; } else { long[] arr = new long[num]; arr[0] = 1; arr[1] = 1; for (int i = 2; i < num; i++) { arr[i] = arr[i - 1] + arr[i - 2]; } return arr[num - 1]; } } //方法三:循环解决,不需要操作数组,性能比上面数组解决方案好。 static long Fib_3(int num) { long last = 1; long nextLast = 1; long result = 0; for (int i = 2; i < num; i++) { result = last + nextLast; nextLast = last; last = result; } return result; }
文章评论