例說計算機遞推演算法

例說計算機遞推演算法

遞推法:遞推法實際上是一種遞推關係,就是為了得到問題的解,把它推到比原問題簡單的問題求解,可分為順推法和逆推法

順推法:先找到遞推關係式,然後從初始條件出發,一步步按遞推關係式遞推,直至求出最終結果。

逆推法:在不知道初始條件的情況下,經某種遞推關係獲知問題的解,再倒過來,推知它的初始條件。

例1 斐波那契數列

13世紀義大利數學家斐波那契的《算盤書》中記載了典型的兔子產仔問題,其大意如下:

如果一對一個月大的兔子以後每一個月都可以生一對小兔子,而一對新生的兔子出生兩個月才可以生出小兔子。也就是,1月份出生,3月份開始產仔。那麼假定一年內沒有產生兔子死亡事件,那麼1年之後共有多少對兔子呢?

題解:

我們來分析一下兔子產仔問題。我們先逐月看每月兔子的對數。

第一個月:1對兔子;

第二個月:1對兔子;

第三個月:2對兔子;

第四個月:3對兔子;

第五個月:5對兔子;

第六個月:8對兔子;

………………

從上面可以看出,從第三個月開始,每個月的兔子總對數等於前兩個月兔子數的總和。相應的計算公式如下:

第n個月兔子總數Fn=Fn-1+Fn-2。

這裡初始第一個月的兔子數F1=1,第二個月的兔子數F2=1。

#include

using namespace std;

int main()

{

int f1,f2,fn;

f1=1;

f2=1;

for(int i=3;i<=12;i++)

{

fn=f1+f2;

f1=f2;

f2=fn;

}

cout<

return 0;

}

輸出

144

例2 學費問題

一個人給他兒子的四年大學生活存一筆錢,大學生每月只能取3000作為下個月的生活費,採用的是整存零取的方式,年利率在1。71%,請問需要一次性存入多少錢。每次都是月初取出3000作為本月生活費。

題解: 這個題目是我們知道了結果,需要逆推條件,

第48月大學生要連本帶息的把3000取走,那麼

第47月存款應為:

(第48個月的存款)/(1+0。0171/12(月))+3000(第47月生活費月初取出當月不記息);

第46月存款應為:

(第47個月的存款)/(1+0。0171/12(月))+3000(第46月生活費月初取出當月不記息);

。。。。。 。。。。。

第1個月存款應為: (第2個月的存款)/(1+0。0171/12(月)) +3000(第1月生活費月初取出當月不記息);

#include

using namespace std;

int main()

{

double x0=3000,x1,rate=0。0171;

for(int i=47;i>=1;i——)

{

x1=x0/(1+rate/12)+3000;

x0=x1;

}

cout<

return 0;

}

輸出

139288

頂部