本題算法分析如下，設A上有n個盤子。

　　如果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上，見圖5.5(b)。

　　(2)將A上的一個圓盤移到B,見圖5.5(c)

　　(3)將C上的n`-1(等于1)個圓盤移到B,見圖5.5(d)

　　B. 將A上的一個圓盤移到C，見圖5.5(e)

　　C. 將B上的n-1(等于2，令其為n`)個圓盤移到C(借助A)，

　　步驟如下：

　　(1)將B上的n`-1(等于1)個圓盤移到A,見圖5.5(f)

　　(2)將B上的一個盤子移到C,見圖5.5(g)

　　(3)將A上的n`-1(等于1)個圓盤移到C，見圖5.5(h)。

　　到此，完成了三個圓盤的移動過程。

　　從上面分析可以看出，當n大于等于2時， 移動的過程可分解為三個步驟：

　　第一步 把A上的n-1個圓盤移到B上;

　　第二步 把A上的一個圓盤移到C上;

　　第三步 把B上的n-1個圓盤移到C上;其中第一步和第三步是類同的。

　　當n=3時，第一步和第三步又分解為類同的三步，即把n`-1個圓盤從一個針移到另一個針上，這里的n`=n-1。顯然這是一個遞歸過

　　程，據此算法可編程如下：

　　move(int n,int x,int y,int z)

　　{

　　if(n==1)

　　printf("%c-->%c\n",x,z);

　　else

　　{

　　move(n-1,x,z,y);

　　printf("%c-->%c\n",x,z);

　　move(n-1,y,x,z);

　　}

　　}

　　main()

　　{

　　int h;

　　printf("\ninput number:\n");

　　scanf("%d",&h);

　　printf("the step to moving %2d diskes:\n",h);

　　move(h,'a','b','c');

　　}

　　move(int n,int x,int y,int z)

　　{

　　if(n==1)

　　printf("%-->%c\n",x,z);

　　else

　　{

　　move(n-1,x,z,y);

　　printf("%c-->%c\n",x,z);

　　move(n-1,y,x,z);

　　}

　　}

　　main()

　　{ ……

　　move(h,'a','b','c');

　　}

　　從程序中可以看出，move函數是一個遞歸函數，它有四個形參n，x，y，zn表示圓盤數，x，y，z分別表示三根針。move 函數的功能是把x上的n個圓盤移動到z 上。當n==1時，直接把x上的圓盤移至z上，輸出x→z。如n!=1則分為三步：遞歸調用move函數，把n-1個圓盤從x移到y;輸出x→z;遞歸調用move函數，把n-1個圓盤從y移到z。在遞歸調用過程中n=n-1，故n的值逐次遞減，最后n=1時，終止遞歸，逐層返回。當n=4 時程序運行的結果為：

　　input number:

　　4

　　the step to moving 4 diskes:

　　a→b

　　a→c

　　b→c

　　a→b

　　c→a

　　c→b

　　a→b

　　a→c

　　b→c

　　b→a

　　c→a

　　b→c

　　a→b

　　a→c

　　b→c

　　相關推薦：

　　2012年軟考系統分析師考試60天完美復習計劃

　　2012年軟件水平考試網絡工程師章節筆記講義匯總

　　2012年上半年軟件水平考試成績查詢匯總