Difference between revisions of "CSC231 Analysis of the Towers of Hanoi"
(Created page with "--~~~~ ---- =Top Down Approach: Version 1= <br /> <source lang="asm"> ;;; hanoi1.asm ;;; D.T. ;;; Towers of Hanoi, top down... ;;; assumptions: ;;; al = n Number of disk ;...") |
(→Top Down Approach: Version 1) |
||
Line 3: | Line 3: | ||
=Top Down Approach: Version 1= | =Top Down Approach: Version 1= | ||
+ | ==Source== | ||
<br /> | <br /> | ||
<source lang="asm"> | <source lang="asm"> | ||
Line 81: | Line 82: | ||
</source> | </source> | ||
<br /> | <br /> | ||
+ | ==Output== | ||
+ | |||
+ | [231a@beowulf ~/handout]$ nasmld hanoi1 | ||
+ | '''A --> B''' | ||
=Top Down Version 2= | =Top Down Version 2= |
Revision as of 17:48, 25 November 2012
--D. Thiebaut 16:24, 25 November 2012 (EST)
Top Down Approach: Version 1
Source
;;; hanoi1.asm
;;; D.T.
;;; Towers of Hanoi, top down...
;;; assumptions:
;;; al = n Number of disk
;;; bl = Source character identifying the source
;;; cl = Dest character identifying the destination
;;; dl = Temp character identifying the extra peg
section .data
moveStr db "X --> X", 10
moveStrLen equ $-moveStr
source equ moveStr + 0
dest equ moveStr + 6
section .text
global _start
;;; ------------------------------------------------------------
;;; M A I N
;;; ------------------------------------------------------------
_start: mov al, 4 ; move 4 disks
mov bl, 'A' ; from A
mov cl, 'B' ; to B
mov dl, 'C' ; using C as extra
call moveDisks
;;; return to OS
mov eax, 1
mov ebx, 0
int 0x80
;;; ------------------------------------------------------------
;;; moveDisks:
;;; assumptions:
;;; al = n Number of disk
;;; bl = Source character identifying the source
;;; cl = Dest character identifying the destination
;;; dl = Temp character identifying the extra peg
;;; Does not return anything
;;; does not modify registers
;;; ------------------------------------------------------------
moveDisks: push ax
push bx
push cx
push dx
mov byte[source], bl
mov byte[dest], cl
call printMove
pop dx
pop cx
pop bx
pop ax
ret
;;; ------------------------------------------------------------
;;; printMove
;;; Prints the string moveStr on the screen
;;; Does not alter any register
;;; ------------------------------------------------------------
printMove: pushad
mov eax, 4
mov ebx, 1
mov ecx, moveStr
mov edx, moveStrLen
int 0x80
popad
ret
Output
[231a@beowulf ~/handout]$ nasmld hanoi1 A --> B
Top Down Version 2
[231a@beowulf ~/handout]$ cat hanoi2.asm
;;; hanoi2.asm
;;; D.T.
;;; Towers of Hanoi, top down...
;;; assumptions:
;;; al = n Number of disk
;;; bl = Source character identifying the source
;;; cl = Dest character identifying the destination
;;; dl = Temp character identifying the extra peg
;;; %define N 6 ; number of disks to move
section .data
moveStr db "X X", 10
moveStrLen equ $-moveStr
source equ moveStr + 0
dest equ moveStr + 2
section .text
global _start
;;; ------------------------------------------------------------
;;; M A I N
;;; ------------------------------------------------------------
_start: mov al, N ; move 4 disks
mov bl, 'A' ; from A
mov cl, 'B' ; to B
mov dl, 'C' ; using C as extra
call moveDisks
;;; return to OS
mov eax, 1
mov ebx, 0
int 0x80
;;; ------------------------------------------------------------
;;; moveDisks:
;;; assumptions:
;;; al = n Number of disk
;;; bl = Source character identifying the source
;;; cl = Dest character identifying the destination
;;; dl = Temp character identifying the extra peg
;;; Does not return anything
;;; does not modify registers
;;; ------------------------------------------------------------
moveDisks: push ax
push bx
push cx
push dx
cmp al, 1
ja .recurse
;;; only 1 to move: move from source to dest!
mov byte[source], bl
mov byte[dest], cl
call printMove
jmp .return
.recurse:
;;; move n-1 disk from source to temp
dec al ; al <-- n-1
xchg cl, dl ; swap dest and temp
call moveDisks
xchg cl, dl ; swap back dest and temp
;;; move 1 from source to dest
push ax
mov al, 1
mov byte[source], bl
mov byte[dest], cl
call printMove
pop ax
;;; move n-1 disk from temp to dest
xchg bl, dl ; make temp the source
call moveDisks
.return: pop dx
pop cx
pop bx
pop ax
ret
;;; ------------------------------------------------------------
;;; printMove
;;; Prints the string moveStr on the screen
;;; Does not alter any of the registers
;;; ------------------------------------------------------------
printMove: pushad
mov eax, 4
mov ebx, 1
mov ecx, moveStr
mov edx, moveStrLen
;;; int 0x80
popad
ret