学习《算法分析》时的拙作，不要见笑！
递归算法的经典例子，是求解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
