遞推法:遞推法實際上是一種遞推關係,就是為了得到問題的解,把它推到比原問題簡單的問題求解,可分為順推法和逆推法
順推法:先找到遞推關係式,然後從初始條件出發,一步步按遞推關係式遞推,直至求出最終結果。
逆推法:在不知道初始條件的情況下,經某種遞推關係獲知問題的解,再倒過來,推知它的初始條件。
例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