Difference between revisions of "CSC231 Analysis of the Towers of Hanoi"

From dftwiki3
Jump to: navigation, search
(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)


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