原創作品，允許轉載，轉載時請務必以超鏈接形式標明文章
#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;
}