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

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

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

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

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

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

如果n=3，那么：

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

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

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

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

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

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

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

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

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

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