Learning "Algorithm Analysis", don't laugh!
The classic example of the recursive algorithm is to solve the Hanoi tower problem (refer to the common algorithm textbook). Here is a more general algorithm to solve the automatic movement problem in the Hanoi tower game. That is to say, the common Hanoi column algorithm is only a special case of this algorithm.
Suppose there is X, Y, Z three columns, and there is a total of N plates. However, the plate is randomly distributed on the column. Of course, the following tray must be larger than the above, only the top of the upper plate is removed on the column, and the top of the column is smaller than the top of the column. , The markings specifying the tray from 1 to N, and the larger the tray, the greater the disk number. Now our question is how to discharge all the trays to the Z pillar.
First prove that all situations that meet the above conditions can be moved to a column.
It may be possible to set Z as a target column (x, y, and z partial relationship), classified discussion:
(1) When n = 1, the nth is moved directly to the Z pillar.
(2) When N is greater than 1
(1) Find the location of the N-plate.
(2) When the N-plate is on the Z pillar, the problem becomes the case where the total tray is N-1.
(3) When the X pillar, only the N-1 plate is collected on the Y pillar.
Then move the N-plate to Z to be turned to n-1.
(4) When the plate is on the Y pillar, only the N-1 plate is collected on the X pillar.
Then move the N-plate to Z to be turned to n-1.
(5) Perform (1) to (4) until n = 1.
Therefore, when the tray is arbitrarily distributed (all the plates are large in each column), the tray can be collected on the Z pillar. Only because X, Y, Z are both parallel, all trays can be moved to any column.
The above proof is also an algorithm description process.
(1) In order to facilitate more people to understand, a Hanoi tower game is written in QBasic language. (Detection on QBasic V1.1).
(2) In order to reduce the length of the code, the mouse is not supported, and the game runs in text mode.
Declare subinitiate21 (n!)
Declare Sub PrintMode (N!)
Declare function directionKey! ()
Declare subinitiate22 (n!)
Declare Sub INSERT (a% (), NUM!)
Declare function gamemode! ()
Declare Sub Finish (auto1!)
Declare Sub Check (CHN!)
Declare subinitiate1 ()
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 = Gamemodedo
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 $, 1, 1)) = 0 THEN
SELECT CASE ASC (MID $, 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 Left!"
Case 9
C $ = "CONGRATULATIONS! You Have Finish it!"
End SELECT
Color 1, 2
IF auto1 = 0 THEN
Locate 11, 40 - Len ($) / 2
PRINT C $
END IF
C $ = "Press any key to continue"
Locate 12, 40 - Len ($) / 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 $, 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 subsis 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) 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 ($) / 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 Description: The above is a complete Hanoi tower game source program, where the random seed is taken from the system time. The most troublesome is three columns. It can be converted into three problems. It does not imitate to have n roots (n> 2) goals are moved to the nth, then, first move the top three trays to the third The column at this time becomes N-2 and repeated the above process to translate into three problems.
