hanoi函數(shù)解析

1、Comment[A1]:這里暫時把n個盤看作一個整體。Comment[A2]:這里暫時把（n1）個盤看作一個整體。1C語言中的經(jīng)典函數(shù)遞歸問題語言中的經(jīng)典函數(shù)遞歸問題HanoiHanoi程序的解析程序的解析在譚浩強(qiáng)編寫的《C程序設(shè)計（第三版）》中有這樣一個經(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問題的解答程序，“Hanoi問題是一個古典的數(shù)學(xué)問題，是一個用遞歸方法解題的典型例子。問題是這樣的：古代有一個梵塔，塔內(nèi)有3個座A、B、C，開始時A座上有64個盤子，盤子大小不等，大的在下，小的在上（如圖1.1所示）。有一個老和尚想把這64個盤子從A座移到C座，但每次只允許移動一個盤子，且在移動過程中在3個座上都始終保持大盤在下，小盤在上。

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

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

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

7、第3層之間的運(yùn)作關(guān)系hanoi(2BAC)hanoi函數(shù)首先運(yùn)行“hanoi(2ACB)”語句(記為31，它的下面兩條語句記為32、33)，把31展開如下：elsehanoi(1ABC)hanoi(2ACB)move(AB)hanoi(1CA，B)；接著hanoi函數(shù)又繼續(xù)運(yùn)行“hanoi(1ABC)”語句（記為21，它的下面兩條語句記為22、23），把21展開：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時，要注意變量（nonetwothree）中值的不斷更新及其更新方法，以21為例：hanoi(n1onethreetwo)1ABCvoidhanoi(intnonetwothree)這里21語句中變量（或表達(dá)式）的具體值已經(jīng)存在，分別為1、A、B、C，在上文中我直接以常量的形式寫出，是為了更直觀地表達(dá)