從八皇后問題的解決方案看面向過程和面向對象

宋東興，殷旭東

（常熟理工學院計算機科學與工程學院，江蘇常熟 215500）

從八皇后問題的解決方案看面向過程和面向對象

宋東興，殷旭東

（常熟理工學院計算機科學與工程學院，江蘇常熟 215500）

通過八皇后問題的解的分析，討論了面向過程的解決方案和面向對象解決方案的不同，比較了面向過程設計思想和面向對象設計思想的區別和聯系，提出程序設計教學要從面向過程逐步過渡到面向對象，片面強調一面而忽視另一面都是不可取的.

八皇后；面向過程；面向對象；對象；解決方案

著名數學家高斯在1850年提出：在8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法？此即八皇后問題.八皇后問題可以采用面向過程和面向對象兩種不同的解決方案.

在眾多針對“軟件危機”[1]的解決方案中，面向對象編程是一種優秀的方法，國內大多數高校的計算機專業都開設了面向對象的程序設計課程，有的學校大一就直接進入面向對象教學.然而要完全拋棄傳統的面向過程方法，只接受面向對象方法并不科學，宏觀上的面向對象思想從微觀上看仍然是面向過程在實現，離開面向過程的鋪墊而直接進入面向對象，學生理解起來往往比較困難，實際教學效果也不理想.筆者通過八皇后問題的求解案例，分析比較面向過程和面向對象的不同，提出程序設計教學要從面向過程循序漸進到面向對象.

1 面向過程的分析方法

1.1 基本思想

以過程作為分析的主題，著重強調一個系統中發生的過程以及由一個過程的結果輸出作為下一個過程輸入的數據流動，通過信息流及其狀態轉換來認識系統，采用的是“自頂向下，逐步求精”的思維方法，核心思想是：以事件為中心，分析解決問題的步驟，然后用函數把這些步驟一步一步實現，使用時依次調用就可以了.

1.2 八皇后問題的面向過程的解決方案

需要使用各種數據結構來保持棋子的位置，算法通過系統地控制每一個數據結構的數值，檢測每個新位置是否符合沒有皇后攻擊其他皇后的原則來解決問題.

1.2.1 窮舉法

解決八皇后問題的關鍵在于：

（1）找到合理的數據結構存放棋子的擺放位置.

（2）要有合理的沖突檢查算法[2].采用的方法是，先把8個棋子擺在棋盤上，每行擺一個，然后去檢查這種擺放是否有沖突，如果沒有沖突，即找到了一種解決方案.

首先是如何存放棋子的擺放位置.可以設想一下，當8個棋子擺放好之后，每個棋子的位置都有一個行值和列值，由于每行只有一個棋子，就可以從第0行開始依次記錄每個棋子的列值，8個棋子的列值依次排列構成一個數字序列，例如24135046，它表示第0行棋子擺放在第2列，第1行棋子擺放在第4列，以此類推，這樣一種擺放方式對應一個8位的8進制數，用一個一維數組來存放這樣一個8進制數，00000000-77777777窮舉了所有的擺放方式.

接下來對每種擺放情況做沖突檢查，若不沖突就是一個解.

注：(i，queen[i])代表一個棋子的行，列坐標.

沖突檢查：（1）每行只放一個棋子，行上不會有沖突.

（2）數組中如沒有兩個元素值相同，則列上沒有沖突.

（3）任意兩個棋子（i，queen[i]），(j，queen[j])，只要有queen[i]+i!=queen[j]+j，且queen[i]-i!=queen [j]-j，則對角線上沒有沖突.

為方便運算：將八進制數范圍00000000-77777777表達成十進制，則范圍為[0，88-1]，再將范圍內每個十進制數轉化為八進制數字存入queen數組中.

窮舉算法：

1.2.2 回溯法[3]

回溯算法也叫試探法，它是一種系統化的窮舉搜索問題的解的方法，基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試.在前進和回撤的路上都設置一些標記，以便正確返回，直到達到目標或者所有可能方案都已嘗試為止.

從第一行開始，逐行安排皇后（Q），Q1從第一行的第一個位置開始嘗試，然后嘗試Q2，…Qi-1，使得前i-1個皇后互不攻擊，再嘗試Qi，如果第i行上沒有剩余可放位置，則返回i-1行，同時使Qi-1放棄剛才擺放位置，并嘗試下一位置，…當Q8成功放置時，則找到一種解.當Q8嘗試過最后一行的所有位置后，算法結束.

回溯算法：

2 面向對象的分析方法

2.1 基本思想

面向對象分析方法的基本思想是：萬物都可看作對象[4]，面向對象的系統是由一組互相作用的對象所組成的一個團體，每一個對象都扮演一個角色，并為團體中的其他成員提供特定的服務或者執行特定的行為，目標的實現來自于每個對象的努力和他們之間的相互協作.

2.2 八皇后問題的面向對象的解決方案

方案要點：創建代表每一個皇后的對象，然后賦予它們尋找解決方案的能力，八個皇后彼此之間相互作用，各自負責尋找自己的解決方案[1].

2.2.1 為皇后對象建模

分析：在任一解決方案中，不會出現空列，一列也不可能有兩個皇后，可以為每一皇后指定一個特定列（col），而尋找一個合適的行（row）.為了找到解決方案，皇后們需要相互聯系，每個皇后只需要了解它的鄰居（neighbor），即緊挨著其左邊的那個皇后.

第n列的可接受的解決方案可表示為：從第1列到第n列，沒有皇后可以攻擊其他皇后.每個皇后只需詢問相鄰皇后是否能夠互相攻擊.如果能夠互相攻擊，那么這個皇后就前進一行（如不能前進將返回失敗），當相鄰皇后返回不能互相攻擊的信息時，解決方案就找到了，通過詢問最右端的皇后，找到一個可能的解決方案，即可找到整個問題的方案.

2.2.2 Queen類的部分方法實現思路

①構造方法

為皇后對象建立必需的初始條件，行（row）從第0列開始，處于第n列皇后通過給定列號（col）以及相鄰的皇后進行初始化.

圖1 皇后類的UML表示

②尋找解決方案findsolution()

通過詢問相鄰皇后是否能夠互相攻擊，來尋找解決方案.如果能夠互相攻擊，那么這個皇后就前進一行（如不能前進將返回失敗），當相鄰皇后返回不能互相攻擊的信息時，解決方案就找到了.

③皇后前進下一位置advance()

如果當前不是最后行，則行號（row）加1，否則當試驗過本列所有位置后仍然沒有找到解決方案時，就要求鄰居皇后尋找新的解決方案，并且自己的行（row）位置重新從第0行開始.

2.2.3 八皇后問題的面向對象解

圖2 findSolution()方法實現思路

3 面向過程和面向對象的解決方案比較

從八皇后的問題的解法來看，傳統的面向過程的求解就像一個人坐在棋盤前，移動一些毫無生命的棋子，這種方式強調的是從一個行為到另一個行為的控制流，每一步過程的結果，都是下一步的前提條件，程序設計者必須事必躬親，考慮系統的每一細節，什么時候對什么數據進行操作.當分析的系統規模較小時，面向過程的方法能取得較好的效果，但當系統逐比較大復雜時，由于系統組成預先不可知，加上系統組成之間的結構關系也不易弄清楚的情況下，面向過程的分析方法就難以勝任了.

而在八皇后問題的面向對象的解法中，我們賦予每一個棋子自己解決問題的能力[1].把尋找解決方案的責任分配給那些相互作用的皇后對象，每一個棋子就像一個有生命的個體，它們彼此相互作用，各自負責尋找自己的解決方案，這代替了那種由單一實體來控制結果的集中模式，當系統需求增加或發生變化時，只需在局部進行改變或增刪操作，而不會影響整個系統的架構.

面向過程方法要求你為數據結構做些什么，而面向對象的方法則問數據結構為你做了些什么；面向過程采用的是一個過程狀態轉換模型，它與實際計算機內部的工作流程大致相吻合，但對于我們理解如何使用計算機來解決問題卻沒有什么幫助，面向過程采用的是“責任驅動”設計模型，與現實世界人們解決問題的方式相近，但無論是哪種方式對程序員來說都應該熟悉和掌握.教師在面向對象的程序設計教學中，選取一些典型的問題，引導學生用兩種不同方式來思考解決，更有利于學生加深對面向對象的思維方式的理解，筆者在實際的教學中采用這種方式也取得了較好的效果.

4 結束語

面向過程和面向對象是兩種不同的思考問題的方法，面向過程方法以事務為中心，側重于分析解決問題所需的步驟，強調怎么實施，而面向對象是以事物為中心，把系統分解成若干對象，側重某個對象在整個解決問題的過程中的責任（行為），強調實施什么.通過用責任來討論問題，提高了抽象的水平，使得對象之間更加獨立，這正是解決復雜問題的關鍵.

對于大多數問題，面向對象方法比面向過程方法優越，但并不意味著它能完全取代面向過程，事實上，從宏觀角度來分析系統時采用面向對象，而從微觀考慮一個對象的行為的具體實現時，離不開面向過程[5].這就要求程序設計課程教學要從面向過程開始，并在教學中及時滲透面向對象的思想，使學生逐步過渡到用面向對象方法思考問題.

[1]（美）Timothy A Budd.面向對象程序設計（影印版）[M].北京：清華大學出版社，2004.

[2]焦玲，邢偉，于海波，等.Java程序設計案例匯編[M].北京：中國鐵道出版社，2008.

[3]嚴蔚敏，吳偉民.數據結構（C語言版）[M].北京：清華大學出版社，1997.

[4]（美）Bruce Eckel.Java編程思想[M].北京：機械工業出版社，2005.

[5]游曉明，劉升.面向過程向面向對象程序設計的轉變與實現[J].湖北師范學院學報，1999（2）.

Observing Procedure-oriented and Object-oriented from the Solution to the Eight-queen Puzzle

SONG Dong-xing,Ying Xu-dong,LIU Yong-jun
(School of Computer Science and Engineering,Changshu Institute of Technology,Changshu 215500,China)

By analyzing the question of the eight-queen puzzle,this paper discusses the different solutions between procedure-oriented and object-oriented,compares their relation and difference.The paper also proposes program?ming design teaching,which needs natural transition from procedure-oriented to object-oriented,and it is not desir?able to emphasize one side and ignore another one.

eight queens;procedure-oriented;object-oriented;object;solution

TP312

A

1008-2794（2012）04-0120-05

2012-02-23

宋東興（1973—），男，江蘇高郵人，講師，研究方向：計算機網絡技術，圖像處理，軟件工程.