原創(chuàng)作品，允許轉(zhuǎn)載，轉(zhuǎn)載時(shí)請(qǐng)務(wù)必以超鏈接形式標(biāo)明文章
#include "stdafx.h"
using namespace std;
/*
algorithm
在數(shù)字上遞歸表示的問(wèn)題也可以表示成遞歸算法，在許多情形下對(duì)樸素的窮舉搜索得到顯著的性能改進(jìn)。
任何數(shù)字遞推公式都可以直接翻譯成遞歸算法，但是基本現(xiàn)實(shí)是編譯器常常不能正確地對(duì)待遞歸算法，結(jié)果產(chǎn)生低效的程序，當(dāng)懷疑可能是這種情況時(shí)，
必須再給編譯器提供一些幫助，將遞歸算法重新寫成非遞歸算法，讓后者把這些子問(wèn)題的答案系統(tǒng)地記錄在一個(gè)表（table）內(nèi)，
利用這種方法的一種技巧稱為動(dòng)態(tài)規(guī)劃（dynamic programming）。
菲波那契數(shù)列指的是這樣一個(gè)數(shù)列：
1，1，2，3，5，8，13，21……
這個(gè)數(shù)列從第二項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和
*/
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;
}