游戲算法分析在C語言教學(xué)中的應(yīng)用

劉天時(shí) 李皎 陳明晰 西安石油大學(xué)計(jì)算機(jī)學(xué)院 710065

1 引言

算法是程序設(shè)計(jì)和軟件開發(fā)的基礎(chǔ)，也是計(jì)算機(jī)程序設(shè)計(jì)語言中一個(gè)重點(diǎn)和難點(diǎn)。算法具有不可見性、抽象性、復(fù)雜性是影響學(xué)生理解算法思想的重要因素[1,2]。由于其邏輯性強(qiáng)、實(shí)踐性強(qiáng)，對(duì)初學(xué)者來說具有一定難度。因此，激發(fā)學(xué)生對(duì)算法設(shè)計(jì)的興趣尤為重要。本文通過一些游戲案例來講解算法設(shè)計(jì)思想，將學(xué)生對(duì)玩游戲的興趣往設(shè)計(jì)算法的方向引導(dǎo)，從而促進(jìn)學(xué)生理解一些典型算法設(shè)計(jì)思想。游戲算法分析教學(xué)方法使得學(xué)生從枯燥無味的算法學(xué)習(xí)中解脫出來，特別是學(xué)生一提到游戲，興趣高漲，產(chǎn)生強(qiáng)烈的求知欲望，從而大大提高學(xué)生的學(xué)習(xí)興趣，真正使學(xué)生愛學(xué)、樂學(xué)，達(dá)到寓教于樂的目的[3]。

下面以游戲案例為切入點(diǎn)，敘述程序設(shè)計(jì)中一些典型的常用算法，包括遞歸法、遞推法和逆向法。

2 遞歸法

在算法分析與設(shè)計(jì)中，常常用到遞歸法。遞歸是指在定義自身的同時(shí)又出現(xiàn)了對(duì)自身的調(diào)用。遞歸方法可以把復(fù)雜問題逐層分解，最后將其劃分為規(guī)模較小的問題進(jìn)行解決，然后再逐層返回。使用遞歸方法往往使函數(shù)的定義或算法的描述簡(jiǎn)潔而且易于理解[4,5,6]。

漢諾塔問題是一個(gè)用遞歸思想解題的經(jīng)典例子。漢諾塔問題可描述為：有3個(gè)分別命名為A、B、C的塔座，在塔座A上插有N個(gè)大小各不相同、從小到大編號(hào)為1，2，…，N的圓盤，且圓盤必須按照自下而上，由大到小疊放（如圖1）。要求將塔座A上的N個(gè)圓盤借助塔座C移至塔座B上，并仍然按同樣順序疊放，圓盤移動(dòng)時(shí)必須遵循如下規(guī)則：每次只能移動(dòng)一個(gè)圓盤；任何時(shí)刻都不能將一個(gè)較大的圓盤壓在較小的圓盤之上；在滿足上述規(guī)則的基礎(chǔ)上，圓盤可以插在A、B和C中的任一塔座上[4]。

可用遞歸思想分析該問題，當(dāng)N=1時(shí)，只需將編號(hào)為1的圓盤從塔座A直接移至塔座B，不需要使用輔助塔座C，問題比較簡(jiǎn)單。當(dāng)N＞1時(shí)，需要使用輔助塔座C，可先將N-1個(gè)較小的圓盤按照移動(dòng)規(guī)則從塔座A移至塔座C，然后將剩下的編號(hào)為N的最大的圓盤移至B，最后再將N-1個(gè)圓盤按照移動(dòng)規(guī)則從塔座C移至塔座B。這樣，N個(gè)圓盤的移動(dòng)問題可以轉(zhuǎn)化為N-1個(gè)圓盤的移動(dòng)問題。用函數(shù)Hanoi（N，A，B，C）實(shí)現(xiàn)將塔座A上的N個(gè)圓盤（如圖1所示）按照移動(dòng)規(guī)則借助塔座C移到塔座B上，最終圓盤必須按照自下而上，由大到小的方式疊放在塔座B上。用函數(shù)Move（N，A，B）實(shí)現(xiàn)將塔座A上編號(hào)為N的圓盤移至塔座B上。漢諾塔問題的求解算法如下：

用F[N]表示將N個(gè)圓盤按移動(dòng)規(guī)則從塔座A移至塔座B至少需要移動(dòng)的次數(shù)，由上述分析過程可知，F(xiàn)[N]=2F[N-1]+1，又因?yàn)镕[1]=1，由以上兩個(gè)等式可以推出F[N]=2N－1。

3 遞推法

遞推法是利用問題本身所具有的一種遞推關(guān)系求問題解的方法。在教學(xué)過程中，可用兔子繁殖問題的例子引出一個(gè)具有遞推關(guān)系的數(shù)列，即Fibonacci數(shù)列。兔子繁殖問題描述如下：兔子在出生兩個(gè)月后，具有繁殖能力，一對(duì)兔子每個(gè)月能生出一對(duì)小兔子來。那么由一對(duì)小兔子開始，一年后可繁殖多少對(duì)兔子?

圖2為兔子繁殖問題示意圖，○表示一對(duì)小兔子，●表示一對(duì)大兔子，實(shí)線表示一對(duì)小兔子長(zhǎng)大成為一對(duì)大兔子或表示一對(duì)大兔子照樣生長(zhǎng)，虛線性表示一對(duì)大兔子生出一對(duì)小兔子[7]。

由圖2可知，一月份是一對(duì)小兔子，二月份這只兔子長(zhǎng)成大兔子；三月份大兔子生出一對(duì)小兔子，此時(shí)共有兩對(duì)兔子；四月份小兔子長(zhǎng)成大兔子，大兔子又生出一對(duì)小兔子，此時(shí)共有三對(duì)兔子；五月份兩對(duì)大兔子生出兩對(duì)小兔子，小兔子長(zhǎng)成大兔子，此時(shí)共有五對(duì)兔子。通過樹形示意圖觀察，我們發(fā)現(xiàn)本月兔子等于上月兔子加上上月兔子。用F(n)表示第n個(gè)月底兔子的對(duì)數(shù)。

圖1 漢諾塔問題初始狀態(tài)

圖2 兔子繁殖問題示意圖

根據(jù)上面的遞推公式，可以計(jì)算出從第一個(gè)月起，逐月的兔子對(duì)數(shù)依次是：1，1，2，3，5，8，13，21，34，55，89，144，233等等。這就是著名的斐波那契數(shù)列。

4 逆向法

數(shù)字拼圖游戲，就是借助N×N矩陣中的空白單元，通過若干次移動(dòng)空白單元格，把錯(cuò)亂的數(shù)字單元位置關(guān)系按先行后列的順序，從小到大依次排列在N×N矩陣單元格中。把數(shù)字單元按照先行后列，從小到大排列，并且空白單元出現(xiàn)在N×N矩陣最后一個(gè)單元格的完成界面稱為N×N數(shù)字拼圖目的界面。數(shù)字拼圖游戲的關(guān)鍵在于出題算法設(shè)計(jì)，即給出一個(gè)N×N錯(cuò)亂的數(shù)字界面。如何保證所出的游戲題有解，我們想到逆向法，即將游戲的目的界面作為逆向法的初始界面，從目的界面開始隨機(jī)地移動(dòng)一些步數(shù)，再把這個(gè)界面作為游戲的初始界面，這樣可以保證每一個(gè)初始界面都是可解的[4]。

游戲中唯一的空白單元通常情況下可以向四個(gè)方向移動(dòng)（特殊情況，空白單元與邊相鄰則可以向三個(gè)方向移動(dòng)，空白單元與角相鄰則可以向兩個(gè)方向移動(dòng)）。用數(shù)字1，2，3，4分別表示四個(gè)移動(dòng)方向，即向上、向下、向左、向右移動(dòng)。我們可以抽取1～4的隨機(jī)數(shù)可以確定空白單元下一步的移動(dòng)方向，通過記錄每次抽取的隨機(jī)數(shù)，便可知空白單元的移動(dòng)軌跡。另一種記錄游戲軌跡的方法是記錄非空白單元的移動(dòng)軌跡[4]。

對(duì)于N×N規(guī)模的數(shù)字拼圖游戲，數(shù)字拼圖出題算法如下：

Step3 若 K = 10N3，算法結(jié)束，否則轉(zhuǎn)向Step2。

數(shù)字拼圖出題算法可保證所出的題目有解，但是在出題中可能出現(xiàn)直接或間接重復(fù)移動(dòng)，例如將同一個(gè)數(shù)字單元連續(xù)移動(dòng)多次，或轉(zhuǎn)圈循環(huán)移動(dòng)等?？刹捎靡恍﹥?yōu)化算法對(duì)簡(jiǎn)單的重復(fù)移動(dòng)進(jìn)行消除。例如，對(duì)“田”字型重復(fù)移動(dòng)可消除，以簡(jiǎn)化移動(dòng)軌跡。

另外，在算法教學(xué)過程中，我們應(yīng)該注重以下幾個(gè)方面的問題：（1）挖掘豐富游戲素材，激發(fā)學(xué)習(xí)興趣；（2）某種類型的算法設(shè)計(jì)思想必須講透，采用精講多練的原則，不能過于寬泛；（3）應(yīng)該配合具體游戲制作多媒體課件，通過圖像、動(dòng)畫、影像、聲音等多媒體信息使算法思想的講解更為生動(dòng)形象。

5 結(jié)束語

游戲案例分析教學(xué)以輕松愉快的方式讓學(xué)生在娛樂中培養(yǎng)和鍛煉學(xué)生的思維能力，是一種特殊的教學(xué)方式。與傳統(tǒng)的教學(xué)方法相比,游戲案例分析教學(xué)使得算法教學(xué)具體、生動(dòng)、形象，彌補(bǔ)了傳統(tǒng)方法的不足。經(jīng)過近兩年在本校C語言課程教學(xué)中應(yīng)用表明，該教學(xué)方法能消除學(xué)生對(duì)算法思想的神秘感和畏難情緒，激發(fā)了學(xué)生主動(dòng)學(xué)習(xí)興趣，使學(xué)生對(duì)于復(fù)雜、抽象的算法有一感性直觀的認(rèn)識(shí)和理解，提高了學(xué)生分析問題和解決問題的能力，取得了良好的教學(xué)效果。

[1] 鄭宗漢，鄭曉明.算法設(shè)計(jì)與分析[M].北京：清華大學(xué)出版社.2005.

[2] 崔彩峰，孫勁光.C語言程序設(shè)計(jì)教學(xué)方法的研究[J].中國(guó)科技信息.2009(09): 212.

[3] 李曉紅.實(shí)施快樂教學(xué)提高教學(xué)效率之淺見[J].中國(guó)科技信息.2009(10): 258.

[4] 劉天時(shí).軟件案例分析[M].北京：清華大學(xué)出版社.2008.

[5] 唐自立.數(shù)據(jù)結(jié)構(gòu)課程中遞歸算法教學(xué)探討[J].中國(guó)科技信息.2006(8): 290-291.

[6] 譚浩強(qiáng).C程序設(shè)計(jì)(第三版)[M].北京：清華大學(xué)出版社.2005.

[7] 黃忠裕.一個(gè)數(shù)學(xué)歷史名題的模型建立及其教學(xué)設(shè)想——談“兔子繁殖問題”[J].湖州師范學(xué)院學(xué)報(bào).2003(03): 117-120.