《新漢諾塔》課程設(shè)計(jì)

屆課程設(shè)計(jì)?漢諾塔?課程設(shè)計(jì)說明書學(xué)生姓名學(xué)號(hào)所屬學(xué)院信息工程學(xué)院專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)指導(dǎo)教師教師職稱講師塔里木大學(xué)教務(wù)處制目錄TOC\o"1-3"\h\u23410前言 143531.數(shù)據(jù)結(jié)構(gòu)簡介 1189322.應(yīng)用技術(shù)領(lǐng)域及范圍 173383.設(shè)計(jì)的原理、方法和主要內(nèi)容 119591正文 289331.設(shè)計(jì)目的 251502.設(shè)計(jì)要求 2125173.需求分析 2248113.1漢諾塔的由來： 2303963.2漢諾塔與宇宙壽命： 3227344.問題分析： 4185515.概要設(shè)計(jì) 5303485.1設(shè)計(jì)思想 5309895.2實(shí)現(xiàn)方法 5326365.3主要模塊 5260585.4模塊關(guān)系 571066.詳細(xì)設(shè)計(jì) 5322906.1功能設(shè)計(jì) 5198036.2算法分析 6130736.3編寫程序如下： 693456.4程序執(zhí)行過程分析： 7210987.調(diào)試分析： 7107798.小結(jié) 1025445致謝 1123446參考文獻(xiàn) 11前言1.數(shù)據(jù)結(jié)構(gòu)簡介數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)程序設(shè)計(jì)的重要理論設(shè)計(jì)根底，它不僅是計(jì)算機(jī)學(xué)科的核心課程，而且成為其他理工專業(yè)的熱門選修課。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲(chǔ)效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象〔數(shù)據(jù)元素〕以及它們之間的關(guān)系和運(yùn)算等的學(xué)科，而且確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。“數(shù)據(jù)結(jié)構(gòu)〞在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)根底課。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程。數(shù)據(jù)結(jié)構(gòu)這一門課的內(nèi)容不僅是一般程序設(shè)計(jì)〔特別是非數(shù)值性程序設(shè)計(jì)〕的根底，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序的重要根底。2.應(yīng)用技術(shù)領(lǐng)域及范圍漢諾塔的應(yīng)用技術(shù)是來自于我們所學(xué)的數(shù)據(jù)知識(shí)和數(shù)學(xué)方面的學(xué)科，其中用到了數(shù)學(xué)遞歸，函數(shù)和數(shù)據(jù)的函數(shù)以及C語言等方面的知識(shí)。漢諾塔的領(lǐng)域是在我的日常生活中的每一個(gè)細(xì)節(jié)中，反復(fù)的運(yùn)用是我的數(shù)學(xué)知識(shí)在生活的表達(dá)，如做歸一問題，循環(huán)問題，倒排問題，邏輯思維的相關(guān)問題等都要運(yùn)用到我悶得漢諾塔原理。漢諾塔的范圍來自每一個(gè)知識(shí)的指導(dǎo)，和生活中的運(yùn)用。在我們的世界不是一成不變的，而是時(shí)時(shí)刻刻都在發(fā)生著變化，但一切的變化都沒有脫離我們這個(gè)世界的規(guī)那么。3.設(shè)計(jì)的原理、方法和主要內(nèi)容漢諾塔的設(shè)計(jì)原理是我們所學(xué)的數(shù)據(jù)結(jié)構(gòu)與遞歸原理的應(yīng)用，并且是在數(shù)據(jù)老師的指導(dǎo)下編寫的源程序。得到了自己所設(shè)計(jì)的結(jié)果。漢諾塔的方法是把n個(gè)盤子從柱子1移到柱子3〔利用柱子2〕，第一步，把n-1個(gè)盤子從柱子1移到柱子2〔利用柱子3〕，第二步，把柱子1剩下的最大的盤子移到柱子3，第三步，把n-1個(gè)盤子從柱子2移到柱子3〔利用柱子1〕。每一個(gè)的移動(dòng)都是所有的東西動(dòng)，一個(gè)動(dòng)就會(huì)把所有的邏輯打亂并且得不到所要測(cè)得結(jié)果。偏離我這此所設(shè)計(jì)的初終。漢諾塔的主要內(nèi)容是經(jīng)過不斷地移動(dòng)來挪去所有的盤子到指定的位置，遞歸原理的應(yīng)用來解釋了我所用的數(shù)據(jù)的知識(shí)。一個(gè)一個(gè)的去組織去協(xié)調(diào)，所有的設(shè)計(jì)不斷地在循環(huán)到達(dá)一定的次數(shù)的到我這次所設(shè)計(jì)結(jié)果。正文1.設(shè)計(jì)目的課程設(shè)計(jì)是?數(shù)據(jù)結(jié)構(gòu)?課程教學(xué)必不可缺的一個(gè)重要環(huán)節(jié)，它可加深學(xué)生對(duì)該課程所學(xué)內(nèi)容的進(jìn)一步的理解與穩(wěn)固，是將計(jì)算機(jī)課程與實(shí)際問題相聯(lián)接的關(guān)鍵步驟。通過課程設(shè)計(jì)，能夠提高學(xué)生分析問題、解決問題，從而運(yùn)用所學(xué)知識(shí)解決實(shí)際問題的能力，因而必須給予足夠的重視。2.設(shè)計(jì)要求1．明確課設(shè)任務(wù)，復(fù)習(xí)與查閱有關(guān)資料。2．按要求完成課設(shè)內(nèi)容，課設(shè)報(bào)告要求文字和圖工整、思路清楚、正確。3．一至四名同學(xué)分為一組，完成一個(gè)應(yīng)用問題的程序的編寫工作。4．應(yīng)用程序應(yīng)具有一定的可用性：〔1〕凡等候用戶輸入時(shí)，給出足夠的提示信息，如“PleaseSelect〔1—3〕：〞提示用戶選擇?！?〕格式明顯易懂，配上適當(dāng)?shù)念伾⒙曇舻容o助效果，能方便地改正輸入時(shí)的錯(cuò)誤，使用戶感到方便、好用。〔3〕有聯(lián)機(jī)求助功能。用戶能直接從系統(tǒng)得到必要的提示，不查手冊(cè)也能解決一些疑難。5．程序具有一定的健壯性，不會(huì)因?yàn)橛脩舻妮斎脲e(cuò)誤引起程序運(yùn)行錯(cuò)誤而中斷執(zhí)行：〔1〕對(duì)輸入值的類型、大小范圍、字符串的長度等，進(jìn)行正確性檢查，對(duì)不合法的輸入值給出出錯(cuò)信息，指出錯(cuò)誤類型，等待重新輸入。〔2〕當(dāng)可能的答復(fù)有多種時(shí)，應(yīng)允許輸入任何一種答復(fù)?！?〕對(duì)刪除數(shù)據(jù)應(yīng)給出警告。3.需求分析3.1漢諾塔的由來：漢諾塔是源自印度神話里的玩具。如下列圖：在印度，有這么一個(gè)古老的傳說：在世界中心貝拿勒斯〔在印度北部〕的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時(shí)候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不管白天黑夜，總有一個(gè)僧侶在按照下面的法那么移動(dòng)這些金片：一次只移動(dòng)一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時(shí)，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。上帝創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上安大小順序摞著64片黃金圓盤。上帝命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤。有預(yù)言說，這件事完成時(shí)宇宙會(huì)在一瞬間閃電式消滅。也有人相信婆羅門至今還在一刻不停地搬動(dòng)著圓盤。3.2漢諾塔與宇宙壽命：如果移動(dòng)一個(gè)圓盤需要1秒鐘的話，等到64個(gè)圓盤全部重新落在一起，宇宙被消滅是什么時(shí)候呢？讓我們來考慮一下64個(gè)圓盤重新摞好需要移動(dòng)多少次吧。1個(gè)的時(shí)候當(dāng)然是1次，2個(gè)的時(shí)候是3次，3個(gè)的時(shí)候就用了7次這實(shí)在是太累了因此讓我們邏輯性的思考一下吧。4個(gè)的時(shí)候能夠移動(dòng)最大的4盤時(shí)如下圖。到此為止用了7次。接下來如下列圖時(shí)用1次，在上面再放上3個(gè)圓盤時(shí)還要用7次〔把3個(gè)圓盤重新放在一起需要的次數(shù)〕。因此，4個(gè)的時(shí)候是“3個(gè)圓盤重新摞在一起的次數(shù)〞+1次+“3個(gè)圓盤重新摞在一起需要的次數(shù)〞=2x“3個(gè)圓盤重新摞在一起的次數(shù)〞+1次=15次。那么，n個(gè)的時(shí)候是2x“〔n-1〕個(gè)圓盤重新摞在一起的次數(shù)〞+1次。由于1個(gè)的時(shí)候是1次，結(jié)果n個(gè)的時(shí)候?yàn)椤?的n次方減1〕次。1個(gè)圓盤的時(shí)候2的1次方減12個(gè)圓盤的時(shí)候2的2次方減13個(gè)圓盤的時(shí)候2的3次方減14個(gè)圓盤的時(shí)候2的4次方減15個(gè)圓盤的時(shí)候2的5次方減1n個(gè)圓盤的時(shí)候2的n次方減1秒，平均每年31556952秒，計(jì)算一下，也就是說，n=64的時(shí)候是〔2的64次方減1〕次。因此，如果移動(dòng)一個(gè)圓盤需要1秒的話，宇宙的壽命=2的64次方減1〔秒〕用一年=60秒x60分x24小時(shí)x365天來算的話，大約有5800億年吧。據(jù)說，現(xiàn)在的宇宙年齡大約是150億年，還差得遠(yuǎn)呢。言而總之，漢諾塔問題在數(shù)學(xué)界有很高的研究價(jià)值，而且至今還在被一些數(shù)學(xué)家們所研究也是我們所喜歡玩的一種益智游戲，它可以幫助開發(fā)智力，激發(fā)我們的思維。對(duì)漢諾塔還可以有進(jìn)一步的研究。4.問題分析：對(duì)于這樣一個(gè)問題，任何人都不可能直接寫出移動(dòng)盤子的每一步，但我們可以利用下面的方法來解決：設(shè)移動(dòng)盤子數(shù)為n，為了將這n個(gè)盤子從A桿移動(dòng)到C桿，可以做以下三步：〔1〕以C盤為中介，從A桿將1至n-1號(hào)盤移至B桿；〔2〕將A桿中剩下的第n號(hào)盤移至C桿；〔3〕以A桿為中介，從B桿將1至n-1號(hào)盤移至C桿；這樣，問題解決了，但實(shí)際操作中，只有第二步可直接完成，而第一、三步又成為移動(dòng)的新問題。以上操作的實(shí)質(zhì)是把移動(dòng)n個(gè)盤子的問題轉(zhuǎn)化為移動(dòng)n-1個(gè)盤。那一、三步如何解決？事實(shí)上，上述方法：設(shè)盤子數(shù)為n，n可為任意數(shù)，該法同樣適用于移動(dòng)n-1個(gè)盤。因此，依據(jù)上法，可解決n-1個(gè)盤子從A桿移到B桿〔第一步〕或從B桿移到C桿〔第三步〕問題?，F(xiàn)在，問題由移動(dòng)n個(gè)盤子的操作轉(zhuǎn)化為移動(dòng)n-2個(gè)盤子的操作。依據(jù)該原理，層層遞推，即可將原問題轉(zhuǎn)化為解決移動(dòng)n-2、n-3……3、2直到移動(dòng)1個(gè)盤的操作，而移動(dòng)一個(gè)盤的操作是可以直接完成的。至此，我們的任務(wù)算作是真正完成了。而這種由繁化簡，用簡單的問題和的操作運(yùn)算來解決復(fù)雜問題的方法，就是遞歸法。在計(jì)算機(jī)設(shè)計(jì)語言中，用遞歸法編寫的程序就是遞歸程序。5.概要設(shè)計(jì)5.1設(shè)計(jì)思想如果盤子為1，那么將這個(gè)盤子從塔座A移動(dòng)到塔座C；

如果不為1，那么采用遞歸思想。將塔座A的前n-1個(gè)盤子借助C盤〔即目的盤〕移到塔座B，移后，此時(shí)C為空座，那我們就可以將塔座A的第n個(gè)盤子移到塔座C了。接下來就將塔座B的n-1個(gè)盤子借助A移到塔座C，從而完成盤子的移動(dòng)。5.2實(shí)現(xiàn)方法通過數(shù)學(xué)函數(shù)的遞歸方法調(diào)用來實(shí)現(xiàn)。5.3主要模塊Main函數(shù)實(shí)現(xiàn)函數(shù)的調(diào)用，move函數(shù)實(shí)現(xiàn)輸出，hanoi函數(shù)調(diào)用move函數(shù)實(shí)現(xiàn)移動(dòng)和最終輸出。5.4模塊關(guān)系程序從Main函數(shù)開始，到main函數(shù)結(jié)束。Main函數(shù)通過調(diào)用hanoi函數(shù)來實(shí)現(xiàn)盤子的移動(dòng)，然后由move函數(shù)輸出在屏幕上。6.詳細(xì)設(shè)計(jì)6.1功能設(shè)計(jì)如果n=1，那么將圓盤從A直接移動(dòng)到C。如果n=2，那么：

(1)將A上的n-1〔等于1〕個(gè)圓盤移到B上；

(2)再將A上的一個(gè)圓盤移到C上；

(3)最后將B上的n-1〔等于1〕個(gè)圓盤移到C上。

如果n=3，那么：

A)將A上的n-1〔等于2，令其為n`〕個(gè)圓盤移到B〔借助于C〕，步驟如下：

(1)將A上的n`-1〔等于1〕個(gè)圓盤移到C上。

(2)將A上的一個(gè)圓盤移到B。

(3)將C上的n`-1〔等于1〕個(gè)圓盤移到B。

B)將A上的一個(gè)圓盤移到C。

C)將B上的n-1〔等于2，令其為n`〕個(gè)圓盤移到C〔借助A〕，步驟如下：

(1)將B上的n`-1〔等于1〕個(gè)圓盤移到A。

(2)將B上的一個(gè)盤子移到C。

(3)將A上的n`-1〔等于1〕個(gè)圓盤移到C。到此，完成了三個(gè)圓盤的移動(dòng)過程。

從上面分析可以看出，當(dāng)n大于等于2時(shí)，移動(dòng)的過程可分解為三個(gè)步驟：第一步把A上的n-1個(gè)圓盤移到B上；第二步把A上的一個(gè)圓盤移到C上；第三步把B上的n-1個(gè)圓盤移到C上；其中第一步和第三步是類同的。當(dāng)n=3時(shí)，第一步和第三步又分解為類同的三步，即把n`-1個(gè)圓盤從一個(gè)針移到另一個(gè)針上，這里的n`=n-1。6.2算法分析本程序的主要算法是利用函數(shù)的遞歸調(diào)用算法。首先，想方法將A座上的前n-1個(gè)盤借助C座移動(dòng)到B座上，然后將A組上的第n個(gè)盤移動(dòng)到C座上。然后再將B座上的n-1個(gè)盤借助A座移動(dòng)到C座上，此次移動(dòng)也和第一次移動(dòng)一樣，重復(fù)遞歸，直到最后一個(gè)盤為止。6.3編寫程序如下：#include<stdio.h>voidmain(){voidhanoi(intn,charone,chartwo,charthree);/*對(duì)hanoi函數(shù)進(jìn)行生聲明*/intm;printf("Pleaseinputthenumberofdiskes:\n");scanf("%d",&m);printf("Thesteptomoving%ddiskes:\n",m);hanoi(m,'A','B','C');getch();}voidhanoi(intn,charone,chartwo,charthree)/*定義hanoi函數(shù)*//*將n個(gè)盤從one座借助two座移到three座*/{voidmove(charx,chary);/*對(duì)move函數(shù)的聲明*/if(n==1)move(one,three);else{hanoi(n-1,one,three,two);move(one,three);hanoi(n-1,two,one,three);}}voidmove(charx,chary)/*定義move函數(shù)*/{printf("%c-->%c\n",x,y);getch();return0;}6.4程序執(zhí)行過程分析：如圖分析7.調(diào)試分析：代碼敲完后，先進(jìn)行調(diào)試分析，找出程序中是否有錯(cuò)。結(jié)果顯示當(dāng)前程序出錯(cuò)，需要返回檢查。認(rèn)真分析，可以看到，main函數(shù)在調(diào)用hanoi函數(shù)之前沒有對(duì)hanoi函數(shù)進(jìn)行聲明，所以編譯顯示出錯(cuò)。接下來就是修改，對(duì)hanoi函數(shù)先進(jìn)行聲明：加上這行聲明后再進(jìn)行調(diào)試程序敲完了，發(fā)現(xiàn)運(yùn)行后速度很快，還沒看清結(jié)果就結(jié)束了。因此，要在main函數(shù)最后加一個(gè)getch〔〕函數(shù)，此函數(shù)的功能是停留運(yùn)行時(shí)間，按任意鍵繼續(xù)，使用戶能夠看到運(yùn)行結(jié)果。因?yàn)镃PU的運(yùn)算速度太快了，如果沒有這個(gè)函數(shù)，那么會(huì)在運(yùn)行的時(shí)候還沒能看到結(jié)果就退出程序了。加上getch函數(shù)之后，好了，編譯成功了，現(xiàn)在就可以測(cè)試一下結(jié)果是否滿足要求了。可以看到，結(jié)果顯示在屏幕上是正確的，設(shè)計(jì)完成。8.小結(jié)通過這次課程設(shè)計(jì)，增加了我學(xué)習(xí)軟件技術(shù)的興趣，雖然還不明確軟件技術(shù)包含的具體內(nèi)容，但從C語言這門課程開始，到數(shù)據(jù)結(jié)構(gòu)，研究算法的特性，已發(fā)現(xiàn)程序設(shè)計(jì)的樂趣，在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的過程中也學(xué)到了許多計(jì)算機(jī)應(yīng)用根底知識(shí)，對(duì)計(jì)算機(jī)的機(jī)體也有了一個(gè)大體的了解。這次課程設(shè)計(jì)是通過我們一個(gè)小組的努力所實(shí)現(xiàn)的要求。在實(shí)際操作過程中犯的一些錯(cuò)誤還會(huì)有意外的收獲，感覺很有意思。在具體操作中對(duì)這學(xué)期所學(xué)的數(shù)據(jù)結(jié)構(gòu)的理論知識(shí)得到穩(wěn)固，到達(dá)設(shè)計(jì)的根本目的，也發(fā)現(xiàn)自己的缺乏之