版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、課課 程程 設(shè)設(shè) 計計2012 年12 月21日目錄目錄1、概述、概述.42 2、實驗?zāi)康摹嶒災(zāi)康?43 3、問題分析、問題分析.54 4、實驗步驟、實驗步驟.55 5、流程圖、流程圖.66 6、程序代碼:、程序代碼:.77 7、程序調(diào)試與測試、程序調(diào)試與測試.108 8、結(jié)論、結(jié)論.129 9、總結(jié)、總結(jié).15一、概述一、概述數(shù)據(jù)結(jié)構(gòu)是計算機(jī)學(xué)科非常重要的一門專業(yè)基礎(chǔ)理論課程,要想編寫針對非數(shù)值計算問題的高質(zhì)量程序,就必須要熟練的掌握這門課程設(shè)計的知識。另外,他與計算機(jī)其他課程都有密切聯(lián)系,具有獨特的承上啟下的重要位置。擁有數(shù)據(jù)結(jié)構(gòu)這門課程的知識準(zhǔn)備,對于學(xué)習(xí)計算機(jī)專業(yè)的其他課程,如操作系
2、統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)、軟件工程的都是有益的。二、實驗?zāi)康亩嶒災(zāi)康?通過本實驗,掌握復(fù)雜性問題的分析方法,了解漢諾塔游戲的時間復(fù)雜性和空間復(fù)雜性。 三、問題分析三、問題分析任務(wù):有三個柱子 A, B, C. A 柱子上疊放有 n 個盤子,每個盤子都比它下面的盤子要小一點,可以從上到下用 1, 2, ., n 編號。要求借助柱子 B,把柱子 A 上的所有的盤子移動到柱子C 上。移動條件為:1、一次只能移一個盤子;2、移動過程中大盤子不能放在小盤子上,只能小盤子放在大盤子上。分析:首先容易證明,當(dāng)盤子的個數(shù)為 n 時,移動的次數(shù)應(yīng)等于 2n - 1。首先把三根柱子按順序排成品字型,把所有的圓盤按從
3、大到小的順序放在柱子 A 上。根據(jù)圓盤的數(shù)量確定柱子的排放順序:若 n 為偶數(shù),按順時針方向依次擺放 A B C;若 n 為奇數(shù),按順時針方向依次擺放 A C B。(1)按順時針方向把圓盤 1 從現(xiàn)在的柱子移動到下一根柱子,即當(dāng) n 為偶數(shù)時,若圓盤1 在柱子 A,則把它移動到 B;若圓盤 1 在柱子 B,則把它移動到 C;若圓盤 1 在柱子 C,則把它移動到 A。(2)接著,把另外兩根柱子上可以移動的圓盤移動到新的柱子上。即把非空柱子上的圓盤移動到空柱子上,當(dāng)兩根柱子都非空時,移動較小的圓盤這一步?jīng)]有明確規(guī)定移動哪個圓盤,你可能以為會有多種可能性,其實不然,可實施的行動是唯一的。反復(fù)進(jìn)行(1
4、)(2)操作,最后就能按規(guī)定完成漢諾塔的移動。四、實驗步驟四、實驗步驟 1、用 c+ 或 c 語言設(shè)計實現(xiàn)漢諾塔游戲;,2、讓盤子數(shù)從 2 開始到 7 進(jìn)行實驗,記錄程序運行時間和遞歸調(diào)用次數(shù);3、畫出盤子數(shù) n 和運行時間 t 、遞歸調(diào)用次數(shù) m 的關(guān)系圖,并進(jìn)行分析。五、流程圖五、流程圖開始輸入 m(m=20)是否繼續(xù)結(jié)束輸出結(jié)果2、否1、是 六、程序代碼:六、程序代碼:#include #include / Hanoi 塔class Hanoipublic:Hanoi()cout floor;if (floor 20)cout 層數(shù)錯誤重新輸入:;goto input;cout endl
5、;arrayA = new char *floor;arrayB = new char *floor;arrayC = new char *floor;for (int h = 0; h floor; h+)arrayAh = new charfloor + 1;arrayBh = new charfloor + 1;arrayCh = new charfloor + 1;for(int i = 0; i floor; i+)for(int j = 0; j floor + 1; j+)arrayAij = 0;arrayBij = 0;arrayCij = 0;for(int n = 0;
6、n floor; n+)for(int m = 0; m = n; m+)arrayAnm = #;stepcount = 0;void HanoiShow()hanoiShow(floor, arrayA, arrayB, arrayC);void Display()system(cls);cout 第 stepcount 步 endl;int i;int j;for(i = 0; i floor + 1; i+)if(i = 0)cout A;elsecout ;cout ;for(i = 0; i floor + 1; i+)if(i = 0)cout B;elsecout ;cout
7、;for(i = 0; i floor + 1; i+)if(i = 0)cout C;elsecout ;cout endl;for(i = 0; i floor; i+)for(j = 0; j floor + 1; j+)cout arrayAij;cout ;for(j = 0; j floor + 1; j+)cout arrayBij;cout ;for(j = 0; j floor + 1; j+)cout arrayCij;cout endl;system(pause);Hanoi()for (int i = 0; i 0)hanoiShow(n - 1, A, C, B);m
8、ove(n, A, B);hanoiShow(n - 1, C, B, A);elsereturn;void move(int n, char *D, char *S)int dc = -1;int sc = -1;int i;int j;for(i = 0; i floor; i+)if(Di0 = #)dc = i;break;for(j = 0; j floor; j+)if(Sj0 = #)sc = j - 1;break;if(sc = -1)sc = floor - 1;for(int k = 0; k floor + 1; k+)Ssck = Ddck;Ddck = 0;step
9、count+;Display();int stepcount;int floor;char *arrayA;char *arrayB;char *arrayC;#endif自定義頭文件#include stdafx.h#include Hanoi.h七、程序調(diào)試與測試七、程序調(diào)試與測試在編譯過程中發(fā)現(xiàn)錯誤經(jīng)查找之后發(fā)現(xiàn)沒有對主函數(shù) main 說明經(jīng)改正后運行結(jié)果運行結(jié)果第一步第一步先輸入要玩的層數(shù)第二步第二步手動運行手動運行八、結(jié)論八、結(jié)論通過對上述遞歸在 Hanoi 塔問題上的應(yīng)用分析,我們可以得出如下結(jié)論:1、遞歸調(diào)用過程中,在程序執(zhí)行之前無法知道控制這種調(diào)用棧的規(guī)模,因為這一規(guī)模取決于遞歸調(diào)用的次序。在這種情況下,程序的地址空間可能動態(tài)變化;2、遞歸應(yīng)用于程序設(shè)計時,結(jié)構(gòu)清晰、程序易讀,編制和調(diào)試程序很方便,不需要用戶自行管理遞歸工作棧。但遞歸應(yīng)用于計算機(jī)時需要占用大量系統(tǒng)資源(包括堆棧、軟中斷和存貯空間等),并消耗大量處理時間。因此,可以考慮采用并行計算進(jìn)
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 二零二五年度民爆工程項目質(zhì)量保證合同4篇
- 2025年度出國定居家居裝飾與裝修設(shè)計合同4篇
- 二零二五年度二手車貸保證金合同范本4篇
- 2025年旅游度假區(qū)場地租賃及運營管理合同3篇
- 二零二五版高端家居導(dǎo)購代理合同2篇
- 二零二五年度高速公路路面施工合同范本4篇
- 2025年淘寶平臺電商數(shù)據(jù)分析與運營合同范本2篇
- 2025年度池塘水域漁業(yè)資源保護(hù)與利用合同樣本4篇
- 2025版健康養(yǎng)生產(chǎn)品銷售合同范例(含專家咨詢)2篇
- 二零二五年度礦山錨桿錨鎖設(shè)計及施工一體化合同4篇
- 招標(biāo)師《招標(biāo)采購項目管理》近年考試真題題庫(含答案解析)
- 微生物組與唾液腺免疫反應(yīng)-洞察分析
- 2024公共數(shù)據(jù)授權(quán)運營實施方案
- 《向心力》 教學(xué)課件
- 結(jié)構(gòu)力學(xué)數(shù)值方法:邊界元法(BEM):邊界元法的基本原理與步驟
- 北師大版物理九年級全一冊課件
- 2024年第三師圖木舒克市市場監(jiān)督管理局招錄2人《行政職業(yè)能力測驗》高頻考點、難點(含詳細(xì)答案)
- RFJ 006-2021 RFP型人防過濾吸收器制造與驗收規(guī)范(暫行)
- 盆腔炎教學(xué)查房課件
- 110kv各類型變壓器的計算單
- 新概念英語課件NCE3-lesson15(共34張)
評論
0/150
提交評論