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

宋東興，殷旭東

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

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

宋東興，殷旭東

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

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

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

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

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

1 面向過程的分析方法

1.1 基本思想

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

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

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

1.2.1 窮舉法

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

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

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

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

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

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

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

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

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

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

窮舉算法：

1.2.2 回溯法[3]

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

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

回溯算法：

2 面向對象的分析方法

2.1 基本思想

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

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

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

2.2.1 為皇后對象建模

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

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

2.2.2 Queen類的部分方法實現(xiàn)思路

①構造方法

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

圖1 皇后類的UML表示

②尋找解決方案findsolution()

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

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

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

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

圖2 findSolution()方法實現(xiàn)思路

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

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

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

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

4 結束語

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

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

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

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

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

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

[5]游曉明，劉升.面向過程向面向對象程序設計的轉變與實現(xiàn)[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—），男，江蘇高郵人，講師，研究方向：計算機網絡技術，圖像處理，軟件工程.