CPT210: Coursework
Introduction
The specification may be updated one or more times. Changes will be highlighted in the
document when updated. Please make sure you follow the most recent announcements of
CPT210. The Towers of Hanoi problem, also known as Lucas’ Tower or Tower of Bramha’s, is a
mathematical puzzle developed by a Mathematician of French Origin named Édouard Lucas. It
is believed that the Solution and Problem for Towers of Hanoi Algorithm was invented by the
mathematician in an Indian city in 1883.
The goal of this game is to move the disks on the source tower to the destination tower (A
tower is also frequently called as peg) without violating the following movement rules: Only one disk can be moved among the towers at any given time. Only the "top" disk can be removed. No large disk can sit over a small disk. To move these disks, you can make use of a temporary tower, also called as an auxiliary tower. This problem can easily be solved using a recursive procedure:
1. Move N-1 Disks from Source Tower to Temporary Tower
2. Move Nth Disk from Source Tower to Destination Tower
3. Move N-1 Disks from Temporary Tower to Destination Tower (using Source Tower as
Temporary Tower)
For a total of n disks, 2^n – 1 moves are required. The corresponding C/Java code is shown in
the next page to illustrate the logic.
C code for the Hanoi problem:
#include
int hanoi(int limit, char src, char tmp, char dst)
{
if(limit == 0)
{
return 0;
}
else
{
hanoi(limit - 1, src, dst, tmp);
printf("Move Disk %d From %c To %c\n", limit, src, dst);
hanoi(limit - 1, tmp, src, dst);
return 0;
}
}
int main()
{
char src_tower = 'A', tmp_tower = 'B', dst_tower = 'C';
int limit;
printf("\nEnter The Number of Disks:\t");
scanf("%d", &limit);
printf("\nSequence of Disks:\n");
hanoi(limit, src_tower, tmp_tower, dst_tower);
printf("\n");
return 0;
}
Java Version:
import java.util.Scanner;
class Hanoi {
static void hanoi(int limit, char src, char tmp, char dst) {
if(limit == 0) {
return;
} else {
hanoi(limit - 1, src, dst, tmp);
System.out.printf("Move Disk %d From %c To %c\n",
limit, src, dst);
hanoi(limit - 1, tmp, src, dst);
return;
}
}
public static void main(String[] args) {
char src_tower = 'A', tmp_tower = 'B', dst_tower = 'C';
int limit;
System.out.printf("\nEnter The Number of Disks:\t");
Scanner scanner = new Scanner(System.in);
limit = scanner.nextInt();
System.out.printf("\nSequence of Disks:\n");
hanoi(limit, src_tower, tmp_tower, dst_tower);
System.out.printf("\n");
}
}
r6 r7 r8
printf("Move Disk %d From %c To %c\n", limit, src, dst);
System.out.printf("Move Disk %d From %c To %c\n", limit, src, dst);
Coursework Requirements
In this coursework, your task is to implement an ARM assembly program that works for the
Hanoi problem. the program should work in the VisUAL emulator. Since VisUAL does not
support printing out text in the console, you are required to output the movement information
into three registers: r6, r7 and r8. In the C and Java code, ‘A’ ‘B’ and ‘C’ refers to the three
towers of the Hanoi game. In your ARM program, you should use 0x1, 0x2 and 0x3 to refer to
these three towers. You should report the movement of disks by writing 0x1, 0x2 or 0x3 into r7
and r8, and the value of limit into r6. That is, each time the follow printf() function executes, the
corresponding assembly code should update the value in these registers.
The number of disks is specified in the register r9 at the beginning of the program. Your
program should work correctly for different number of disks. You do not need to consider
exceptional situations like negative number of disks or zero disks. Due to the limitation of the
VisUAL simulator, I will test the program with smaller numbers of disks. Name your code file as “firstname_lastname_id.s”. For example: “Jianjun_Chen_6501295.s”. Then
submit it to the LearningMall. The deadline is 3
rd June 2021.