從八皇后問(wèn)題的解決方案看面向過(guò)程和面向?qū)ο?/h1>

2012-04-20 09:31:38宋東興殷旭東

常熟理工學(xué)院學(xué)報(bào)訂閱 2012年4期 收藏

關(guān)鍵詞：面向?qū)ο?/a>棋子皇后

宋東興，殷旭東

（常熟理工學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇常熟 215500）

從八皇后問(wèn)題的解決方案看面向過(guò)程和面向?qū)ο?/p>

宋東興，殷旭東

（常熟理工學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇常熟 215500）

通過(guò)八皇后問(wèn)題的解的分析，討論了面向過(guò)程的解決方案和面向?qū)ο蠼鉀Q方案的不同，比較了面向過(guò)程設(shè)計(jì)思想和面向?qū)ο笤O(shè)計(jì)思想的區(qū)別和聯(lián)系，提出程序設(shè)計(jì)教學(xué)要從面向過(guò)程逐步過(guò)渡到面向?qū)ο?，片面?qiáng)調(diào)一面而忽視另一面都是不可取的.

八皇后；面向過(guò)程；面向?qū)ο螅粚?duì)象；解決方案

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

在眾多針對(duì)“軟件危機(jī)”[1]的解決方案中，面向?qū)ο缶幊淌且环N優(yōu)秀的方法，國(guó)內(nèi)大多數(shù)高校的計(jì)算機(jī)專業(yè)都開(kāi)設(shè)了面向?qū)ο蟮某绦蛟O(shè)計(jì)課程，有的學(xué)校大一就直接進(jìn)入面向?qū)ο蠼虒W(xué).然而要完全拋棄傳統(tǒng)的面向過(guò)程方法，只接受面向?qū)ο蠓椒ú⒉豢茖W(xué)，宏觀上的面向?qū)ο笏枷霃奈⒂^上看仍然是面向過(guò)程在實(shí)現(xiàn)，離開(kāi)面向過(guò)程的鋪墊而直接進(jìn)入面向?qū)ο螅瑢W(xué)生理解起來(lái)往往比較困難，實(shí)際教學(xué)效果也不理想.筆者通過(guò)八皇后問(wèn)題的求解案例，分析比較面向過(guò)程和面向?qū)ο蟮牟煌?，提出程序設(shè)計(jì)教學(xué)要從面向過(guò)程循序漸進(jìn)到面向?qū)ο?

1 面向過(guò)程的分析方法

1.1 基本思想

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

1.2 八皇后問(wèn)題的面向過(guò)程的解決方案

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

1.2.1 窮舉法

解決八皇后問(wèn)題的關(guān)鍵在于：

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

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

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

接下來(lái)對(duì)每種擺放情況做沖突檢查，若不沖突就是一個(gè)解.

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

沖突檢查：（1）每行只放一個(gè)棋子，行上不會(huì)有沖突.

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

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

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

窮舉算法：

1.2.2 回溯法[3]

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

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

回溯算法：

2 面向?qū)ο蟮姆治龇椒?/h2>

2.1 基本思想

面向?qū)ο蠓治龇椒ǖ幕舅枷胧牵喝f(wàn)物都可看作對(duì)象[4]，面向?qū)ο蟮南到y(tǒng)是由一組互相作用的對(duì)象所組成的一個(gè)團(tuán)體，每一個(gè)對(duì)象都扮演一個(gè)角色，并為團(tuán)體中的其他成員提供特定的服務(wù)或者執(zhí)行特定的行為，目標(biāo)的實(shí)現(xiàn)來(lái)自于每個(gè)對(duì)象的努力和他們之間的相互協(xié)作.

2.2 八皇后問(wèn)題的面向?qū)ο蟮慕鉀Q方案

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

2.2.1 為皇后對(duì)象建模

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

第n列的可接受的解決方案可表示為：從第1列到第n列，沒(méi)有皇后可以攻擊其他皇后.每個(gè)皇后只需詢問(wèn)相鄰皇后是否能夠互相攻擊.如果能夠互相攻擊，那么這個(gè)皇后就前進(jìn)一行（如不能前進(jìn)將返回失?。?，當(dāng)相鄰皇后返回不能互相攻擊的信息時(shí)，解決方案就找到了，通過(guò)詢問(wèn)最右端的皇后，找到一個(gè)可能的解決方案，即可找到整個(gè)問(wèn)題的方案.

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

①構(gòu)造方法

為皇后對(duì)象建立必需的初始條件，行（row）從第0列開(kāi)始，處于第n列皇后通過(guò)給定列號(hào)（col）以及相鄰的皇后進(jìn)行初始化.

圖1 皇后類的UML表示

②尋找解決方案findsolution()

通過(guò)詢問(wèn)相鄰皇后是否能夠互相攻擊，來(lái)尋找解決方案.如果能夠互相攻擊，那么這個(gè)皇后就前進(jìn)一行（如不能前進(jìn)將返回失?。?，當(dāng)相鄰皇后返回不能互相攻擊的信息時(shí)，解決方案就找到了.

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

如果當(dāng)前不是最后行，則行號(hào)（row）加1，否則當(dāng)試驗(yàn)過(guò)本列所有位置后仍然沒(méi)有找到解決方案時(shí)，就要求鄰居皇后尋找新的解決方案，并且自己的行（row）位置重新從第0行開(kāi)始.

2.2.3 八皇后問(wèn)題的面向?qū)ο蠼?/p>

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

3 面向過(guò)程和面向?qū)ο蟮慕鉀Q方案比較

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

而在八皇后問(wèn)題的面向?qū)ο蟮慕夥ㄖ?，我們賦予每一個(gè)棋子自己解決問(wèn)題的能力[1].把尋找解決方案的責(zé)任分配給那些相互作用的皇后對(duì)象，每一個(gè)棋子就像一個(gè)有生命的個(gè)體，它們彼此相互作用，各自負(fù)責(zé)尋找自己的解決方案，這代替了那種由單一實(shí)體來(lái)控制結(jié)果的集中模式，當(dāng)系統(tǒng)需求增加或發(fā)生變化時(shí)，只需在局部進(jìn)行改變或增刪操作，而不會(huì)影響整個(gè)系統(tǒng)的架構(gòu).

面向過(guò)程方法要求你為數(shù)據(jù)結(jié)構(gòu)做些什么，而面向?qū)ο蟮姆椒▌t問(wèn)數(shù)據(jù)結(jié)構(gòu)為你做了些什么；面向過(guò)程采用的是一個(gè)過(guò)程狀態(tài)轉(zhuǎn)換模型，它與實(shí)際計(jì)算機(jī)內(nèi)部的工作流程大致相吻合，但對(duì)于我們理解如何使用計(jì)算機(jī)來(lái)解決問(wèn)題卻沒(méi)有什么幫助，面向過(guò)程采用的是“責(zé)任驅(qū)動(dòng)”設(shè)計(jì)模型，與現(xiàn)實(shí)世界人們解決問(wèn)題的方式相近，但無(wú)論是哪種方式對(duì)程序員來(lái)說(shuō)都應(yīng)該熟悉和掌握.教師在面向?qū)ο蟮某绦蛟O(shè)計(jì)教學(xué)中，選取一些典型的問(wèn)題，引導(dǎo)學(xué)生用兩種不同方式來(lái)思考解決，更有利于學(xué)生加深對(duì)面向?qū)ο蟮乃季S方式的理解，筆者在實(shí)際的教學(xué)中采用這種方式也取得了較好的效果.

4 結(jié)束語(yǔ)

面向過(guò)程和面向?qū)ο笫莾煞N不同的思考問(wèn)題的方法，面向過(guò)程方法以事務(wù)為中心，側(cè)重于分析解決問(wèn)題所需的步驟，強(qiáng)調(diào)怎么實(shí)施，而面向?qū)ο笫且允挛餅橹行模严到y(tǒng)分解成若干對(duì)象，側(cè)重某個(gè)對(duì)象在整個(gè)解決問(wèn)題的過(guò)程中的責(zé)任（行為），強(qiáng)調(diào)實(shí)施什么.通過(guò)用責(zé)任來(lái)討論問(wèn)題，提高了抽象的水平，使得對(duì)象之間更加獨(dú)立，這正是解決復(fù)雜問(wèn)題的關(guān)鍵.

對(duì)于大多數(shù)問(wèn)題，面向?qū)ο蠓椒ū让嫦蜻^(guò)程方法優(yōu)越，但并不意味著它能完全取代面向過(guò)程，事實(shí)上，從宏觀角度來(lái)分析系統(tǒng)時(shí)采用面向?qū)ο螅鴱奈⒂^考慮一個(gè)對(duì)象的行為的具體實(shí)現(xiàn)時(shí)，離不開(kāi)面向過(guò)程[5].這就要求程序設(shè)計(jì)課程教學(xué)要從面向過(guò)程開(kāi)始，并在教學(xué)中及時(shí)滲透面向?qū)ο蟮乃枷?，使學(xué)生逐步過(guò)渡到用面向?qū)ο蠓椒ㄋ伎紗?wèn)題.

[1]（美）Timothy A Budd.面向?qū)ο蟪绦蛟O(shè)計(jì)（影印版）[M].北京：清華大學(xué)出版社，2004.

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

[3]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M].北京：清華大學(xué)出版社，1997.

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

[5]游曉明，劉升.面向過(guò)程向面向?qū)ο蟪绦蛟O(shè)計(jì)的轉(zhuǎn)變與實(shí)現(xiàn)[J].湖北師范學(xué)院學(xué)報(bào)，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—），男，江蘇高郵人，講師，研究方向：計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)，圖像處理，軟件工程.

猜你喜歡

面向?qū)ο?/a>棋子皇后

棋子多少顆

小學(xué)生學(xué)習(xí)指導(dǎo)(低年級(jí))(2021年5期)2021-07-21 02:01:02

擺棋子

數(shù)學(xué)小靈通(1-2年級(jí))(2020年11期)2020-12-28 00:41:16

有趣的棋子

數(shù)學(xué)小靈通(1-2年級(jí))(2020年9期)2020-10-27 03:24:26

面向?qū)ο蟮挠?jì)算機(jī)網(wǎng)絡(luò)設(shè)計(jì)軟件系統(tǒng)的開(kāi)發(fā)

電子測(cè)試(2018年15期)2018-09-26 06:01:34

遇皇后

奇妙博物館(2018年7期)2018-08-07 08:08:34

棋子餓了

大灰狼(2018年5期)2018-06-20 14:49:32

為什么皇后鎮(zhèn)被稱為“冒險(xiǎn)之都”？

小溪流(畫(huà)刊)(2018年12期)2018-02-26 12:45:30

面向?qū)ο蟮臄?shù)據(jù)交換協(xié)議研究與應(yīng)用

電測(cè)與儀表(2017年24期)2017-12-19 05:15:24

被放逐的皇后

學(xué)生天地(2016年13期)2016-05-17 05:45:34

面向?qū)ο骔eb開(kāi)發(fā)編程語(yǔ)言的的評(píng)估方法

現(xiàn)代計(jì)算機(jī)(2016年12期)2016-02-28 18:35:25

常熟理工學(xué)院學(xué)報(bào)2012年4期

常熟理工學(xué)院學(xué)報(bào)的其它文章

FX2N-48MR在電梯智能控制系統(tǒng)的應(yīng)用

一種基于角色和協(xié)作的軟件需求獲取方法

詞結(jié)合型未登錄詞識(shí)別方法研究

嵌入式圖像檢測(cè)系統(tǒng)的設(shè)計(jì)與應(yīng)用

多聚焦像素級(jí)數(shù)字圖像信息融合

一種無(wú)需同步的閃光測(cè)光系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)