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