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

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

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

于永彥趙建洋

江蘇淮陰工學(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

（五）成績管理................................................................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.棧的存儲和運(yùn)算.........................................................67

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

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

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

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

六、成績評定......................................................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è)的最重要的一門專業(yè)基礎(chǔ)

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

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

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

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

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

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

系。

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

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

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

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

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

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

操作系統(tǒng)，及VisualC++6.0以上版本的開發(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è)計(jì)的重要性，認(rèn)真做好各項(xiàng)準(zhǔn)備工作；

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

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

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

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

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

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

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

動(dòng)；

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

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

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

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

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

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

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

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

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

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

紀(jì)律，團(tuán)結(jié)協(xié)作，尊重他人。通過設(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ù)書

任務(wù)書內(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è)計(jì)的基本方法,

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

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

經(jīng)教師審查通過預(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ù)資料，撰寫課程設(shè)計(jì)報(bào)告書，

寫出心得體會和改進(jì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ǔ)知識。

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ì)通過的學(xué)生進(jìn)入實(shí)驗(yàn)室，運(yùn)用VC++6.0集成環(huán)境，編寫程序，實(shí)

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

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

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

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

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

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

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

下面提供十個(gè)設(shè)計(jì)課題，涉及面有大有小，難度有深有淺，考察的知識點(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ù)

字放到這些格子里，使其每行的和、每列的利及兩條對角線的和都是一個(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í)，稱為單偶幻方。

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

都是針對當(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ù)的下面

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

是唯一答案。

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

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

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

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

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

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

17241815

23571416

46132022

101219213

11182529

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

角幻方。

81711524

11259182

193122110

22620413

51423716

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

(2)階梯法

例：以5階為例。

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

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

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

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

31692215

20821142

72513119

24125186

114171023

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

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

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

例：以8階幻方為例。

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

格子所示。

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

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

(即沒有涂黃色的格子)

2-157

9111416

17192224

26282931

34363739

41434648

49515456

58606163

第四步：從右下角開始從右到左從下到上在選中的格子里填進(jìn)剛才沒有填的數(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è)格子。

對應(yīng)于5階幻方中數(shù)字1的單位填1,2,3,4o對應(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ì)要求

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

幻方制作

1.奇數(shù)階幻方

2.偶數(shù)階幻方

請選擇（1或2,0：退出）:

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

是否存在對應(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è)問題：

(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)移位問題：

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

顯然，移位后，

temp[8]~temp[O]

依次存入

temp[9]~temp[l]

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

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

了解了一維數(shù)組循環(huán)移位問題后，顯然，矩陣卷動(dòng)無非是多個(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ù)組元素的重新組合，對應(yīng)交換元素值。

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

因此，問題的關(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)可以看作為“過度”旋轉(zhuǎn)，如逆時(shí)針旋轉(zhuǎn)90°,可認(rèn)為是順時(shí)針旋轉(zhuǎn)270

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

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

編寫代碼，實(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)

請選擇（1、2或3,0：退出）:

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

（三）漢諾塔

1.基本涵義

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

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

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

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

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

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

漫舟塔周篇的初始模型

611II__________

ABC

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

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

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

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

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

解決64曾的漢諾塔。

2.常規(guī)解法

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

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

的圓盤為1號，次之為2號，依次類推，則最下面的圓盤的編號為N。

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

將1號盤從A桿上移到B桿上即可。

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

-1個(gè)圓盤和最下面的N號圓盤。

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

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

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

（2）將A桿上剩余的N號盤子移到B桿上;

1

2

L…

\N-1

BC

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

I2

II…

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

_________NII___________

ABC

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

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

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

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

漢諾塔

1.遞歸解法

2.非遞歸解法

請選擇（1或2,0：退出）:

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

(四)八皇后

1.基本涵義

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

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

于同一行、同一列或同一斜線上，問有多少種擺法。

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

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

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

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

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

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

證上面的說法：

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

標(biāo)I表示第I個(gè)皇后在棋盤的第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è)皇后的行號}。

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

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

八皇后問題I

1.方法一

2.方法二

3.方法三

請選擇（1、2或3,0：退出）:

選擇一個(gè)菜單后，要求輸入棋盤的階層，即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********@******

（五）成績管理

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

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

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

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

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

學(xué)號、姓名、班級、五門課成績。

主要功能有：

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

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

成績管理

輸入學(xué)生成績

修改學(xué)生成績

刪除學(xué)生成績

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

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

按學(xué)號或姓名查詢學(xué)生成績

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

8.成績排序

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

請選擇（1~9,0：退出）：

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

2.參考代碼

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

#include“stdlib.h”/*其它說明*/

//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ù)開始*******/

main()

inti;

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

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

clrscr();/*清屏*/

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

(

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

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