求1,1,2,3,5,8,13 斐波那契数列第N个数的值
朋友问了个斐波那契算法。我给出了个递归算法
public static int Foo(int n) { if (n <= 2) { return n; } else { return Foo(n - 1) + Foo(n - 2); } }
结果被打击了,说递归效率不行啊,于是网上饿补了下,发现很多方法,总结了两个
1. 递推工式 num[i + 2] = num[i + 1] + num[i];
public static int GetNum1(int n) { int result = 0; if (n <= 2) { result = n; } else { int[] num = new int[n]; num[0] = 1; num[1] = 1; System.Console.Write(num[0] + " " + num[1] + " "); for (int i = 0; i <n-2; i++) { num[i + 2] = num[i + 1] + num[i]; result = num[i + 2]; System.Console.Write(result + " "); } } return result; }