原创作品，允许转载，转载时请务必以超链接形式标明文章
#include "stdafx.h"
using namespace std;
/*
algorithm
在数字上递归表示的问题也可以表示成递归算法，在许多情形下对朴素的穷举搜索得到显著的性能改进。
任何数字递推公式都可以直接翻译成递归算法，但是基本现实是编译器常常不能正确地对待递归算法，结果产生低效的程序，当怀疑可能是这种情况时，
必须再给编译器提供一些帮助，将递归算法重新写成非递归算法，让后者把这些子问题的答案系统地记录在一个表（table）内，
利用这种方法的一种技巧称为动态规划（dynamic programming）。
菲波那契数列指的是这样一个数列：
1，1，2，3，5，8，13，21……
这个数列从第二项开始，每一项都等于前两项之和
*/
unsigned int fib1(unsigned int n)
{
if (n<=1)
{
return 1;
}
else
{
return fib1(n-1) + fib1(n-2);
}
}
unsigned int fib2(unsigned int n)
{
if (n<=1)
{
return 1;
}
unsigned int fib_n = 1;
unsigned int fib_n_1 = 1;
unsigned int fib_n_2 = 1;
for (int i=2;i<=n;i++)
{
fib_n = fib_n_1 + fib_n_2;
fib_n_2 = fib_n_1;
fib_n_1 = fib_n;
}
return fib_n;
}
int main()
{
for (int i=1;i<11;i++)
{
printf("fib1(%u)=%u \r\n",i,fib1(i));
printf("fib2(%u)=%u \r\n",i,fib2(i));
}
system("pause");
return 0;
}