题目：输出第 n 个斐波纳契数（Fibonacci）
方法一、简单递归
这个就不说了，小n怡情，大n伤身啊……当n=40的时候，就明显感觉到卡了，不是一般的慢。
//输出第n个 Fibonacci 数
#include <iostream>
using namespace std; long long Fibonacci(int n)
{
if(n<=) return ;
else return Fibonacci(n-) + Fibonacci(n-);
} int main()
{
int n;
while(cin>>n, n)
cout<<Fibonacci(n)<<endl; return ;
}
方案二、动态规划
//输出第n个 Fibonacci 数
#include <iostream>
#include <cstring>
#define MAXN 300
using namespace std; long long F[MAXN];
int i;
long long Fibonacci(int n)
{
i++;
F[]=;
F[]=;
if(n<=) return ;
else
{
if(F[n]==0) // !!!!!!!!!!
F[n]=Fibonacci(n-) + Fibonacci(n-);
return F[n];
}
} int main()
{
int n;
while(cin>>n, n)
{
i=;
memset(F,,sizeof(F));
cout<<Fibonacci(n)<<" ";
cout<<"调用"<<i<<"次"<<endl; }
return ;
}
【以上程序可以优化：既然只要求输出第n个斐波纳契数f(n)，则只需用两个变量记录f(n-1)和f(n-2)，不用开数组将整个1到n的斐波纳契数列都记录下来。】
最开始忘了 if(F[n]==0) 这个判断（17行），导致了很多次的重复计算——和递归算法一样多的次数。
以下是程序运行截图，上图为正确程序，下图为漏掉了 if(F[n]==0) 这个判断的错误程序。可以看出运行时间上的巨大差距：
当输入n=100时，错误的程序很长很长一段时间内都还没计算出来。
方法三、for循环 + 数组
速度也非常快。
//输出第n个 Fibonacci 数
#include <iostream>
#include <cstring>
#define MAXN 300
using namespace std; long long F[MAXN];
long long Fibonacci(int n)
{
F[]=;
F[]=;
if(n<=) return ;
else
{
for(int i=; i<n; ++i)
F[i] = F[i-] + F[i-];
return F[n-];
}
} int main()
{
int n;
while(cin>>n, n)
{
memset(F,,sizeof(F));
cout<<Fibonacci(n)<<endl;
}
return ;
}