汉诺塔问题是源于印度的一个古老传说。汉诺塔问题简短的描述下.假如有start ,tmp , end三个柱子。

  1. 初始条件:最开始是tmp和end为空,而start上面有按从大到小往上摆的盘子(塔状);
  2. 最终目标:实现把所有盘子放到end柱子上,顺序跟之前的start柱子一样.从大到小往上的塔状形;
  3. 限制条件:我们在搬动的时候可以把tmp柱子拿来临时用下,不过在搬动的任何时候不能出现小盘到大盘上面的情况。

先考虑最简单的情况,假如只有一个盘子,就直接从start搬到目的地end。

如果两个盘子则是先把小盘子放tmp,然后大盘子放end,最后再把tmp里的盘子放end。

假如有N个盘子时,我们可以这样想,底下最大的那个我们先不管。

于是可以先想办法把start上的N-1个盘子搬到tmp上,然后把最大的那个搬end上,最后再想办法把tmp上的N-1个搬到end上。

汉诺塔

使用汇编语言实现了汉诺塔算法,以栈的方式处理数据,用递归方式实现的子程序。源代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
assume   cs:code,ds:data
;数据段的定义
;--------------------------------------------------
data  segment
    mess        db 5 dup (0ah,0dh)
                db 14 dup ('              |                       |                       |                ',0ah,0dh)               
                db '   -----------|----------- -----------|----------- -----------|-----------     ',0ah,0dh
                db '          Tower A                 Tower B                 Tower C              ','$';
    bin         dw 6                ;将bin初始化
    one         dw 28;,15       ;三个塔
    two         dw 76;,19
    three   dw 124;,19
data ends
;-----------------------------------------------------
;代码段的定义
code  segment
start:    
    ;清屏
    mov ax,600h
    mov bh,07h
    xor cx,cx
    mov dx,184fh
    int 10h
    ;设置光标位置
    mov ah,2
    mov bh,0
    mov dx,0
    int 10h

    mov ax,data     ;将数据段送到dx
    mov ds,ax
    lea dx, mess    ;输出mess
    mov ah,09h
    int 21h

    mov ax,0b800h
    mov es,ax   
    mov di,160*7+28
    mov al,2
    mov ah,01100000b
    call rect
    mov di,160*9+28
    mov al,3
    mov ah,01010000b
    call rect
    mov di,160*11+28
    mov al,4
    mov ah,00110000b
    call rect
    mov di,160*13+28
    mov al,5
    mov ah,00010000b
    call rect
    mov di,160*15+28
    mov al,6
    mov ah,00100000b
    call rect
    mov di,160*17+28
    mov al,7
    mov ah,01000000b
    call rect     

    push    bin         ;压栈操作
    push    one
    push    two
    push    three
    call    hanoi       ;调用Hanoi

    mov ah,4ch
    int 21h   

;汉诺塔    
hanoi:      
        push    ax
        push    dx
        push    bp
        mov bp,sp
        mov ax,1
        cmp ax,word ptr [bp+14]
        je  equal
        jmp unequal
    equal:    ;若相等执行
        mov ax,word ptr[bp+12]
        mov bx,word ptr [bp+8]
        call moverect
        jmp exit
    unequal:        ;若不相等执行
        mov ax,[bp+14]
        sub ax,1
        push    ax
        push    [bp+12]
        push    [bp+8]
        push    [bp+10]
        call    hanoi

        mov ax,word ptr [bp+12]
        mov bx,word ptr [bp+8]
        call moverect

        mov ax,[bp+14]
        sub ax,1
        push    ax
        push    [bp+10]
        push    [bp+12]
        push    [bp+8]
        call    hanoi
    exit:
        pop bp
        pop dx
        pop ax
        ret 8

;子程序:绘制矩形
;参数:    es:[di]矩行中心位置
;       al矩形长度
;       ah矩形颜色
rect:   ;子程序
        push ax
        push bx
        push cx
        push di

        mov bl,ah
        mov ah,0
        sub di,ax
        sub di,ax
        mov cx,ax
        add cx,ax
        add cx,1
    rect_1:
        mov byte ptr es:[di+1],bl
        mov byte ptr es:[di+160+1],bl
        add di,2
        loop rect_1

    rect_over:
        pop di
        pop cx
        pop bx
        pop ax
        ret

;子程序:移动矩形
;参数 al=A列   
;       ah=A行
;       bl=C列
;       bh=C行
moverect:
        call delay
        push ax
        push bx
        push cx
        push dx

        mov dl,al
        mov dh,0
        mov si,dx
        mov cx,0
    moverect_3:
        mov dl,es:[si+1]
        cmp dl,07h
        jne moverect_2
        cmp cx,19
        je moverect_2
        add si,160
        add cx,1
        jmp     moverect_3
    moverect_2:
        sub si,22   

        mov dl,bl
        mov dh,0
        mov di,dx
        mov cx,0
    moverect_4:
        mov dl,es:[di+1]
        cmp dl,07h
        jne moverect_5
        cmp cx,19
        je moverect_5
        add di,160
        add cx,1
        jmp     moverect_4
    moverect_5:
        sub di,22
        sub di,320  

        mov cx,23       
        moverect_1:
            mov al,es:[si+1]
            mov es:[di+1],al
            mov al,es:[si+160+1]
            mov es:[di+160+1],al
            mov byte ptr es:[si+1],111b
            mov byte ptr es:[si+160+1],111b
            add di,2
            add si,2
        loop moverect_1

        pop dx
        pop cx      
        pop bx
        pop ax
        ret

;子程序:延时
delay:
    push cx
    mov cx,0ffh
    run1:
    push cx
    mov cx,0fffh
    run2:
    loop run2
    pop cx
    loop run1
    pop cx
    ret     

code    ends
;---------------------------------------
end   start