hanoi函數(shù)解析

1、Comment[A1]:這里暫時(shí)把n個(gè)盤(pán)看作一個(gè)整體。Comment[A2]:這里暫時(shí)把（n1）個(gè)盤(pán)看作一個(gè)整體。1C語(yǔ)言中的經(jīng)典函數(shù)遞歸問(wèn)題語(yǔ)言中的經(jīng)典函數(shù)遞歸問(wèn)題HanoiHanoi程序的解析程序的解析在譚浩強(qiáng)編寫(xiě)的《C程序設(shè)計(jì)（第三版）》中有這樣一個(gè)經(jīng)典遞歸（紅框中）程序：(程序運(yùn)行環(huán)境：VisualStdio2008)#include“stdafx.h“#includevoidmain()voidhanoi(intnonetwo

2、three)intmprintf(“inputthenumberofdiskes:“)scanf(“%d“printf(“Thesteptomove%ddiskes:n“m)hanoi(mABC)get()get()voidhanoi(intnonetwothree)voidmove(xy)if(n==1)move(onethree)elsehanoi(n1onethreetwo)move(onethree)hanoi(n1twoone

3、three)voidmove(xy)printf(“%c%cn“xy)很顯然，這是著名的Hanoi問(wèn)題的解答程序，“Hanoi問(wèn)題是一個(gè)古典的數(shù)學(xué)問(wèn)題，是一個(gè)用遞歸方法解題的典型例子。問(wèn)題是這樣的：古代有一個(gè)梵塔，塔內(nèi)有3個(gè)座A、B、C，開(kāi)始時(shí)A座上有64個(gè)盤(pán)子，盤(pán)子大小不等，大的在下，小的在上（如圖1.1所示）。有一個(gè)老和尚想把這64個(gè)盤(pán)子從A座移到C座，但每次只允許移動(dòng)一個(gè)盤(pán)子，且在移動(dòng)過(guò)程中在3個(gè)座上都始終保持大盤(pán)在下，小盤(pán)在上。

4、在移動(dòng)過(guò)程中可以利用B座。”ABC圖1.11.1一、首先，我們用數(shù)學(xué)知識(shí)來(lái)分析：1、逆向分析：要把n個(gè)盤(pán)從A移到C，先要把(n1)個(gè)盤(pán)從A移到B，再把第n個(gè)盤(pán)從A移到C，最后把（n1）個(gè)盤(pán)從B移到C；要把（n1）個(gè)盤(pán)從A移到B，又必須先把（n2）個(gè)盤(pán)從A移到C，再把第（n1）個(gè)盤(pán)從A移到B，最后把（n2）個(gè)盤(pán)從C移到B；…；如此循環(huán)，直到遇到第一個(gè)盤(pán)，這是終止遞歸的標(biāo)志，又是層層解開(kāi)遞歸的鑰匙。Comment[A8]:這里對(duì)A、B、C重

5、新分配了在下一個(gè)hanoi函數(shù)中的位置，目的是實(shí)現(xiàn)從A到B的調(diào)運(yùn)。下同。Comment[A9]:注意：運(yùn)行到這一步時(shí)仍需再一次調(diào)用hanoi函數(shù)。Comment[A10]:記為11，而實(shí)際上，它一步就可以完成了！Comment[A11]:方法同21語(yǔ)句，上文已經(jīng)分析過(guò)。Comment[A12]:方法同31語(yǔ)句。3略。由以上同樣可以看出移動(dòng)的總次數(shù)為C（n）=。12?n二、然后，我們?cè)龠\(yùn)用C語(yǔ)言的知識(shí)來(lái)分析：要用C語(yǔ)言中的遞歸函數(shù)來(lái)分析，

6、首先必須明白遞歸函數(shù)的運(yùn)作原理，以上文的遞歸函數(shù)的調(diào)用為例：第一次是main函數(shù)調(diào)用：hanoi(mABC)此時(shí)，在運(yùn)行hanoi函數(shù)時(shí)，n值全賦為m的值one值全賦為‘A’two值全賦為‘B’，three值全賦為‘C’，亦即，當(dāng)函數(shù)頭中的變量一旦取到值時(shí)，函數(shù)內(nèi)所有的變量取值隨即確定下來(lái)，而不是函數(shù)運(yùn)行到那一條語(yǔ)句才把該句中的變量值確定下來(lái)。所以，第一次使用Hanoi是時(shí)，有elsehanoi(2ACB)move(AC)這里是前兩層與

7、第3層之間的運(yùn)作關(guān)系hanoi(2BAC)hanoi函數(shù)首先運(yùn)行“hanoi(2ACB)”語(yǔ)句(記為31，它的下面兩條語(yǔ)句記為32、33)，把31展開(kāi)如下：elsehanoi(1ABC)hanoi(2ACB)move(AB)hanoi(1CA，B)；接著hanoi函數(shù)又繼續(xù)運(yùn)行“hanoi(1ABC)”語(yǔ)句（記為21，它的下面兩條語(yǔ)句記為22、23），把21展開(kāi)：if(n==1)hanoi(1ABC)move(AC)然后反推到執(zhí)行22：

8、move(A，B)再到23：hanoi(1CA，B)再返回執(zhí)行：32：move（A，C）；再到33：hanoi(2BAC)當(dāng)調(diào)用hanoi時(shí)，要注意變量（nonetwothree）中值的不斷更新及其更新方法，以21為例：hanoi(n1onethreetwo)1ABCvoidhanoi(intnonetwothree)這里21語(yǔ)句中變量（或表達(dá)式）的具體值已經(jīng)存在，分別為1、A、B、C，在上文中我直接以常量的形式寫(xiě)出，是為了更直觀地表達(dá)