这里仍然要注意一个问题，有些人会简单的用数组存储斐波那契数列，而不是用三个数转换。估计是要占用不少内存空间的，空间复杂度虽然没有原来要求那么高，还是要注意一下的。
#include <iostream> using namespace std; long Function_one(long n) { if (n <= 0)return 1; //0和1 long current = 1; //大于1 long last = 1; long beforelast = 0; for (long i = 2; i <= n; i++) { current = last + beforelast; beforelast = last; //下次循环的第n-2项 last = current; //下次循环的n-1项 } return current; } long Function_two(long n) { long sum = 0; for (long i = 1; i <= n; i++) { sum += Function_one(i); } return sum; } long main() { long n; while (cin >> n) { cout << Function_one(n) << ',' << Function_two(n) << endl; } return 0; }线性代数书上，这是作为例题讲的，就是证明斐波那契数列可以由一个公式，即一次计算就能求出答案，那么这样他的复杂度是不是变成O(1)呢？实际上在那个等式中，仍然存在着幂的运算。所以快速幂还是目前我觉得计算斐波那契数列不错的方法之一。 思路就是求斐波那契数列第n项即求对于矩阵{1,1;1,0}的n次幂，说实话我是不知道的，看了线性代数的有关内容又看了一下网上一些人的解法。然后结合他们的一些思想。写的这个 代码：
#include <iostream> using namespace std; struct Matrix { int mat[2][2]; Matrix() //构造 { mat[0][0] = 1; mat[0][1] = 1; mat[1][0] = 1; mat[1][1] = 0; } friend Matrix operator * (const Matrix& a, const Matrix& b);//友元函数声明 }; Matrix operator * (const Matrix& a, const Matrix& b)//乘法重载 { Matrix m; m.mat[0][0] = a.mat[0][0] * b.mat[0][0] + a.mat[0][1] * b.mat[1][0]; m.mat[0][1] = a.mat[0][0] * b.mat[0][1] + a.mat[0][1] * b.mat[1][1]; m.mat[1][0] = a.mat[1][0] * b.mat[0][0] + a.mat[1][1] * b.mat[1][0]; m.mat[1][1] = a.mat[1][0] * b.mat[0][1] + a.mat[1][1] * b.mat[1][1]; return m; } //********************************************************* //函 数 名：power //参 数： exp m // 指数 矩阵 //返 回 值：矩阵 //备 注：递归求矩阵 //********************************************************* Matrix power(const Matrix& m, int exp) { if (exp == 0)//递归终止条件 { Matrix r; r.mat[0][0] = r.mat[1][1] = 1; r.mat[0][1] = r.mat[1][0] = 0; return r; } Matrix val = power(m, exp / 2); if (exp % 2) return m*val*val; else return val*val; } //********************************************************* //函 数 名：Function_one //参 数： n 第n项 //返 回 值：答案 //备 注：递归求数列第n项 //********************************************************* int Function_one(int n) { Matrix m; m = power(m, n); return m.mat[0][1]; } //********************************************************* //函 数 名：Function_two //参 数： n 前n项 //返 回 值：答案 //备 注：递归求数列前n项和 //********************************************************* int Function_two(int n)//这个函数没有什么改动，我认为一个加号递归，复杂度是不会影响多少的 { int result; if (n == 0)return 0; else { result = Function_one(n) + Function_two(n - 1); } return result; } long main() { int n; while(cin >> n) cout << Function_one(n)<<','<<Function_two(n) << endl; return 0; }