1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
public class TowerOfHanoi
{
// TO DO: Instance Variables
private HStack towers[] = new HStack[3];
private int numDiscs;
/* Construct the Towers of Hanoi (3 towers) with aNumDisc
* on the first tower. Each tower can be identified by an
* integer number (0 for the first tower, 1 for the second
* tower, and 2 for the third tower). Each disc can be identified
* by an integer number starting from 0 (for the smallest disc)
* and (aNumDisc - 1) for the largest disc.
*/
public TowerOfHanoi(int aNumDiscs)
{
towers[0] = new HStack();
towers[1] = new HStack();
towers[2] = new HStack();
for(int i = 1; i <= aNumDiscs; i++)
{
towers[0].push(aNumDiscs-i);
}
numDiscs = aNumDiscs;
}
/* Returns an array of integer representing the order of
* discs on the tower (from bottom up). The bottom disc should
* be the first element in the array and the top disc should be
* the last element of the array. The size of the array MUST
* be the number of discs on the tower. For example, suppose
* the tower 0 contains the following discs 0,1,4,6,7,8 (from top
* to bottom). This method should return the array [8,7,6,4,1,0]
* (from first to last).
* @param tower the integer identify the tower number.
* @return an array of integer representing the order of discs.
*/
public int[] getArrayOfDiscs(int tower)
{
return towers[tower].toArray();
}
/* Gets the total number of discs in this Towers of Hanoi
* @return the total number of discs in this Towers of Hanoi
*/
public int getNumberOfDiscs()
{
// TO DO
return numDiscs;
}
/* Gets the number of discs on a tower.
* @param tower the tower identifier (0, 1, or 2)
* @return the number of discs on the tower.
*/
public int getNumberOfDiscs(int tower)
{
return towers[tower].getLength();
}
/* Moves the top disc from fromTower to toTower. Note that
* this operation has to follow the rule of the Tower of Hanoi
* puzzle. First fromTower must have at least one disc and second
* the top disc of toTower must not be smaller than the top disc
* of the fromTower.
* @param fromTower the source tower
* @param toTower the destination tower
* @return ture if successfully move the top disc from
* fromTower to toTower.
*/
public boolean moveTopDisc(int fromTower, int toTower)
{
if(towers[fromTower].getLength() == 0)
{
return false;
}
if(towers[toTower].getLength() == 0)
{
towers[toTower].push(towers[fromTower].pop());
return true;
}
else if(towers[fromTower].peek() < towers[toTower].peek())
{
towers[toTower].push(towers[fromTower].pop());
return true;
}
else
{
return false;
}
}
public class HStack
{
private HNode head;
private int length;
public HStack()
{
length = 0;
}
public int peek()
{
return head.getData();
}
public int pop()
{
int output = head.getData();
head = head.getNext();
length--;
return output;
}
public void push(int i)
{
head = new HNode(i,head);
length++;
}
public boolean hasNext()
{
return head != null;
}
public int getLength()
{
return length;
}
public String toString()
{
String output = "";
for(HNode tmp = head; tmp != null; tmp=tmp.getNext())
{
output += tmp.getData() + " ";
}
return output;
}
public int[] toArray()
{
int[] output = new int[length];
int i = length-1;
for(HNode tmp = head; tmp != null; tmp = tmp.getNext())
{
output[i] = tmp.getData();
i--;
}
return output;
}
}
public class HNode
{
private HNode next = null;
private int data;
public HNode(int d, HNode n)
{
data = d;
next = n;
}
public int getData()
{
return data;
}
public HNode getNext()
{
return next;
}
}
}
|
