河內(nèi)之塔解決方法

《河內(nèi)之塔解決方法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、河內(nèi)之塔班級：信管一班姓名：王苗兵學(xué)號：2011193310291設(shè)計題目河內(nèi)之塔2問題描述說明河內(nèi)之塔(TowersofHanoi)是法國人(Lucas)于1883年從泰國帶至法國的，河內(nèi)為越戰(zhàn)時北越的首都，即現(xiàn)在的胡志明市；1883年法國數(shù)學(xué)家曾提及這個故事，據(jù)說創(chuàng)世有一座教塔，是由三支鉆石棒所支撐，開始時神在第一根棒上放置64個由上至下依由小至大排列的金盤（Disc），并命令僧侶將所有的金盤從第一根石棒移至第三根石棒，且搬運過程中遵守大盤子在小盤子之下的原則，若每日僅僅搬一個盤子，則當(dāng)盤子全數(shù)搬運完畢之時，此塔將毀損，而

2、也就是世界末日來臨之時。3設(shè)計解法如果柱子標(biāo)為ABC，要由A搬至C，在只有一個盤子時，就將它直接搬至C，當(dāng)有兩個盤子，就將B當(dāng)作輔助柱。如果盤數(shù)超過2個，將第三個以下的盤子遮起來，就很簡單了，每次處理兩個盤子，也就是：A->B、A->C、B->C這三個步驟，而被遮住的部份，其實就是進(jìn)入程式的遞回處理。事實上，若有n個盤子，則移動完畢所需之次數(shù)為2^n-1，所以當(dāng)盤數(shù)為64時，則所需次數(shù)為：264-1=18446744073709551615為5.05390248594782e+16年，也就是約五千個世紀(jì)，如果對這數(shù)字沒什幺概念

3、，就假設(shè)每秒鐘搬一個盤子好了，也要約5850億年左右。程序代碼如下：程序采用窮舉法，對輸入的數(shù)值進(jìn)行分析，需要2^n–1次搬運。if來判斷，算法如下。void?Hanoi(int?n,char?A,char?B,char?C)??{?????if(n?==?1)????{???printf("Move?sheet?%d?from?%c?to?%c?",n,A,C);??}??else????{?????????Hanoi(n-1,A,C,B);??????????printf("Move?sheet?%d?from?%c?

4、to?%c?",n,A,B);??Hanoi(n-1,B,A,C);??????}??}??運行結(jié)果如下：在鍵盤上輸入數(shù)字3還可以繼續(xù)輸入數(shù)值，數(shù)值越大，所需搬運的次數(shù)也越大。4調(diào)試報告4.1測試用例首先，測試程序能不能運算出正確的結(jié)果，輸入數(shù)據(jù)3出現(xiàn)了7組符合要求的解。接著輸入數(shù)據(jù)0提示輸入錯誤，重新輸入4能得到正確運行結(jié)果。出現(xiàn)了7組符合要求的解。從而可知輸入的數(shù)據(jù)要為整數(shù)，4．2調(diào)試運行結(jié)果程序第一次編譯時，有19個錯誤，都是語法錯誤，修改后，能通過編譯。第一次運行，并不能輸出正確結(jié)果，主要原因有兩個：

5、一個是輸入的數(shù)據(jù)類型不對；另一個是輸入的數(shù)值不對。其他的錯誤有除數(shù)不能為零，括號的位置不對。經(jīng)過修改，調(diào)試后，能運算出正確的結(jié)果。在鍵盤上輸入數(shù)據(jù)3，程序運行成功，運行結(jié)果如上圖設(shè)計程序中的結(jié)果所示并且仍可以繼續(xù)輸入數(shù)據(jù)，出現(xiàn)運行結(jié)果，不同的盤子數(shù)，所搬運的次數(shù)不同，數(shù)值越大，搬運次數(shù)越多。5結(jié)束語通過本次的課程學(xué)習(xí)與設(shè)計，讓我對java程序的數(shù)據(jù)結(jié)構(gòu)和程序設(shè)計算法的思路有了更深刻有更全面更進(jìn)一步的認(rèn)識，拓寬了我對于算法設(shè)計的思維與解決能力。根據(jù)不同的需求，采用不同的數(shù)據(jù)存儲方式，不一定要用棧，二叉樹等高級類型，有時用基本的一

6、維數(shù)組，只要運用得當(dāng)，也能達(dá)到相同的效果，甚至更佳，就如這次的課程設(shè)計題目----河內(nèi)之塔，通過用簡單的if判斷，舍棄多余的循環(huán)，提高了程序的運行效率。在編寫這個程序的過程中，我溫習(xí)了之前學(xué)的基本語法，更加深刻的認(rèn)識到循環(huán)是大部分程序的基本要素。結(jié)合了這學(xué)期學(xué)的數(shù)據(jù)結(jié)構(gòu)，分析算法的時間復(fù)雜度，不斷改進(jìn)算法，更加鞏固了之前學(xué)的知識，比以前更能靈活運用。本次寫的程序還有很大的發(fā)展空間，可以通過循環(huán)，重復(fù)輸入數(shù)據(jù)，多次計算盤子搬運次數(shù)。還可以通過設(shè)計，讓程序能計算出任意結(jié)果，。在輸出方面，為提高運行效率，可以設(shè)計只輸出一組解。在輸入

7、方面，放寬數(shù)據(jù)類型。隨著數(shù)量增加，循環(huán)增加，為提高運行效率，可以考慮更改數(shù)據(jù)類型。通過本次的java課程算法設(shè)計，我收獲了很多，鞏固舊知識的同時，學(xué)習(xí)了新的知識。更重要的是，它使我對java程序設(shè)計算法產(chǎn)生了濃厚的興趣，面對一道編程題時有了新的思維，對編寫程序更有信心。