遞推法在C語言項目實踐中的應用技巧

唐小健

(廣東省韶關市中等職業技術學校，廣東 韶關 512000)

0 引言

所謂遞推法就是給定某個初始值，或稱為舊值，歸納出新值和舊值之間的內在聯系，如此不停地一直運算下去，直到得出需要的數值。這里需要知道的是新值的求出要看舊值的求出，如果舊值無法求出，那么新值也就無法推導出來。這跟數學上的遞推公式是同一類問題。

從以上對遞推法的闡述，要使用遞推法進行求解問題，關鍵是在確定初始值的基礎上，如何找出新值和舊值之間的內在聯系即運算規律是關鍵，規律找出來了，就可以順利的進行遞推，得到解題結果就是時間問題了。所以說，只要找出其中的數的運算規律，可以說項目實踐成功了一大半。下面在詳述項目的解題過程中，著重對數據之間的關系以及遞推的具體實現進行分析和探究。

1 項目實踐1：遞推法解決斐波那契數列問題

1.1 項目任務

打印輸出斐波那契數列的前40 項。斐波那契數列的前幾項是：1，1，2，3，5，8，13，21，34，…。輸出格式是每行輸出4個數。

1.2 項目分析

初看斐波那契數列的前幾項，相鄰的數之間或前后數之間好像沒有任何內在的關系，第一項是1，第二項還是1，第三項是2，第四項是3，第五項是5，……。可是只要仔細分析，其數據之間的內在聯系即規律也就一目了然了，原來，斐波那契數列的分布規律是：從第三項開始，每個數等于前面兩個數之和。

對于這個“簡單”的問題，在C 語言編程教學中需要用遞推法來實現，下面詳述了這個問題。

用變量a，b 和c 來描述遞推過程，可以把這三個變量當做會移動的指針或者游標。現在把數列的第一項數值1 賦值給變量a，把數列的第二項數值1 賦值給變量b。此時變量a 指向第一個數1，變量b 指向第二個數1。把前面兩個數相加的結果賦值給變量c，即c=a+b，此時變量c指向第三個數2，如圖1所示。

圖1 斐波那契數列的第1次運算分析圖

上面只是得到第一個新值（第三個數2），那么，又如何得到第二個新值（第四個數3）呢？上面說到可以把變量當做指針來操作，如果把變量a，b 從左順序向右移動一個位置，又進行c=a+b賦值操作，此時的變量c指向第四個數3，如圖2所示。

圖2 斐波那契數列的第2次運算分析圖

按照這個規律順序向右移動變量a和b一個位置，進行c=a+b 操作，變量c 也隨之向右移動一個位置，變量c 代表的是遞推出來的一個個的“新值”，如果進行輸出，那問題不就得到解決了嗎。

仔細觀察上面的運算分析圖可以很清晰的發現，變量a，b 及c 的遞推承接關系，變量a，b、c 順序指向相鄰的三個數，不管怎么移動，移動幾次，執行的都是c=a+b 操作，關鍵是變量a，b 及c 不是固定不變的，隨著指向不同位置上的數值，變量的值也是隨之改變的。分析上面的運算分析圖可以很容易確定變量a，b 及c的遞推承接關系：

確定了變量的遞推關系表達式，就可以動手編寫具體的C程序代碼了。

1.3 項目實踐的C語言程序框架設計

可以先定義好基本類型整型變量a、b、c、t及count，變量a、b、c 用來指向斐波那契數列中的相鄰的三個數，變量t 用來控制變量移動的次數。因為前兩項預先已經輸出，要求輸出40項，因此只要從左向右順序移動的次數是38次，也即變量t 的控制范圍是[1，38]，用C 語言中的循環控制語句for 就可以實現。變量count 是個計數器，用來統計數列中數的個數，控制每行輸出四個數，賦初值為2（統計前兩個數）。程序的總體框架可以設計如下：

1.4 項目實踐的完整C語言程序如下

1.5 C程序的運行

運行上面的C 語言程序，可輸出斐波那契數列的前40項，每行四個數，共有十行，如圖3所示。

圖3 按照4×10格式輸出斐波那契數列前40項

1.6 項目算法設計的改進

毫無疑問，以上遞推算法的設計可以順利的求解斐波那契數列問題，循環遞推了38次，從第三個數的單個輸出開始，每個數就要循環遞推一次。運算效率不是很高，那有沒有可以提高解題效率的遞推算法呢？答案顯然是肯定的。

再仔細觀察和分析上面的圖1 圖2 運算分析圖，可知要遞推出下一個“新數”，只要把變量a和b順序向右移動一個位置。能不能每次順序向右移動二個位置，同時輸出兩項呢？答案顯然也是肯定的、可行的。具體見以下分析。

同樣定義兩個整型變量a和b，用來指向相鄰的兩個數，首先把第一項1 賦值給變量a，把第二項1 賦值給變量b，也即a=1，b=1。此時變量a 指向數列的第一項，變量b指向數列的第二項，如圖4所示。

圖4 斐波那契數列的改進分析①

把變量a 和b 同時向右移動二個位置，此時變量a指向第三個數2，變量b指向第四個數3，如圖5所示。

圖5 斐波那契數列的改進分析②

此時如果執行如下運算：

會得到a=a+b=1+1=2，b=b+a=1+2=3，我們驚奇地發現，a 和b 的指向跟圖5 一樣，a 指向第三個數2，b 指向第四個數3。

再把變量a和b同時向右移動二個位置，此時變量a指向第五個數5，變量b指向第六個數8，如圖6所示。

圖6 斐波那契數列的改進分析③

同樣地，執行運算a=a+b 和b=b+a，此時a=2+3=5，b=3+5=8，a 指向第五個數5，b 指向第六個數8，指向跟圖6一樣。

到此為止，可以驗證變量a和b每次同時向右移動二個位置，同時算出兩個“新數”的改進遞推算法是完全可行的。因為每次輸出兩項，所以循環控制次數總共只需要20 次就行了，大大提高了程序的運行效率。只要把上面的程序稍作修改就可以了，改進后的完整C程序如下所示。

需要注意的是該程序跟改進之前的程序是不完全一樣的：①所有40 個數都是在進入循環之后輸出的；②計數器變量count初始賦值為0；③for循環控制語句只需要循環20次，每次輸出兩個數；④遞推的實現語句不一樣：改進之前是“a=b;b=c;”，改進之后是“a=a+b;b=b+a;”。執行上面程序，輸出結果是一樣的。

1.7 項目實踐的進階：斐波那契數列的另類解法

如果對普通變量的動態賦值問題理解不是很透徹，可以考慮用C語言中的數組技術來求解。事實上，數組的應用在任何高級編程語言中都是極其重要的一項操作，可以解決許多用普通變量無法求解的復雜問題，編寫程序更加簡練，更加易于理解，方便程序的編譯和調試，在代碼二次修改方面也更加方便，C語言當然也不例外。

因為數組中的分量是帶有下標的，正好可以用來存放具有某些規律的一系列數據，通過一定的算法運算可以快速的得到問題的答案。下面我們使用C語言中的數組和遞推算法來進行斐波那契數列的前40 項輸出，也是每行輸出四個數。

程序首先定義好三個變量：因為輸出的數據較大，所以需要定義一個放置數列各項數據的長整型數組變量shulie[40]，數組下標從0 開始，分量shulie[0]賦初值為斐波那契數列的第一項數據1，分量shulie[1]賦初值為斐波那契數列的第二項數據1；循環控制變量i，為普通整數類型；計數器變量count，為普通整數類型，賦初值為2。在進入循環之前先輸出數組的前兩項，進入循環之后判斷計數器的數值是否是4 的整數倍，是的話就輸出換行符號進行換行，否則按照遞推規律進行新值的運算并輸出，同時計數器進行自加1操作。因為數組的下標從0 開始的，現在要輸出40 個數，所以循環控制變量i的遍歷范圍是[0,39]。

完整的C程序代碼如下：

此程序采用數組實現了每次向右移動一個位置，每次輸出一個數。如果要求每次向右移動二個位置，每次輸出兩個數，那么需要修改程序。如果我們對C 語言程序的執行流程理解透徹，就只需對上面程序稍加修改便可以達到這個目的。修改之后的C程序如下：

2 項目實踐2：遞推法解決猴子吃桃問題

2.1 項目任務

有只猴子在第一天摘下若干個桃子，馬上吃了一半又多吃了一個；第二天早上將前一天吃剩下的桃子吃掉一半又多吃了一個；以后每天早上都吃了前一天吃剩下的一半零一個。到第10天早上想吃桃子時，此時只剩下一個桃子了。請用C語言編程求解猴子第一天一共摘下多少個桃子？

2.2 項目分析

這個問題比較簡單，是個典型的迭代問題，可以使用遞推算法求解。項目實踐1的遞推是頭開始逐步推出后面的每一項數據的。本項目同樣可以采用遞推算法進行求解，只不過遞推的順序正好相反，從最后一項數據開始倒推，逐步推出前面的每一項數據。

前面說過，遞推的關鍵是找出新值與舊值之間的關系。下面就來找出猴子吃桃問題的前后相鄰兩天的桃子數之間的關系。

假設前后相鄰兩天的桃子數定義為qian 和hou，那么根據倒推的遞推算法，應用數學的思維，確定每天的桃子數。最后一天（第10 天）的桃子數為1 個的話，第九天的桃子數應該就是4個，…，一直推到第一天的桃子數，問題得到解決。如表1所示。

表1 猴子吃桃問題的項目分析表

通過上表的數據分析，確定前后相鄰兩天桃子數的關系是qian=(hou+1)×2。這里有兩個變量qian 和hou，分別存放前后相鄰兩天桃子的數量，如果在使用變量hou遞推出變量qian的數值之后，hou的值就不用保存了，因此這里可以只定義一個變量taozi，用來臨時存放每天的桃子數量，那么前后相鄰兩天桃子數的關系是就可以表述為taozi=(taozi+1)*2。

2.3 項目實踐的完整C語言程序

代碼如下：

該程序的控制思路：①定義整型變量taozi 及n，taozi 用來統計每天的桃子數量，n 是循環控制變量；②采用倒推的遞推算法，所以變量n 是從9 開始遞減的，一直到第一天為止；③在循環體中循環執行遞推關系表達式taozi=(taozi+1)*2，一直到計算出第一天的桃子數為止。

2.4 程序執行結果

猴子在第一天總共摘下1534個桃子。

2.5 項目實踐的進階

同樣的，猴子吃桃問題也可以使用遞推算法和數組技術進行求解，其完整的C程序如下。

3 結束語

本文研究了C語言編程教學中對于遞推法的應用技巧，給出對斐波那契數列問題和猴子吃桃問題的求解。其實很多問題通過分析和算法設計，都可以歸結到遞推的算法上來，關鍵在于我們能不能夠分析出問題中所蘊含的相鄰數據之間的關系，因為這是順利進行遞推的前提和基礎。善用遞推算法可以拓寬C語言編程思維，進而提高使用C 語言程序設計解決實際應用問題的能力。