唐小健

(廣東省韶關(guān)市中等職業(yè)技術(shù)學(xué)校，廣東 韶關(guān) 512000)

0 引言

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

從以上對遞推法的闡述，要使用遞推法進(jìn)行求解問題，關(guān)鍵是在確定初始值的基礎(chǔ)上，如何找出新值和舊值之間的內(nèi)在聯(lián)系即運(yùn)算規(guī)律是關(guān)鍵，規(guī)律找出來了，就可以順利的進(jìn)行遞推，得到解題結(jié)果就是時間問題了。所以說，只要找出其中的數(shù)的運(yùn)算規(guī)律，可以說項(xiàng)目實(shí)踐成功了一大半。下面在詳述項(xiàng)目的解題過程中，著重對數(shù)據(jù)之間的關(guān)系以及遞推的具體實(shí)現(xiàn)進(jìn)行分析和探究。

1 項(xiàng)目實(shí)踐1：遞推法解決斐波那契數(shù)列問題

1.1 項(xiàng)目任務(wù)

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

1.2 項(xiàng)目分析

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

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

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

圖1 斐波那契數(shù)列的第1次運(yùn)算分析圖

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

圖2 斐波那契數(shù)列的第2次運(yùn)算分析圖

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

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

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

1.3 項(xiàng)目實(shí)踐的C語言程序框架設(shè)計

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

1.4 項(xiàng)目實(shí)踐的完整C語言程序如下

1.5 C程序的運(yùn)行

運(yùn)行上面的C 語言程序，可輸出斐波那契數(shù)列的前40項(xiàng)，每行四個數(shù)，共有十行，如圖3所示。

圖3 按照4×10格式輸出斐波那契數(shù)列前40項(xiàng)

1.6 項(xiàng)目算法設(shè)計的改進(jìn)

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

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

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

圖4 斐波那契數(shù)列的改進(jìn)分析①

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

圖5 斐波那契數(shù)列的改進(jìn)分析②

此時如果執(zhí)行如下運(yùn)算：

會得到a=a+b=1+1=2，b=b+a=1+2=3，我們驚奇地發(fā)現(xiàn)，a 和b 的指向跟圖5 一樣，a 指向第三個數(shù)2，b 指向第四個數(shù)3。

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

圖6 斐波那契數(shù)列的改進(jìn)分析③

同樣地，執(zhí)行運(yùn)算a=a+b 和b=b+a，此時a=2+3=5，b=3+5=8，a 指向第五個數(shù)5，b 指向第六個數(shù)8，指向跟圖6一樣。

到此為止，可以驗(yàn)證變量a和b每次同時向右移動二個位置，同時算出兩個“新數(shù)”的改進(jìn)遞推算法是完全可行的。因?yàn)槊看屋敵鰞身?xiàng)，所以循環(huán)控制次數(shù)總共只需要20 次就行了，大大提高了程序的運(yùn)行效率。只要把上面的程序稍作修改就可以了，改進(jìn)后的完整C程序如下所示。

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

1.7 項(xiàng)目實(shí)踐的進(jìn)階：斐波那契數(shù)列的另類解法

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

因?yàn)閿?shù)組中的分量是帶有下標(biāo)的，正好可以用來存放具有某些規(guī)律的一系列數(shù)據(jù)，通過一定的算法運(yùn)算可以快速的得到問題的答案。下面我們使用C語言中的數(shù)組和遞推算法來進(jìn)行斐波那契數(shù)列的前40 項(xiàng)輸出，也是每行輸出四個數(shù)。

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

完整的C程序代碼如下：

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

2 項(xiàng)目實(shí)踐2：遞推法解決猴子吃桃問題

2.1 項(xiàng)目任務(wù)

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

2.2 項(xiàng)目分析

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

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

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

表1 猴子吃桃問題的項(xiàng)目分析表

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

2.3 項(xiàng)目實(shí)踐的完整C語言程序

代碼如下：

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

2.4 程序執(zhí)行結(jié)果

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

2.5 項(xiàng)目實(shí)踐的進(jìn)階

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

3 結(jié)束語

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