遞推算法

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

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

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

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

這道題目可以采用逆推法分析存錢和取錢的過(guò)程，因?yàn)榘凑赵聻橹芷谌″X，所以共四年48個(gè)月，并分別對(duì)每個(gè)月進(jìn)行計(jì)算。為了在第48個(gè)月大學(xué)畢業(yè)時(shí)連本帶利要取1000元，這要求出前47個(gè)月時(shí)銀行存款的錢數(shù)。

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

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

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

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

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

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

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