游戲算法分析在C語言教學中的應用

劉天時 李皎 陳明晰 西安石油大學計算機學院 710065

1 引言

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

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

2 遞歸法

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

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

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

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

3 遞推法

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

圖2為兔子繁殖問題示意圖，○表示一對小兔子，●表示一對大兔子，實線表示一對小兔子長大成為一對大兔子或表示一對大兔子照樣生長，虛線性表示一對大兔子生出一對小兔子[7]。

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

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

圖2 兔子繁殖問題示意圖

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

4 逆向法

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

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

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

Step3 若 K = 10N3，算法結束，否則轉向Step2。

數(shù)字拼圖出題算法可保證所出的題目有解，但是在出題中可能出現(xiàn)直接或間接重復移動，例如將同一個數(shù)字單元連續(xù)移動多次，或轉圈循環(huán)移動等。可采用一些優(yōu)化算法對簡單的重復移動進行消除。例如，對“田”字型重復移動可消除，以簡化移動軌跡。

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

5 結束語

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

[1] 鄭宗漢，鄭曉明.算法設計與分析[M].北京：清華大學出版社.2005.

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

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

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

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

[6] 譚浩強.C程序設計(第三版)[M].北京：清華大學出版社.2005.

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