數(shù)據(jù)結(jié)構(gòu)-n階Hanoi塔問題作業(yè)_孫志佳(017)_計(jì)算機(jī)科學(xué)與技術(shù)2.

1、n階Hanoi塔問題塔問題解題思路匯報(bào)專業(yè):計(jì)算機(jī)科學(xué)與技術(shù)班級(jí):A班學(xué)號(hào):017姓名:孫志佳題目介紹題目介紹1 分析問題復(fù)雜性及舉例說明分析問題復(fù)雜性及舉例說明2程序代碼程序代碼3一、題目介紹： 假設(shè)有三個(gè)命名為XY Z的塔座 ，在塔座X上插有n個(gè)直徑大小不相同，由小到大編號(hào)為1 ，2 ，3 ， ，n的圓盤，要求將X座上的圓盤移至塔座C并按同樣的順序疊排。圓盤移動(dòng)必須遵守下列規(guī)則： 1：每次只能移動(dòng)一個(gè)圓盤 2：圓盤可以插在任意一個(gè)塔座上 3：任何時(shí)刻都不能將一個(gè)較大的圓盤放在一個(gè)較小的圓盤上二、分析問題分析問題復(fù)雜性及舉例說明：及舉例說明：分析：分析：若有n個(gè)盤子，則移動(dòng)完所需之次數(shù)為2n

2、 - 1，所以當(dāng)盤數(shù)為64時(shí)，則所需次數(shù)為： 264 - 1 = 18446744073709551615 為5.05390248594782e+16年，也就是約5000世紀(jì)，如果對(duì)這數(shù)字沒什么概念，就假設(shè)每秒鐘搬一個(gè)盤子好了，也要約5850億年左右。舉例說明：舉例說明：以三階Hanoi塔為例，我們所需要的7個(gè)步驟是：1Z2Y1Y3Z1X2Z1Z則對(duì)于n階Hanoi塔： n = 1時(shí)只需將編號(hào)為1的圓盤從X座移至Z座 n 1時(shí)，我們分三個(gè)階段： 1：將X塔座上的n-1個(gè)圓盤按照規(guī)定移至到Y(jié)塔座 2：將編號(hào)為n的圓盤由X座移至Z座 3：利用X塔座，將Y塔座上的n-1個(gè)圓盤按規(guī)定移至到Z塔座xyz

3、圖例三、程序代碼：#include void hanoi(int i , char X , char Y , char Z);void move(int i , char x , char y);int main()int n ;printf(請(qǐng)輸入n的值：);scanf(%d,&n); hanoi(n , X , Y , Z); return 0 ; void hanoi(int i , char X , char Y , char Z) if(i = 1)move(i ,X, Z);else hanoi(i - 1 , X , Z , Y); /函數(shù)遞歸調(diào)用 move(i , X , Z);hanoi(i - 1 , Y , X , Z); void move(int i , char x , char y) static int c = 1 ; /局部變量i申明為 static