Difference between revisions of "CSC231 Analysis of the Towers of Hanoi"
(→Top Down Approach: Version 1) |
(→Top Down Approach: Version 1) |
||
Line 1: | Line 1: | ||
--[[User:Thiebaut|D. Thiebaut]] 16:24, 25 November 2012 (EST) | --[[User:Thiebaut|D. Thiebaut]] 16:24, 25 November 2012 (EST) | ||
---- | ---- | ||
+ | =A High-Level Version in Python= | ||
+ | |||
+ | <br /> | ||
+ | <source lang="python"> | ||
+ | # hanoi.py (Python V 2.7) | ||
+ | # D. Thiebaut | ||
+ | # implements the game of hanoi in python. | ||
+ | # uses recursion. | ||
+ | # | ||
+ | # to run, type | ||
+ | # python hanoi.py | ||
+ | # at the command line | ||
+ | |||
+ | def moveDisk( source, dest, extra, n ): | ||
+ | if n==1: | ||
+ | print "move disk from %s to %s" % ( source, dest ) | ||
+ | return | ||
+ | |||
+ | # more than 1 disk... | ||
+ | moveDisk( source, extra, dest, n-1) | ||
+ | print "move disk from %s to %s" % ( source, dest ) | ||
+ | moveDisk( extra, dest, source, n-1) | ||
+ | |||
+ | def main(): | ||
+ | while True: | ||
+ | n = input( "# of disks? " ) | ||
+ | moveDisk( "A", "B", "C", n ) | ||
+ | |||
+ | main() | ||
+ | |||
+ | </source> | ||
+ | <br /> | ||
+ | |||
+ | |||
=Top Down Approach: Version 1= | =Top Down Approach: Version 1= | ||
Revision as of 17:50, 25 November 2012
--D. Thiebaut 16:24, 25 November 2012 (EST)
Contents
A High-Level Version in Python
# hanoi.py (Python V 2.7)
# D. Thiebaut
# implements the game of hanoi in python.
# uses recursion.
#
# to run, type
# python hanoi.py
# at the command line
def moveDisk( source, dest, extra, n ):
if n==1:
print "move disk from %s to %s" % ( source, dest )
return
# more than 1 disk...
moveDisk( source, extra, dest, n-1)
print "move disk from %s to %s" % ( source, dest )
moveDisk( extra, dest, source, n-1)
def main():
while True:
n = input( "# of disks? " )
moveDisk( "A", "B", "C", n )
main()
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