計(jì)算機(jī)工程系《C++程序設(shè)計(jì)》學(xué)習(xí)輔導(dǎo)資料之二課程設(shè)計(jì)指導(dǎo)書(shū)

計(jì)算機(jī)工程系《C++程序設(shè)計(jì)》學(xué)習(xí)輔導(dǎo)資料之二

課程設(shè)計(jì)指導(dǎo)書(shū)

于永彥趙建洋

江蘇淮陰工學(xué)院計(jì)算機(jī)工程系

二00六年二月二十八日

目錄

一、課程設(shè)計(jì)的目的.................................................1

二、實(shí)驗(yàn)環(huán)境與教學(xué)要求.............................................1

三、實(shí)施原則、方案與步驟...........................................1

四、設(shè)計(jì)課題.......................................................2

（-）幻方.....................................................................2

1.奇數(shù)階幻方的制作........................................................3

2.偶數(shù)階幻方的制作.......................................................4

3.設(shè)計(jì)要求................................................................8

（二）矩陣操作.................................................................8

1.矩陣翻轉(zhuǎn)................................................................8

2.矩陣卷動(dòng)................................................................8

3.矩陣旋轉(zhuǎn)................................................................9

4.設(shè)計(jì)要求...............................................................10

（三）漢諾塔..................................................................11

1.基本涵義...............................................................11

2.常規(guī)解法...............................................................11

3.設(shè)計(jì)要求...............................................................12

（四）八皇后..................................................................13

1.基本涵義...............................................................13

2.設(shè)計(jì)要求...............................................................13

（五）成績(jī)管理................................................................14

1.設(shè)計(jì)要求...............................................................14

2.參考代碼...............................................................15

（六）H編碼..................................................................28

1.二元H碼...............................................................28

2.m元H碼..............................................................30

（七）數(shù)據(jù)排序...............................................................32

1.基本概念...............................................................32

2.插入排序...............................................................32

3.交換排序...............................................................34

4.選擇排序...............................................................36

5.歸并排序...............................................................38

6.設(shè)計(jì)要求...............................................................39

（八）數(shù)據(jù)查找...............................................................39

1.基本概念...............................................................39

2.順序查找...............................................................40

3.二分查找...............................................................41

4.索引查找...............................................................43

5.散列查找...............................................................47

(九)最短路徑...............................................................57

1.圖概念.................................................................57

2.圖的表示方法...........................................................61

3.帶權(quán)圖的最短路徑......................................................63

4.設(shè)計(jì)要求...............................................................66

(十)表達(dá)式求值.............................................................67

1.基本概念...............................................................67

2.棧的存儲(chǔ)和運(yùn)算.........................................................67

3.表達(dá)式求值.............................................................69

4.設(shè)計(jì)要求...............................................................73

5.參考代碼...............................................................73

五、課程設(shè)計(jì)報(bào)告要求..............................................77

六、成績(jī)?cè)u(píng)定......................................................78

附錄A課程設(shè)計(jì)報(bào)告格式要求........................................79

附錄BC/C++常用函數(shù)..............................................84

1.數(shù)學(xué)函數(shù).................................................................84

2.字符串函數(shù)...............................................................85

(1)strcpy(chardestination[],constcharsource[]);...............................................................85

(2)stmcpy(chardestination[],constcharsource[],intnumchars);....................................86

(3)strcat(chartarget[],constcharsource[]);........................................................................86

(4)stmcat(chartarget[],constcharsource[],intnumchars);...............................................86

(5)intstrcmp(constcharfirststring[],constcharsecondstring);.........................................87

(6)strlen(constcharstring[]);..............................................................................................87

附錄CCString基礎(chǔ).................................................88

1.主要函數(shù)的實(shí)現(xiàn)...........................................................88

2.常用函數(shù).................................................................89

(1)Delete.................................................................................................................................89

(2)FindOneOf.........................................................................................................................89

(3)Find.....................................................................................................................................89

(4)GetAt..................................................................................................................................89

(5)Insert..................................................................................................................................89

(6)Left......................................................................................................................................89

(7)Right....................................................................................................................................89

(8)MakeLower,MakeUpper.............................................................................................90

(9)MakeReverse......................................................................................................................90

(10)+=.....................................................................................................................................90

(11)str[]...................................................................................................................................90

(12)TrimLeft,TrimRight........................................................................................................90

(13)Remove(TCHARch);...................................................................................................91

3.CString與char□的相互轉(zhuǎn)換................................................91

4.將NULL字節(jié)放入CString中..............................................91

5.在非MFC程序中引用CString............................................................................................92

(1)在非dll或lib里使用CString類..........................................92

(2)在dll或lib里使用CString類............................................92

附錄D文件操作....................................................94

1.標(biāo)準(zhǔn)流設(shè)備...............................................................94

2.文件流...................................................................95

3.使用I/O成員函數(shù).........................................................96

(1)用getline。讀取輸入行.................................................96

(2)用get()讀取一個(gè)字符...................................................97

(3)get()輸入一系列字符..................................................98

(4)輸出一個(gè)字符..........................................................99

4.文件操作.................................................................99

(1)文件輸出..............................................................99

(2)文件輸入..............................................................101

附錄E隨機(jī)函數(shù)...................................................103

一、課程設(shè)計(jì)的目的

《C++程序設(shè)計(jì)》是計(jì)算機(jī)科學(xué)與技術(shù)、通信工程等相關(guān)專業(yè)的最重要的一門(mén)專業(yè)基礎(chǔ)

課，內(nèi)容龐大，涉及面廣，知識(shí)點(diǎn)多，教、學(xué)難度都非常大，往往費(fèi)了大量時(shí)間而達(dá)不到預(yù)

期教學(xué)效果。俗語(yǔ)說(shuō)：學(xué)習(xí)的最好方法是實(shí)踐。本課程設(shè)計(jì)正是基于此，力求為學(xué)生提供??

個(gè)理論聯(lián)系實(shí)際的機(jī)會(huì)，通過(guò)布置一定難度的課題，要求學(xué)生獨(dú)立完成。通過(guò)實(shí)踐，建立系

統(tǒng)設(shè)計(jì)的整體思想，鍛煉編寫(xiě)程序、調(diào)試程序的能力，學(xué)習(xí)文檔編寫(xiě)規(guī)范，培養(yǎng)獨(dú)立學(xué)習(xí)、

吸取他人經(jīng)驗(yàn)、探索前言知識(shí)的習(xí)慣，樹(shù)立團(tuán)隊(duì)協(xié)作精神。同時(shí)，課程設(shè)計(jì)可以充分彌補(bǔ)課

堂教學(xué)及普通實(shí)驗(yàn)中知識(shí)深度與廣度有限的缺陷，更好地幫助學(xué)生從全局角度把握課程體

系。

本書(shū)獨(dú)立于具體的C++語(yǔ)言教科書(shū)，重點(diǎn)放在C++語(yǔ)言的基本特征上，結(jié)合實(shí)際應(yīng)用，

通過(guò)詳細(xì)的實(shí)例，循序漸進(jìn)地啟發(fā)學(xué)生完成設(shè)計(jì)。書(shū)中給出的課題實(shí)例概念清楚，體系完整,

內(nèi)容豐富，采用循序漸進(jìn)的方式，提高學(xué)生實(shí)際動(dòng)手能力，完成“知識(shí)+實(shí)踐=技能”的整

個(gè)學(xué)習(xí)過(guò)程。

二、實(shí)驗(yàn)環(huán)境與教學(xué)要求

要求實(shí)驗(yàn)室配備微型電子計(jì)算機(jī)80臺(tái)，配置為奔騰PII以上，安裝Windows2000以上

操作系統(tǒng)，及VisualC++6.0以上版本的開(kāi)發(fā)環(huán)境。

要求教師在正確理解課程教學(xué)大綱的基礎(chǔ)上,結(jié)合課題體系的實(shí)際需求及學(xué)生的實(shí)踐能

力、工作條件等外部因素，選擇恰當(dāng)?shù)脑O(shè)計(jì)課題，既體現(xiàn)教學(xué)目的，乂能反映實(shí)際教學(xué)情況。

要求保證充足的實(shí)踐課時(shí)，最好配備專職指導(dǎo)教師。

要求同學(xué)們：

1.要充分認(rèn)識(shí)課程設(shè)計(jì)的重要性，認(rèn)真做好各項(xiàng)準(zhǔn)備工作；

2.既要虛心接受老師的指導(dǎo)，又要充分發(fā)揮主觀能動(dòng)性，要結(jié)合課題，獨(dú)立思考，努

力鉆研，勤于實(shí)踐，勇于創(chuàng)新：

3.收集資料，自學(xué)相關(guān)知識(shí)，拓寬知識(shí)面，根據(jù)課題的基本要求，自行完成設(shè)計(jì)任務(wù)。

4.在教師指導(dǎo)下，學(xué)習(xí)并掌握面向?qū)ο蟮某绦蛟O(shè)計(jì)知識(shí)，學(xué)習(xí)VC++中MFC編程，最

好能應(yīng)用MFC設(shè)計(jì)圖形界面的成果。

5.要按時(shí)、獨(dú)立完成規(guī)定的工作任務(wù)，不弄虛作假，不抄襲他人；

6.嚴(yán)格遵守學(xué)習(xí)和勞動(dòng)紀(jì)律，不無(wú)故缺席，不遲到早退，不懈怠，不拖拉，要積極主

動(dòng)；

7.嚴(yán)格要求自己，樹(shù)立嚴(yán)肅、嚴(yán)密、嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度，按時(shí)、按質(zhì)、按量完成；

8.互幫互助，要樹(shù)立團(tuán)隊(duì)協(xié)作精神。

三、實(shí)施原則、方案與步驟

制訂課程設(shè)計(jì)實(shí)施計(jì)劃時(shí)，要體現(xiàn)以下設(shè)計(jì)原則：

?以學(xué)生為主，要求獨(dú)立完成設(shè)計(jì)任務(wù)，注重培養(yǎng)學(xué)生自學(xué)能力、實(shí)踐能力、文檔撰

寫(xiě)能力、主動(dòng)探索精神。

?教師針對(duì)每位學(xué)生的知識(shí)基礎(chǔ)、實(shí)踐技能等提出具體要求，輔導(dǎo)要有側(cè)重，要因材

施教。對(duì)基礎(chǔ)差的要勤檢查、多指導(dǎo)，對(duì)能力強(qiáng)的要適時(shí)提高要求，增加選做內(nèi)容,

積極鼓勵(lì)，充分發(fā)揮其潛力。

?要求學(xué)生從點(diǎn)滴開(kāi)始，踏踏實(shí)實(shí)按規(guī)定去做，培養(yǎng)嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度。教育學(xué)生遵守

紀(jì)律，團(tuán)結(jié)協(xié)作，尊重他人。通過(guò)設(shè)計(jì)工作以提高業(yè)務(wù)能力，增強(qiáng)團(tuán)隊(duì)協(xié)作精神。

根據(jù)C++程序設(shè)計(jì)的課程特點(diǎn)，本課程設(shè)計(jì)采取集中與分散相結(jié)合的方式，安排在理論

教學(xué)完成后進(jìn)行，具體方案如下：

1.教師下達(dá)課程設(shè)計(jì)任務(wù)書(shū)

任務(wù)書(shū)內(nèi)容包括設(shè)計(jì)題目、主要技術(shù)指標(biāo)、要求、給定條件及原始數(shù)據(jù)、所用儀器設(shè)備

和參考資料及文獻(xiàn)等。教師可以視情況講授必要的設(shè)計(jì)思路和設(shè)計(jì)方法。

2.學(xué)生完成預(yù)設(shè)計(jì)

本階段學(xué)生應(yīng)明確任務(wù)，查閱資料及文獻(xiàn)，自學(xué)新知識(shí)、新技術(shù)，掌握設(shè)計(jì)的基本方法,

確定設(shè)計(jì)方案，進(jìn)行設(shè)計(jì)分析，完成預(yù)設(shè)計(jì)。

3.實(shí)驗(yàn)階段

經(jīng)教師審查通過(guò)預(yù)設(shè)計(jì)方案后，即可進(jìn)入實(shí)驗(yàn)室編程調(diào)試。實(shí)驗(yàn)由學(xué)生獨(dú)立完成，教師

僅作定時(shí)指導(dǎo)。

4.設(shè)計(jì)總結(jié)階段

本階段學(xué)生要認(rèn)真回顧，總結(jié)收獲，發(fā)現(xiàn)不足，整理技術(shù)資料，撰寫(xiě)課程設(shè)計(jì)報(bào)告書(shū)，

寫(xiě)出心得體會(huì)和改進(jìn)意見(jiàn)。

具體實(shí)施時(shí)，要根據(jù)具體情況，如課程大綱要求、實(shí)驗(yàn)環(huán)境、學(xué)生專業(yè)、層次及軟件水

平等，具體安排設(shè)計(jì)步驟。一般的設(shè)計(jì)步驟如下：

1.選題與搜集資料：根據(jù)分組，選擇課題，合理分工，進(jìn)行需求分析與系統(tǒng)調(diào)查，搜

集相關(guān)資料，了解涉及的理論基礎(chǔ)知識(shí)。

2.系統(tǒng)分析與預(yù)設(shè)計(jì)：根據(jù)課題要求及搜集的資料，進(jìn)行系統(tǒng)功能劃分，分析數(shù)據(jù)流

程，進(jìn)行模塊設(shè)計(jì)。

3.指導(dǎo)教師檢查每位學(xué)生的預(yù)設(shè)計(jì)結(jié)果，確定是否可以進(jìn)入下一步。

4.程序設(shè)計(jì)：預(yù)設(shè)計(jì)通過(guò)的學(xué)生進(jìn)入實(shí)驗(yàn)室，運(yùn)用VC++6.0集成環(huán)境，編寫(xiě)程序，實(shí)

現(xiàn)所設(shè)計(jì)的模塊功能。

5.調(diào)試與測(cè)試：自主調(diào)試程序，或同課題、同組成員交叉測(cè)試，并記錄測(cè)試情況。

6.成果驗(yàn)收：指導(dǎo)教師對(duì)每位同學(xué)設(shè)計(jì)的成果進(jìn)行驗(yàn)收，打成果成果成績(jī)。

7.布置設(shè)計(jì)成果通過(guò)驗(yàn)收的同學(xué)撰寫(xiě)課程設(shè)計(jì)報(bào)告。

8.課程設(shè)計(jì)答辯。

9.結(jié)合每位學(xué)生的軟件成果、工作態(tài)度、設(shè)計(jì)報(bào)告等，評(píng)定綜合成績(jī)。

四、設(shè)計(jì)課題

下面提供十個(gè)設(shè)計(jì)課題，涉及面有大有小，難度有深有淺，考察的知識(shí)點(diǎn)、體現(xiàn)的設(shè)計(jì)

目的也有所不同。指導(dǎo)教師可根據(jù)大綱要求，同學(xué)們的學(xué)習(xí)興趣、水平高低，指導(dǎo)學(xué)生選擇

適當(dāng)?shù)恼n題。同學(xué)們也可自擬設(shè)計(jì)課題，但必須征得指導(dǎo)老師同意。

(―)幻方

所謂幻方，就是一個(gè)n行n列的正方形，共有產(chǎn)個(gè)格子，將1、2、3.............「這些數(shù)

字放到這些格子里，使其每行的和、每列的利及兩條對(duì)角線的和都是一個(gè)相同的數(shù)S,S稱

為幻和。當(dāng)n為奇數(shù)時(shí)，稱為奇數(shù)階幻方，當(dāng)n為偶數(shù)時(shí)，稱為偶階幻方。當(dāng)n可被4整除

時(shí)，稱方為雙偶幻方。當(dāng)n不可被4整除時(shí)，稱為單偶幻方。

多少年來(lái)，許多數(shù)學(xué)家都在研究這個(gè)古老而有趣的問(wèn)題，試圖找出般的解法，但-?般

都是針對(duì)當(dāng)n是奇數(shù)和n是4的倍數(shù)的情況。

當(dāng)n是奇數(shù)時(shí)的算法：

首先，將1放在第一行中間一個(gè)格子里。

其次，依次將后一個(gè)數(shù)放到前一個(gè)數(shù)的右上格，如：將2放到1的右上格。將3放到2

的右上格等等?？赡艹霈F(xiàn)下面的情況。

①若右上格從上面超出，則將后一數(shù)放到與右上格同列的最后?行。

②若右上格從右面超出，則將后一數(shù)放到與右上格同行的最后一列。

③若右上格既從右面超出又從上面超出，則將后一數(shù)放到前一數(shù)的下面。

④若右上格已被數(shù)字填充，則將后一數(shù)放到前一數(shù)的下面

依以上法則，你可以很快的寫(xiě)出奇數(shù)階幻方！當(dāng)然，這中寫(xiě)法只是其中?個(gè)答案，而不

是唯一答案。

1.奇數(shù)階幻方的制作

(1)連續(xù)擺數(shù)法

例：一個(gè)5/5格子，由最上面一行中間一格開(kāi)始，依次填1,2,3等等。下一個(gè)格子填在

左上位置。但是要注意兩點(diǎn)：

>出了幻方的范圍，右邊接到左邊，下邊接到上邊。

>某一格右上已經(jīng)有了數(shù)字，改填在這個(gè)格子的下面一格，然后延續(xù)前面的方法。

17241815

23571416

46132022

101219213

11182529

也不一定按照斜上方寫(xiě)字，可以走馬步，或其他方法。下面用的是馬步，得到的是泛對(duì)

角幻方。

81711524

11259182

193122110

22620413

51423716

哪些“步子”是可行的，是需要注意的一個(gè)問(wèn)題。

(2)階梯法

例：以5階為例。

第一步：畫(huà)一個(gè)9x9的方格。如下斜著填數(shù)字。注意中間的5x5格子才是要作的幻方

的位置，已經(jīng)涂成了黃色。

第二步：黃色范圍以外的數(shù)字，平移到黃色格子中沒(méi)有數(shù)字的位置。

去掉外圍的格子，就得到所要作的幻方。

31692215

20821142

72513119

24125186

114171023

2.偶數(shù)階幻方的制作

偶數(shù)階幻方的制作比較復(fù)雜，下面介紹幾個(gè)方法。

(1)對(duì)稱法，適用于雙偶數(shù)階幻方

例：以8階幻方為例。

第一步：在左上4x4格子中，取一半的格子，要求每行每列都取到2個(gè)。如下圖黃色

格子所示。

第二步：按照左右對(duì)稱、上下對(duì)稱、中心對(duì)稱的方法把這8個(gè)格子擴(kuò)充為32個(gè)格子。

第三步：從左上角開(kāi)始，從左到右從上到下，從1開(kāi)始填數(shù)。不過(guò)只填沒(méi)有選中的格子

(即沒(méi)有涂黃色的格子)

2-157

9111416

17192224

26282931

34363739

41434648

49515456

58606163

第四步：從右下角開(kāi)始從右到左從下到上在選中的格子里填進(jìn)剛才沒(méi)有填的數(shù)字。

642624559757

955115352145016

1747194544224224

4026382829353133

3234303637273925

4123432120461848

4915511312541056

858660613631

制作成功。

這個(gè)方法可以產(chǎn)生不同的雙偶數(shù)階幻方。

思考：能否算出這個(gè)方法可以產(chǎn)生多少個(gè)8階幻方？

(2)斯特雷奇法，適用于單偶數(shù)幻方

例：設(shè)階數(shù)n=2(2m+1)=6,m=1。

第一步：把方陣分為4個(gè)小方陣，位置依次為A左上，B右下，C右上，D左下。

用連續(xù)擺數(shù)法，把l-aA2放在A中成第一個(gè)幻方；把92+1?2az'2放在B中成第二

個(gè)幻方。把2aA2+1?3a人2放在C中成第三個(gè)幻方。把3aA2+1?4aA2放在D中成第四個(gè)幻

方。

816261924

357212325

492222720

352833171015

303234121416

313629131822

換。

3516261924

3327212325

3192222720

82833171015

30534121416

43629131822

（3）LUX方法這是劍橋大學(xué)康韋教授發(fā)明的方法

例：設(shè)階數(shù)n=2（2m+l尸10,m=2。

第一步：任取一個(gè)2m+l階幻方，例如5階幻方。如下。

12316421

151471811

24171392

20819126

53102225

第二步：在上面的m+1行（此處為3行）的每個(gè)格子里填入一個(gè)字母L；接下去一行填

字母U,余下m-l行填字母X。最后把中間的一個(gè)L與它下面的一個(gè)U交換一下。

1L23L16L4L21L

15L14L7L18L11L

24L17L13U9L2L

20U8U19L12U6U

5X3X10X22X25X

第三步：作一個(gè)10x1。方格，設(shè)想為每2x2為一個(gè)單位，每個(gè)單位相應(yīng)于上面一個(gè)格子。

對(duì)應(yīng)于5階幻方中數(shù)字1的單位填1,2,3,4o對(duì)應(yīng)于5階幻方中數(shù)字2的填5,6,7,8。

等等。但是標(biāo)有字母L的按照“右上一左下一右下一左上“次序；標(biāo)有字母U的按照“左上

一左下一右下一右上“次序；標(biāo)有字母X的按照“左上一右下一左下一右上“次序。

419289646116138481

239091626314158283

60575653282572694441

58595455262770714243

969368654952363385

949566675051343567

77802932767345482124

78793031747546472223

17209123740858897100

19181110393887869998

當(dāng)然，這個(gè)方法也產(chǎn)生很多幻方，并不唯一。

3.設(shè)計(jì)要求

編寫(xiě)代碼，實(shí)現(xiàn)奇、偶數(shù)幻方的制作。運(yùn)行程序后，出現(xiàn)下面的參考界面:

幻方制作

1.奇數(shù)階幻方

2.偶數(shù)階幻方

請(qǐng)選擇（1或2,0：退出）:

選擇一個(gè)菜單后，要求輸入幻方的階數(shù)n。n的取值范圍為3?10。輸入n后，首先判斷

是否存在對(duì)應(yīng)階的幻方，如果存在，則顯示幻方制作效果。

（-）矩陣操作

1.矩陣翻轉(zhuǎn)

沿某中心軸翻轉(zhuǎn)，或垂直，或水平翻轉(zhuǎn)。翻轉(zhuǎn)的實(shí)質(zhì)是，矩陣的每行（或每列）元素進(jìn)

行倒序排放。

01230123

12；4121241,21

65：923239;56

38:734341；83

4556：67787867!5645

2.矩陣卷動(dòng)

可以左右、上下卷動(dòng)。如下圖:

01230123

1241224121

6592359236

3873487343

4556677856677845

——A-----------/

矩陣卷動(dòng)涉及二個(gè)問(wèn)題：

(1)卷動(dòng)方向，或左右卷動(dòng)，或上下卷動(dòng)。

(2)卷動(dòng)幅度T,如上下卷動(dòng)行數(shù)，左右卷動(dòng)列數(shù)。

卷動(dòng)的實(shí)質(zhì)是將某行或某列元素循環(huán)移位。上卜一卷動(dòng)時(shí)，是將每列元素循環(huán)移位，左右

卷動(dòng)時(shí)是將每行元素循環(huán)移位，卷動(dòng)方向決定是左移還是右移。

一維數(shù)組的循環(huán)移位問(wèn)題：

如，已知inttemp[10],將其循環(huán)右移一位。

顯然，移位后，

temp[8]~temp[O]

依次存入

temp[9]~temp[l]

而原來(lái)的temp[9]則返回?cái)?shù)組起始部位，存入temp[O]?

那么，循環(huán)右移W位呢？循環(huán)左移W位呢？

了解了一維數(shù)組循環(huán)移位問(wèn)題后，顯然，矩陣卷動(dòng)無(wú)非是多個(gè)一維數(shù)組循環(huán)移位，只要

在外層加個(gè)大循環(huán)就解決了。

3.矩陣旋轉(zhuǎn)

矩陣旋轉(zhuǎn)(繞中心點(diǎn))涉及二個(gè)方面：

(1)旋轉(zhuǎn)方向，順時(shí)針還是逆時(shí)針。

(2)旋轉(zhuǎn)角度,如90°、180°、270°,360°等。

分析：

(1)考慮旋轉(zhuǎn)方向、角度

(2)此處僅考慮方陣情況，即矩陣行、列數(shù)相同。

(3)考慮是奇次方陣還是偶次方陣。

(4)旋轉(zhuǎn)時(shí)，實(shí)質(zhì)是數(shù)組元素的重新組合，對(duì)應(yīng)交換元素值。

(5)設(shè)方陣有K圈，每圈操作過(guò)程相似。

因此，問(wèn)題的關(guān)鍵是某圈元素的旋轉(zhuǎn)、交換。

如下圖。

考慮幾種特殊情況，如90°,180°,270°,360°等。

（1）其它角度都是90°的整數(shù)倍.因此，設(shè)計(jì)時(shí)僅需要考慮90°情況，其它情況只需

重復(fù)操作若干次即可。以順時(shí)針旋轉(zhuǎn)為例，如需旋轉(zhuǎn)180°,只需將旋轉(zhuǎn)90°操作連續(xù)

執(zhí)行兩次即能實(shí)現(xiàn)。

（2）逆時(shí)針旋轉(zhuǎn)可以看作為“過(guò)度”旋轉(zhuǎn)，如逆時(shí)針旋轉(zhuǎn)90°,可認(rèn)為是順時(shí)針旋轉(zhuǎn)270

當(dāng)然，也可設(shè)計(jì)新的交換規(guī)則。

4.設(shè)計(jì)要求

編寫(xiě)代碼，實(shí)現(xiàn)矩陣的翻轉(zhuǎn)、卷動(dòng)和旋轉(zhuǎn)。運(yùn)行程序后，隨機(jī)生成一個(gè)元素為三位正整

數(shù)的5X5矩陣，并顯現(xiàn)下面的參考界面：

矩陣操作

1.矩陣翻轉(zhuǎn)

2.矩陣卷動(dòng)

3.矩陣旋轉(zhuǎn)

請(qǐng)選擇（1、2或3,0：退出）:

選擇?個(gè)菜單后，要求輸入操作的方向、行數(shù)或列數(shù)或角度，輸入后，顯示操作結(jié)果。

（三）漢諾塔

1.基本涵義

在印度，有這么一個(gè)古老的傳說(shuō)：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊

黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時(shí)候，在其中一根針上從下到上

地穿好了由大到小的64片金片，這就是所謂的漢諾塔（如下圖）。不論白天黑夜，總有一

個(gè)僧侶在按照下面的法則移動(dòng)這些金片：一次只移動(dòng)一片，不管在哪根針上，小片必在大片

匕面。當(dāng)所有的金片都從梵天穿好的那根針上移到另外?概針上時(shí)，世界就將在一聲霹靂中

消滅，梵塔、廟宇和眾生都將同歸于盡。故漢諾塔問(wèn)題又被稱為“世界末日問(wèn)題?！?/p>

漫舟塔周篇的初始模型

611II__________

ABC

這是一個(gè)典型問(wèn)題。由于問(wèn)題中給出的圓盤(pán)移動(dòng)條件是：一次僅能移動(dòng)一個(gè)盤(pán)，且不允

許大盤(pán)放在小盤(pán)的上面，這樣64個(gè)盤(pán)子的移動(dòng)次數(shù)為：

18,446,744,073,709,511,615（次）

這是個(gè)天文數(shù)字，若每一微秒可以計(jì)算（并不輸出）?次移動(dòng)，那麼也需要幾乎一百萬(wàn)

年。我們僅能找出問(wèn)題的解決方法并解決較小N值時(shí)的漢諾塔，但目前計(jì)算機(jī)的速度還不能

解決64曾的漢諾塔。

2.常規(guī)解法

按照上面的方法分析問(wèn)題，找到移動(dòng)圓盤(pán)的的遞歸算法：

設(shè)要解決的的漢諾塔共有N個(gè)圓盤(pán)，對(duì)A桿上的全部N個(gè)圓盤(pán)從小到大順序編號(hào)，最小

的圓盤(pán)為1號(hào)，次之為2號(hào)，依次類推，則最下面的圓盤(pán)的編號(hào)為N。

第一步：先將問(wèn)題簡(jiǎn)化。假設(shè)A桿上只有一個(gè)圓盤(pán)，即漢諾塔只有一層N1,則只要

將1號(hào)盤(pán)從A桿上移到B桿上即可。

第二步：對(duì)於一個(gè)有N（N>1）個(gè)圓盤(pán)的漢諾塔，將N個(gè)圓盤(pán)分成兩部分：上面的N

-1個(gè)圓盤(pán)和最下面的N號(hào)圓盤(pán)。

第三步：將“上面的N—1個(gè)圓盤(pán)”看成一個(gè)整體，為了解決N個(gè)圓盤(pán)的漢諾塔，可以

按下面圖示的方式逕行操作：

（1）將A桿上面的N—1個(gè)盤(pán)子，借助B桿，移到C桿上；

（2）將A桿上剩余的N號(hào)盤(pán)子移到B桿上;

1

2

L…

\N-1

BC

（3）將C桿上的N―1個(gè)盤(pán)子，借助A桿，移到B桿上。

I2

II…

,r--------h,N-I

_________NII___________

ABC

整理上述結(jié)果，把第一步中化簡(jiǎn)問(wèn)題的條件作為遞歸結(jié)束條件，將第三步分析得到的算

法作為遞歸算法，可以寫(xiě)出如下完整得遞歸算法描述。

3.設(shè)計(jì)要求

編寫(xiě)代碼，用兩種方法解決盤(pán)子的移動(dòng)。運(yùn)行程序后，顯現(xiàn)下面的參考界面:

漢諾塔

1.遞歸解法

2.非遞歸解法

請(qǐng)選擇（1或2,0：退出）:

選擇?個(gè)菜單后，要求輸入盤(pán)片數(shù)目，輸入后，顯示移動(dòng)過(guò)程及結(jié)果。

(四)八皇后

1.基本涵義

八皇后問(wèn)題是一個(gè)古老而著名的問(wèn)題。該問(wèn)題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提

出：在8X8格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處

于同一行、同一列或同一斜線上，問(wèn)有多少種擺法。

高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解,

后來(lái)有人用圖論的方法解出92種結(jié)果。

顯然問(wèn)題的鍵在于如何判定某個(gè)皇后所在的行、歹U、斜線上是否有別的皇后；可以從矩

陣的特點(diǎn)上找到規(guī)律，如果在同一行，則行號(hào)相同；如果在同一列上，則列號(hào)相同；如果同

在“/”斜線上的行列值之和相同；如果同在“\”斜線上的行列值之差相同；如果斜線不

分方向，則同一斜線上兩皇后的行號(hào)之差的絕對(duì)值與列號(hào)之差的絕對(duì)值相同。從下圖可以驗(yàn)

證上面的說(shuō)法：

對(duì)于一組布局我們可以用?個(gè)一維數(shù)組來(lái)表示：X:ARRAY[1..8]OFINTEGER;X[I]的下

標(biāo)I表示第I個(gè)皇后在棋盤(pán)的第I行，X[I]的內(nèi)容表示在第I行的第X[I]列，例如：X[3]=5

就表示第3個(gè)皇后在第3行的第5歹h在這種方式下，要表示兩個(gè)皇后A和B不在同一列

或斜線上的條件可以描述為：

X[A]oX[B]ANDABS(A-B)oABS(X[A]-X[B]){A和B分別表示兩個(gè)皇后的行號(hào)}。

2.設(shè)計(jì)要求

編寫(xiě)代碼，用至少三種方法解決八皇后問(wèn)題。運(yùn)行程序后，顯現(xiàn)下面的參考界面：

八皇后問(wèn)題I

1.方法一

2.方法二

3.方法三

請(qǐng)選擇（1、2或3,0：退出）:

選擇一個(gè)菜單后，要求輸入棋盤(pán)的階層，即N。輸入后，顯示共有多少種布局方案，并

顯示每一種方案的具體情況，如下圖：

77:(0,2)(1,0)(2,6)(3,4)(4,7)(5,1)(6,3)(7,5)

78:(0,7)(1,1)(2,4)(3,2)(4,0)(5,6)(6,3)(7,5)

第77種狀態(tài)為:第78種狀態(tài)為:

******@*****@***

Q********@******

（五）成績(jī)管理

1.設(shè)計(jì)要求

由于同學(xué)們已經(jīng)學(xué)習(xí)了指針、鏈表、文件讀寫(xiě)等基本知識(shí)，為了與后續(xù)課程，如數(shù)據(jù)結(jié)

構(gòu)、數(shù)據(jù)庫(kù)系統(tǒng)等有一個(gè)知識(shí)體系上的銜接，特設(shè)置一個(gè)信息管理類的課題《成績(jī)管理系統(tǒng)》,

其它諸如人事管理、學(xué)籍管理、圖書(shū)管理、通訊錄管理等，結(jié)構(gòu)類似，僅管理對(duì)象有所不同。

管理內(nèi)容包括：

學(xué)號(hào)、姓名、班級(jí)、五門(mén)課成績(jī)。

主要功能有：

添加、修改、刪除、讀出、寫(xiě)入、查找、排序、計(jì)算總分、平均分、分類匯總等。

編寫(xiě)代碼，運(yùn)行程序后，顯現(xiàn)下面的參考界面：

成績(jī)管理

輸入學(xué)生成績(jī)

修改學(xué)生成績(jī)

刪除學(xué)生成績(jī)

計(jì)算每位學(xué)生的總分

計(jì)算每位學(xué)生的平均分

按學(xué)號(hào)或姓名查詢學(xué)生成績(jī)

按班級(jí)查詢學(xué)生成績(jī)

8.成績(jī)排序

9.按班級(jí)統(tǒng)計(jì)學(xué)科總分、平均分等

請(qǐng)選擇（1~9,0：退出）：

選擇一個(gè)菜單后，顯示結(jié)果。

2.參考代碼

#include"stdio.h”/*1/0函數(shù)*/

#include“stdlib.h”/*其它說(shuō)明*/

//includenstring.h"/*字符串函數(shù)*/

#include"conio.h"/*屏幕操作函數(shù)*/

#include"mem.hH/*內(nèi)存操作函數(shù)*/

#include"ctype.h"/*字符操作函數(shù)*/

#include"alloc.h"/*動(dòng)態(tài)地址分配函數(shù)*/

#defineN3/*定義常數(shù)*/

typedefstructzl/*定義數(shù)據(jù)結(jié)構(gòu)*/

charno[l1];

charname[15];

intscore[N];

floatsum;

floataverage;

intorder;

structzl*next;

}STUDENT;

/*以下是函數(shù)原型*/

STUDENT*init();/*初始化函數(shù)*/

STUDENT*create();/*創(chuàng)建鏈表*/

STUDENT*delete(STUDENT*h);/*刪除記錄*/

voidprint(STUDENT*h);/*顯示所有記錄*/

voidsearch(STUDENT*h);/*查找*/

voidsave(STUDENT*h);/*保存*/

STUDENT*load();/*讀入記錄*/

voidcomputer(STUDENT*h);/*計(jì)算總分和均分*/

STUDENT*insert(STUDENT*h);/*插入記錄*/

voidappend();/*追加記錄*/

voidcopy();/*復(fù)制文件*/

STUDENT*sort(STUDENT*h);/*排序*/

STUDENT*index(STUDENT*h);/*索弓I*/

voidtotal(STUDENT*h);/*分類合計(jì)*/

intmenu_select();/*菜單函數(shù)*/

/******主函數(shù)開(kāi)始*******/

main()

inti;

STUDENT*head;/*鏈表定義頭指針*/

head=init();/*初始化鏈表*/

clrscr();/*清屏*/

for(;;)/*無(wú)限循環(huán)*/

(

switch(menu_select())/*調(diào)用主菜單函數(shù)，返回值整數(shù)作開(kāi)關(guān)語(yǔ)句的條件*/

{/*值不同，執(zhí)行的函數(shù)不同，b