2.2 遞推算法思想

知識(shí)點(diǎn)講解：光盤：視頻講解\第2章\遞推算法思想.avi

與枚舉算法思想相比，遞推算法能夠通過已知的某個(gè)條件，利用特定的關(guān)系得出中間推論，然后逐步遞推，直到得到結(jié)果為止。由此可見，遞推算法要比枚舉算法聰明，它不會(huì)嘗試每種可能的方案。

2.2.1 遞推算法基礎(chǔ)

遞推算法可以不斷利用已有的信息推導(dǎo)出新的東西，在日常應(yīng)用中有如下兩種遞推算法。

① 順推法：從已知條件出發(fā)，逐步推算出要解決問題的方法。例如斐波那契數(shù)列就可以通過順推法不斷遞推算出新的數(shù)據(jù)。

② 逆推法：從已知的結(jié)果出發(fā)，用迭代表達(dá)式逐步推算出問題開始的條件，即順推法的逆過程。

2.2.2 實(shí)踐演練——解決“斐波那契數(shù)列”問題

為了說明遞推算法的基本用法，接下來將通過一個(gè)具體實(shí)例的實(shí)現(xiàn)過程，詳細(xì)講解遞推算法思想在編程過程中的基本應(yīng)用。

實(shí)例2-3 使用順推法解決“斐波那契數(shù)列”問題

源碼路徑 光盤\daima\2\shuntui.c

問題描述：斐波那契數(shù)列因數(shù)學(xué)家列昂納多?斐波那契以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”。一般而言，兔子在出生兩個(gè)月后，就有繁殖能力，一對(duì)兔子每個(gè)月能生出一對(duì)小兔子來。如果所有兔子都不死，那么一年以后可以繁殖多少對(duì)兔子？

算法分析：以新出生的一對(duì)小兔子進(jìn)行如下分析。

① 第一個(gè)月小兔子沒有繁殖能力，所以還是一對(duì)。

② 2個(gè)月后，一對(duì)小兔子生下了一對(duì)新的小兔子，所以共有兩對(duì)兔子。

③ 3個(gè)月以后，老兔子又生下一對(duì)，因?yàn)樾⊥米舆€沒有繁殖能力，所以一共是3對(duì)。

……

依次類推可以列出關(guān)系表，如表2-1所示。

表2-1 月數(shù)與兔子對(duì)數(shù)關(guān)系表

表中數(shù)字1,1,2,3,5,8……構(gòu)成了一個(gè)數(shù)列，這個(gè)數(shù)列有個(gè)十分明顯的特點(diǎn)：前面相鄰兩項(xiàng)之和，構(gòu)成了后一項(xiàng)。這個(gè)特點(diǎn)的證明：每月的大兔子數(shù)為上月的兔子數(shù)，每月的小兔子數(shù)為上月的大兔子數(shù)，某月兔子的對(duì)數(shù)等于其前面緊鄰兩個(gè)月的和。

由此可以得出具體算法如下所示：

設(shè)臵初始值為F0=1，第1個(gè)月兔子的總數(shù)是F1=1。

第2個(gè)月的兔子總數(shù)是F2= F0+F1。

第2個(gè)月的兔子總數(shù)是F3= F1+F2。

第3個(gè)月的兔子總數(shù)是F4= F2+F3。

………

第n個(gè)月的兔子總數(shù)是Fn= Fn-2+Fn-1。

具體實(shí)現(xiàn)：根據(jù)上述問題描述，根據(jù)“斐波那契數(shù)列”的順推算法分析，編寫實(shí)現(xiàn)文件shuntui.c，具體實(shí)現(xiàn)代碼如下所示。

          #include <stdio.h>
          #define NUM 13
          int main()
          {
          int i;
              long fib[NUM] = {1,1}; //定義一個(gè)擁有13個(gè)元素的數(shù)組，用于保存兔子的初始數(shù)據(jù)和每月的總數(shù)
          //順推每個(gè)月的總數(shù)
          for(i=2; i<NUM; i++)
              {
          fib[i] = fib[i-1]+fib[i-2];
              }
          //循環(huán)輸出每個(gè)月的總數(shù)
          for(i=0; i<NUM; i++)
              {
                printf("第%d月兔子總數(shù)：%d\n", i, fib[i]);
              }
          getch();
          return 0;
          }

執(zhí)行后的效果如圖2-4所示。

圖2-4 “斐波那契數(shù)列”問題執(zhí)行效果

2.2.3 實(shí)踐演練——解決“銀行存款”問題

一個(gè)實(shí)例不能說明遞推算法思想的基本用法，接下來開始使用逆推算法解決“銀行存款”問題。

實(shí)例2-4 使用逆推法解決“銀行存款”問題

源碼路徑 光盤\daima\2\nitui.c

問題描述：母親為兒子小Sun 4年的大學(xué)生活準(zhǔn)備了一筆存款，方式是整存零取，規(guī)定小Sun每月月底取下一個(gè)月的生活費(fèi)。現(xiàn)在假設(shè)銀行的年利息為1.71%，請(qǐng)編寫程序，計(jì)算母親最少需要存入多錢？

算法分析：可以采用逆推法分析存錢和取錢的過程，因?yàn)榘凑赵聻橹芷谌″X，所以需要將4年分為48個(gè)月，并分別對(duì)每個(gè)月進(jìn)行計(jì)算。

如果在第48月后Sun大學(xué)畢業(yè)時(shí)連本帶息要取1000元，則要先求出第47個(gè)月時(shí)銀行存款的錢數(shù)：

第47月月末存款=1000/(1+0.0171/12)；

第46月月末存款=(第47月月末存款+1000)/(1+0.0171/12)；

第45月月末存款=(第46月月末存款+1000)/(1+0.0171/12)；

第44月月末存款=(第45月月末存款+1000)/(1+0.0171/12);

……

第2月月末存款=(第3月月末存款+1000)/(1+0.0171/12)；

第1月月末存款=(第2月月末存款+1000)/(1+0.0171/12)。

具體實(shí)現(xiàn)：編寫實(shí)現(xiàn)文件nitui.c，具體實(shí)現(xiàn)代碼如下所示。

        #include <stdio.h>
        #define FETCH 1000
        #define RATE 0.0171
        int main()
        {
            double corpus[49];
            int i;
            corpus[48]=(double)FETCH;
            for(i=47; i>0; i--)
            {
            corpus[i]=(corpus[i+1]+FETCH)/(1+RATE/12);
            }
            for(i=48; i>0; i--)
            {
              printf("%d月月末本利共計(jì)：%.2f\n", i, corpus[i]);
            }
            getch();
            return 0;
        }

執(zhí)行后的效果如圖2-5所示。

圖2-5 “銀行存款”問題執(zhí)行效果