学习《算法分析》时的拙作，不要见笑！
递归算法的经典例子，是求解hanoi塔问题（请参照常见的算法课本）。在这里介绍一种更为通用的算法去解决在hanoi塔游戏过程中的自动移动问题。也就是说，常见的hanoi塔算法仅仅是本算法的特殊情况。
假设现在有x，y，z三条柱子，上面共有n个盘子。但是盘子在柱子上是随机分布的，当然，下面的盘子一定比上面的大，只能在柱子上取出最上面的盘子放到x,y,z之一柱子上且比柱子最上面的盘子小，规定盘子的标号分别从1到n，且盘子越大，盘子号越大。现在我们的问题是如何将所有的盘子依次排放到z柱子上去。
首先证明满足上面条件的所有情况均能移动到一个柱子上去。
不妨设z为目标柱子（x,y,z均为并列关系），分类讨论：
（一） 当n=1时，直接将第n个移到z柱子上。
（二） 当n大于1时
（1） 找出n号盘子的位置。
（2） 当n号盘子在z柱子上时，该问题变成总盘子为n-1的情况。
（3） 在x柱子上时，只许将n-1个盘子收集到y柱子上
然后将n号盘子移到z上即可变成n-1问题。
（4） 盘子在y柱子上时，只许将n-1个盘子收集到x柱子上
然后将n号盘子移到z上即可变成n-1问题。
（5） 执行（1）到（4）直到n=1。
所以，当盘子是任意分布时（每一柱子上盘子均为上小下大），均可以将盘子收集到z柱子上。又因为x,y,z均为并列关系，可将所有盘子移动到任意柱子上。
以上证明过程也是算法描述过程。
（1） 为了方便更多数人理解，特用qbasic语言编写了一款hanoi塔游戏。（在qbasic v1.1上调试通过）。
（2） 为了减少代码长度，不支持鼠标，游戏在文本方式下运行。
DECLARE SUB initiate21 (n!)
DECLARE SUB printmode (n!)
DECLARE FUNCTION directionkey! ()
DECLARE SUB initiate22 (n!)
DECLARE SUB insert (a%(), num!)
DECLARE FUNCTION gamemode! ()
DECLARE SUB finish (auto1!)
DECLARE SUB check (chn!)
DECLARE SUB initiate1 ()
DECLARE SUB zhinput (n!)
DECLARE SUB hanoi (n!, x1%(), x2%(), x3%())
DECLARE FUNCTION search% (n!, x1%(), x2%(), x3%())
DECLARE SUB move (x1%(), n!, x3%(), delay!)
DECLARE SUB main (n!)
DECLARE FUNCTION nextkey$ ()
DECLARE SUB windows ()
DIM SHARED movenum(0)
DIM SHARED x%(9), y%(9), z%(9)
CLS
CALL zhinput(n)
CALL initiate1
choice = gamemode
DO
IF choice = 1 THEN CALL initiate21(n) ELSE initiate22 (n)
CALL windows
CALL main(n)
n = n + 1
LOOP
END
CONST wherex = 11
CONST wherey = 31
CONST wherez = 51
DATA " Fature game "," Normal game "
SUB check (chn)
ch = 0
chn = 1
FOR i = 1 TO x%(0) + y%(0) + z%(0)
IF z%(i) <> i THEN
ch = 1
EXIT FOR
END IF
NEXT i
IF ch = 0 THEN chn = 0
END SUB
FUNCTION directionkey
DIM c AS STRING * 2
DO
c$ = INKEY$
IF ASC(c$) = 13 THEN
directionkey = 0
EXIT FUNCTION
END IF
IF c$ <> "" AND ASC(MID$(c$, 1, 1)) = 0 THEN
SELECT CASE ASC(MID$(c$, 2, 1))
CASE 72
directionkey = 1
CASE 75
directionkey = 2
CASE 77
directionkey = 3
CASE 80
directionkey = 4
END SELECT
EXIT FUNCTION
END IF
LOOP
END FUNCTION
SUB finish (auto1)
SELECT CASE z%(0)
CASE 1 TO 2
c$ = "oh,finish!"
CASE 3 TO 4
c$ = "OK! hurry on!"
CASE 5 TO 7
c$ = "pass the level! very good! continue!"
CASE 8
c$ = "perfect! only one level left!"
CASE 9
c$ = "congratulations! you have finish it!"
END SELECT
COLOR 1, 2
IF auto1 = 0 THEN
LOCATE 11, 40 - LEN(c$) / 2
PRINT c$
END IF
c$ = "PRESS ANY KEY TO CONTINUE"
LOCATE 12, 40 - LEN(c$) / 2
PRINT c$
SLEEP
IF z%(0) = 9 THEN END
END SUB
FUNCTION gamemode
gamemodenum = 1
CALL printmode(1)
DO
SELECT CASE directionkey
CASE 0
EXIT DO
CASE 1
gamemodenum = gamemodenum - 1
IF gamemodenum < 1 THEN gamemodenum = 2
CALL printmode(gamemodenum)
CASE 4
gamemodenum = gamemodenum + 1
IF gamemodenum > 2 THEN gamemodenum = 1
CALL printmode(gamemodenum)
END SELECT
LOOP
gamemode = gamemodenum
END FUNCTION
SUB hanoi (n, x1%(), x2%(), x3%())
subx = search%(n, x1%(), x2%(), x3%())
IF n = 1 THEN
SELECT CASE subx
CASE 1
movenum(0) = movenum(0) + 1
CALL move(x1%(), n, x3%(), 1)
CASE 2
movenum(0) = movenum(0) + 1
CALL move(x2%(), n, x3%(), 1)
END SELECT
ELSE
SELECT CASE subx
CASE 1
CALL hanoi(n - 1, x1%(), x3%(), x2%())
movenum(0) = movenum(0) + 1
CALL move(x1%(), n, x3%(), 1)
CALL hanoi(n - 1, x1%(), x2%(), x3%())
CASE 2
CALL hanoi(n - 1, x2%(), x3%(), x1%())
movenum(0) = movenum(0) + 1
CALL move(x2%(), n, x3%(), 1)
CALL hanoi(n - 1, x2%(), x1%(), x3%())
CASE 3
CALL hanoi(n - 1, x1%(), x2%(), x3%())
END SELECT
END IF
END SUB
SUB initiate1
COLOR 1, 2 ' the game color
CLS
LOCATE 1, 37: PRINT "Hanoi"
LOCATE 3, 3: PRINT "press x,y,z to move"
LOCATE 4, 3: PRINT "press Esc to exit"
LOCATE 5, 3: PRINT "press a to auto run"
LOCATE 21, wherex: PRINT "X"
LOCATE 21, wherey: PRINT "Y"
LOCATE 21, wherez: PRINT "Z"
END SUB
SUB initiate21 (n)
x%(0) = n: y%(0) = 0: z%(0) = 0
FOR i = 1 TO 9
x%(i) = 99: y%(i) = 99: z%(i) = 99
NEXT i
FOR i = 1 TO n
x%(i) = i
NEXT i
END SUB
SUB initiate22 (n)
c$ = TIME$
seed = VAL(MID$(c$, 7, 8))
RANDOMIZE (seed)
x%(0) = 0
y%(0) = 0
z%(0) = 0
FOR i = 1 TO 9
x%(i) = 99: y%(i) = 99: z%(i) = 99
NEXT i
FOR i = n TO 1 STEP -1
insertnum = INT(RND(1) * 3 + 1)
SELECT CASE insertnum
CASE 1
CALL insert(x%(), i)
CASE 2
CALL insert(y%(), i)
CASE 3
CALL insert(z%(), i)
END SELECT
NEXT i
END SUB
SUB insert (a%(), num)
FOR i = 1 TO a%(0)
a%(a%(0) + 2 - i) = a%(a%(0) - i + 1)
NEXT i
a%(1) = num
a%(0) = a%(0) + 1
END SUB
SUB main (n)
movenum(0) = 0
DO
subc$ = nextkey$
subc1$ = subc$
LOCATE 12, 62
PRINT subc$; "--> ";
auto = 0
SELECT CASE subc$
CASE "a"
CALL hanoi(n, x%(), y%(), z%())
auto = 1
CASE "x"
subc$ = nextkey$
SELECT CASE subc$
CASE "y"
movenum(0) = movenum(0) + 1
CALL move(x%(), 1, y%(), 0)
CASE "z"
movenum(0) = movenum(0) + 1
CALL move(x%(), 1, z%(), 0)
END SELECT
CASE "y"
subc$ = nextkey$
SELECT CASE subc$
CASE "x"
movenum(0) = movenum(0) + 1
CALL move(y%(), 1, x%(), 0)
CASE "z"
movenum(0) = movenum(0) + 1
CALL move(y%(), 1, z%(), 0)
END SELECT
CASE "z"
subc$ = nextkey$
SELECT CASE subc$
CASE "x"
movenum(0) = movenum(0) + 1
CALL move(z%(), 1, x%(), 0)
CASE "y"
movenum(0) = movenum(0) + 1
CALL move(z%(), 1, y%(), 0)
END SELECT
CASE CHR$(27)
END
END SELECT
LOCATE 12, 62: PRINT subc1$; "-->"; subc$
chn = 1
CALL check(chn)
IF chn = 0 THEN CALL finish(auto): EXIT DO
CALL windows
LOCATE 11, 62
PRINT "move:"; movenum(0)
LOOP
END SUB
SUB move (x1%(), n, x3%(), delay)
IF x1%(1) < x3%(1) THEN
IF delay <> 0 THEN
FOR i = 1 TO 5 'ctr the speed
SOUND 0, 1
NEXT i
END IF
movex = x1%(1)
FOR i = 2 TO x1%(0)
x1%(i - 1) = x1%(i)
NEXT i
x1%(i - 1) = 99
x1%(0) = x1%(0) - 1
FOR i = x3%(0) TO 1 STEP -1
x3%(i + 1) = x3%(i)
NEXT i
x3%(1) = movex
x3%(0) = x3%(0) + 1
CALL windows
LOCATE 11, 62
PRINT "move:"; movenum(0)
ELSE
LOCATE 11, 1: PRINT " ";
LOCATE 11, 1: PRINT "wrong";
END IF
END SUB
FUNCTION nextkey$
DO
nextc$ = INKEY$
IF nextc$ = "a" OR nextc$ = CHR$(27) OR nextc$ = "x" OR nextc$ = "y" OR nextc$ = "z" THEN
nextkey$ = nextc$
EXIT DO
END IF
LOOP
END FUNCTION
SUB printmode (n)
COLOR 15, 1
RESTORE
FOR i = 1 TO 2
READ c$
LOCATE 12 + i, 40 - LEN(c$) / 2
PRINT c$
NEXT i
RESTORE
FOR i = 1 TO n
READ c$
NEXT i
LOCATE 12 + n, 40 - LEN(c$) / 2
COLOR 15, 2
PRINT c$
END SUB
FUNCTION search% (n, x1%(), x2%(), x3%())
FOR i = 1 TO x1%(0)
IF n = x1%(i) THEN search = 1
NEXT i
FOR i = 1 TO x2%(0)
IF n = x2%(i) THEN search = 2
NEXT i
FOR i = 1 TO x3%(0)
IF n = x3%(i) THEN search = 3
NEXT i
END FUNCTION
SUB windows
VIEW PRINT 11 TO 20
COLOR 4, 2
CLS
FOR i = 1 TO x%(0)
FOR j = 0 TO 2 * x%(i)
LOCATE 20 - x%(0) + i, wherex - x%(i) + j
PRINT CHR$(219);
NEXT j
NEXT i
FOR i = 1 TO y%(0)
FOR j = 0 TO 2 * y%(i)
LOCATE 20 - y%(0) + i, wherey - y%(i) + j
PRINT CHR$(219);
NEXT j
NEXT i
FOR i = 1 TO z%(0)
FOR j = 0 TO 2 * z%(i)
LOCATE 20 - z%(0) + i, wherez - z%(i) + j
PRINT CHR$(219);
NEXT j
NEXT i
END SUB
SUB zhinput (n)
COLOR 1, 2
CLS
LOCATE 2, 2
INPUT "input a number (3--9) to start the game:", n
IF n < 3 OR n > 9 THEN CALL zhinput(n)
END SUB
说明：以上是完整的hanoi塔游戏源程序，其中的随机数种子取自系统时间。
最麻烦的是三根柱子，多于三根的就可以转换成三根的问题了不仿设有n根（n>2) 目标是移到第n根上，那么，首先将前三根的盘子移到第三根此时的柱子就变成n-2了重复以上过程即可转化成三根的问题了
