MOOC清华《程序设计基础》第6章：三种递推方法求兔子数列问题（斐波那契数列）

//递推算法的常用步骤：
//第一步：设定递推初值；
//第二步：依公式递推（常用循环实现）。

//递推算法的优点：
//1，递推公式往往比通项公式容易得到；
//2，计算机非常擅长递推公式的重复计算。 

#include 
using namespace std;

int main()
{
int N;
cout <<"请输入月份N：";
cin >> N;
int Fibonacci_1(int n);
int Fibonacci_2(int n);
int Fibonacci_3(int n);

cout <<"第1种方法所求第" < <cout <<"第2种方法所求第" < <cout <<"第3种方法所求第" < < 
return 0;
}

int Fibonacci_1(int n)
//方法一：按大小兔子分别递推 
{
int *small = new int[n];
int *big = new int[n];
int fib = 0;

small[0] = 1;
big[0] = 0;

for(int i = 1; i {
small[i] = big[i - 1];
big[i] = small[i - 1] + big[i - 1];
}
fib = small[n - 1] + big[n - 1];
delete[] small;
delete[] big;

return fib;
}

int Fibonacci_2(int n)
//方法二：按总数递推 
{
int *total = new int[n];
int fib = 0;

total[0] = 1;
total[1] = 1;

for(int i = 2; i total[i] = total[i - 1] + total[i - 2];
fib = total[n - 1];
delete[] total;

return fib;
}

int Fibonacci_3(int n)
//方法三：不用数组递推 
{
int dang_yue;
int qian_yue = 1;
int shang_yue = 1;

for(int i = 2; i {
dang_yue = qian_yue + shang_yue;
qian_yue = shang_yue;
shang_yue = dang_yue;
}  //注意赋值的顺序，以免把还需要的有用的值给覆盖掉了

return dang_yue; 
}