hanoi函數解析

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

4、在移動過程中可以利用B座。”ABC圖1.11.1一、首先，我們用數學知識來分析：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)，直到遇到第一個盤，這是終止遞歸的標志，又是層層解開遞歸的鑰匙。Comment[A8]:這里對A、B、C重

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

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

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