遞推算法

今天我們就來了解一個簡單的算法：遞推算法。通過已知條件，利用特定關(guān)系得出中間推論，直至得到結(jié)果的算法。遞推算法分為順推和逆推兩種。

所謂順推法是從已知條件出發(fā)，逐步推算出要解決的問題的方法。比如之前我們講過的斐波拉契數(shù)列，設(shè)它的函數(shù)為f（n），已知f（1）=1，f（2）=1;f（n）=f（n-2）+f（n-1）（/1>=3。nEN）。則我們通過順推可以知道，f（3）=f（1）+f（2）=2，f（4）=f（2）+f（3）=3……直至我們要求的解。

同理，所謂逆推法從已知問題的結(jié)果出發(fā)，用迭代表達式逐步推算出問題開始的條件，即順推法的逆過程，稱為逆推。比如最簡單的求數(shù)值的題目：將一個數(shù)乘以4，再加上112，減去20，最后除以4，這時得100，那么求這個數(shù)字是多少呢？這道題目我們就可以用逆推法來求解，100～4，加上20，減去112，除以4便是結(jié)果了。

了解了遞推算法的基本原理后，我們帶入編程的思想來做一道題目：媽媽為小陳的四年大學(xué)學(xué)費準備了一筆存款，方式是整存零取，規(guī)定小陳每月月底取下一個月的生活費1000元。現(xiàn)在假設(shè)利率為1.71%，編寫程序，計算媽媽最少需要存多少錢？

這道題目可以采用逆推法分析存錢和取錢的過程，因為按照月為周期取錢，所以共四年48個月，并分別對每個月進行計算。為了在第48個月大學(xué)畢業(yè)時連本帶利要取1000元，這要求出前47個月時銀行存款的錢數(shù)。

（1）第47個月月末存款=1000（1+0.0171/12）

（2）第46個月月末存款=（47月月末存款+1000）/（1+0.0171/12）

（3）第45個月月末存款=（46月月末存款+1000）/（1+0.0171/12）

（47）第2個月月末存款=（第三個月月末存款+1000）/（1+0.0171/12）

（48）第1個月月末存款=（第二個月月末存款+1000）/（1+0.0171/12）

本次我們使用的編程語言為c語言。很明顯這道題目采用遞推算法中的逆序方法，我們已知最后第48個月要取出的金額數(shù)目為1000元，我們便可以先確定一個數(shù)組為money【49】，將1000元存放在money【48】中，然后通過循環(huán)的方法，利用遞歸的特性，可以得出一個計算公式，這里需要注意一下，這里的利率指的是年利率，月利率需要除以12。根據(jù)計算公式可得：（每個月月末存款+1000）/（1+0.0171/12）;通過循環(huán)遞推的方法從第48個月一直朝前計算，直到計算到第1個月的本末利息，便可得出最后的結(jié)果：46364.32元。

遞推算法的難度不大。代碼知識內(nèi)容都是我們學(xué)過的，通過遞推算法我們了解了存款利息的計算方式，有興趣的同學(xué)還可以把銀行貸款的計算方法變成代碼，貸款和存款利息的計算方式有差別。貸款方式基本上分為兩種：等額本金和等額本息。感興趣的同學(xué)趕緊動起手來了解嘗試吧。