Program 6: Towers of Hanoi

Transcribed Text

Program 6: Towers of Hanoi1 In Hanoi, according to legend, are three diamond rods and 64 golden discs of different sizes which can slide onto any rod. Initially all the discs are on a single rod in descending order of size – smallest at the top. Monks move the discs, one per second, from one rod to another obeying the following rules 1. Only one disc can be moved at a time. 2. Each move consists of taking the top disc from one of the stacks and placing it on top of another stack or on an empty rod. 3. No larger disc may be placed on top of a smaller disc. Their objective is to move all the discs onto a second diamond rod at which point the world ends. If we number the rods 1, 2 and 3 there is a simple recursive routine to produce the move sequence Hanoi(int Numdiscs, int source, int destination) { if (Numdiscs>1) Hanoi(Numdiscs-1,source,6-source-desination) output (“move disc on”, source, “to”, destination) if (Numdiscs>1) Hanoi(Numdiscs-1,6-source-destination,destination) } Write a Pep/9 assembly code program that implements an augmented version of the algorithm. Your program should: Prompt for Number of discs (<16) Source rod (1,2 or 3) Destination rod (1, 2 or 3) Whether moves are to be displayed (y/n) A move number (k). Compute the move sequence, outputting the details if requested Output the contents of the rods after move k (if there is one) – see examples Output the total number of moves. Extra credit: Output the rod contents vertically – see Extra Credit examples By the due date, turn in your source code and results of testing it. Grading Correctness 50 Testing 20 Readability 30 1 https://en.wikipedia.org/wiki/Tower_of_Hanoi Example program runs Number of discs (<16): 10 Source rod (1,2,3): 1 Destination rod (1,2,3): 3 Show moves? (y/n): n Show discs after move k: -1 Total moves: 1023 Number of discs (<16): 10 Source rod (1,2,3): 1 Destination rod (1,2,3): 2 Show moves? (y/n): n Show discs after move k: 1022 After move 1022 Rod: 1 Rod: 2 10 9 8 7 6 5 4 3 2 Rod: 3 1 Total moves: 1023 Number of discs (<16): 3 Source rod (1,2,3): 1 Destination rod (1,2,3): 3 Show moves? (y/n): y Show discs after move k: 0 move disc on rod 1 to rod 3 move disc on rod 1 to rod 2 move disc on rod 3 to rod 2 move disc on rod 1 to rod 3 move disc on rod 2 to rod 1 move disc on rod 2 to rod 3 move disc on rod 1 to rod 3 Total moves: 7 Number of discs (<16): 15 Source rod (1,2,3): 1 Destination rod (1,2,3): 2 Show moves? (y/n): n Show discs after move k: 5 After move 5 Rod: 1 15 14 13 12 11 10 9 8 7 6 5 4 1 Rod: 2 3 Rod: 3 2 Total moves: 32767 Number of discs (<16): 4 Source rod (1,2,3): 1 Destination rod (1,2,3): 3 Show moves? (y/n): y Show discs after move k: 10 move disc on rod 1 to rod 2 move disc on rod 1 to rod 3 move disc on rod 2 to rod 3 move disc on rod 1 to rod 2 move disc on rod 3 to rod 1 move disc on rod 3 to rod 2 move disc on rod 1 to rod 2 move disc on rod 1 to rod 3 move disc on rod 2 to rod 3 move disc on rod 2 to rod 1 After move 10 Rod: 1 2 Rod: 2 3 Rod: 3 4 1 move disc on rod 3 to rod 1 move disc on rod 2 to rod 3 move disc on rod 1 to rod 2 move disc on rod 1 to rod 3 move disc on rod 2 to rod 3 Total moves: 15 Extra Credit Example runs Number of discs (<16): 14 Source rod (1,2,3): 1 Destination rod (1,2,3): 3 Show moves? (y/n): n Show discs after move k: 1000 After move 1000 1 2 3 4 6 11 7 12 8 13 9 14 5 10 Rod 1 Rod 2 Rod 3 Total moves: 16383 Number of discs (<16): 10 Source rod (1,2,3): 3 Destination rod (1,2,3): 1 Show moves? (y/n): n Show discs after move k: 1022 After move 1022 2 3 4 5 6 7 8 9 10 1 Rod 1 Rod 2 Rod 3 Total moves: 1023

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

; program 6
; Enhance Hanoi
;
;
;
; next - add parameter k and move counter
;       - call showpins when movecounter = k
;
;
;    showpins2 - ec
;
call main
stop
;
N:       .block 2            ; global variable #2d
S:       .block 2            ; global variable #2d
D:       .block 2            ; global variable #2d
K:       .block 2            ; global variable #2d
movevis: .block 2            ; global variable #2d
mvcount: .block 2            ; global variable #2d
whereis: .block 32          ;
P3:      .block 32
P2:      .block 32
P1:      .block 32
prompt1: .ascii "Number of discs (<16): \x00"
prompt2: .ascii "Source rod (1,2,3): \x00"
prompt3: .ascii "Destination rod (1,2,3): \x00"
prompt4: .ascii "Show discs after move k: \x00"
prompt5: .ascii "Show moves? (y/n): \x00"
str1:    .ascii "move disc on rod \x00"
str2:    .ascii " to rod \x00"
pin:    .ascii "Rod 1\tRod 2\tRod 3\x00"
after:   .ascii "After move \x00"
total:   .ascii "Total moves: \x00"
NL:      .ascii "\n\x00"
TAB:    .ascii "\t\x00"
SPACE:   .ascii " \x00"
main:    stro prompt1,d      ; number of discs
deci N,d
stro prompt2,d      ; start corner
deci S,d
stro prompt3,d      ; end corner
deci D,d
try:    stro prompt5,d
ldba charIn,d
cpba 'y',i
breq yesshow
cpba 'n',i
breq noshow
br try               ; neither n nor y - try again
yesshow: ldwa 1,i
stwa movevis,d       ; movevis = 1; show moves
br init
noshow: ldwa 0,i
stwa movevis,d       ; movevis = 0; do not show moves
init:    stro prompt4,d       ; show discs after move k
deci K,d
;initialize whereis
ldwx N,d
aslx
ldwa S,d
L:       stwa whereis,x
subx 2,i
brgt L
;initialize mvcount
ldwa 0,i
stwa mvcount, d
; call Hanoi
ldwa K,d
stwa -2,s
ldwa N,d
stwa -4,s
ldwa S,d
stwa -6,s
ldwa D,d
stwa -8,s
subsp 8, i          ; push #k #Numdiscs #src #dst
call Hanoi
addsp 8, i          ; pop #k #Numdiscs #src #dst
stro total, d
deco mvcount, d

ret

;...
\$45.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Assembly Language Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.