Implement the two versions of the solveTower algorithm given in Segment 7.31 7.3
ID: 3857336 • Letter: I
Question
Implement the two versions of the solveTower algorithm given in Segment 7.31
7.31) Before we write some pseudocode to describe the algorithm, we need to identify a base case. If
only one disk is on pole 1, we can move it directly to pole 3 without using recursion. With this as
the base case, the algorithm is as follows:
Algorithm to move numberOfDisks disks from startPole to endPole using tempPole
as a spare according to the rules of the Towers of Hanoi problem
if (numberOfDisks == 1)
Move disk from startPole to endPole
else
{
Move all but the bottom disk from startPole to tempPole
Move disk from startPole to endPole
Move all disks from tempPole to endPole
}
At this point, we can develop the algorithm further by writing
Algorithm solveTowers(numberOfDisks, startPole, tempPole, endPole)
if (numberOfDisks == 1)
Move disk from startPole to endPole
else
{
solveTowers(numberOfDisks - 1, startPole, endPole, tempPole)
Move disk from startPole to endPole
solveTowers(numberOfDisks - 1, tempPole, startPole, endPole)
}
If we choose zero disks as the base case instead of one disk, we can simplify the algorithm a
bit, as follows:
Algorithm solveTowers(numberOfDisks, startPole, tempPole, endPole)
// Version 2
if (numberOfDisks > 0)
{
solveTowers(numberOfDisks - 1, startPole, endPole, tempPole)
Move disk from startPole to endPole
solveTowers(numberOfDisks - 1, tempPole, startPole, endPole)
}
Although somewhat easier to write, the second version of the algorithm executes many more recursive
calls. Both versions, however, make the same moves.
. Represent the towers by either
single characters or strings. Each method should display directions that indicate the moves that must be made.
Insert counters into each method to count the number of times it is called. These counters can be data fields of
the class that contains these methods. Compare the number of recursive calls made by each method for various
numbers of disks.
Explanation / Answer
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package chegg;
import java.util.Scanner;
class TowerProblem {
int version1Moves;// Count no. of moves for version1 method
int version2Moves;// Count no. of moves for version2 method
int version1RecursionCalls;// Count no. of recursions for version1 method
int version2RecursionCalls;// Count no. of recursions for version2 method
public void solveTowersVersion1(int n, String startPole, String tempPole, String endPole) {
if (n == 1) {
// System.out.println(startPole + " -> " + endPole);
version1Moves++;// Increment for each move
} else {
version1RecursionCalls++;// Increment for each recursion call
solveTowersVersion1(n - 1, startPole, endPole, tempPole);
// System.out.println(startPole + " -> " + endPole);
version1Moves++;// Increment for each move
version1RecursionCalls++;// Increment for each recursion call
solveTowersVersion1(n - 1, tempPole, startPole, endPole);
}
}
public void solveTowersVersion2(int n, String startPole, String tempPole, String endPole) {
if (n > 0){
version2RecursionCalls++;// Increment for each recursion call
solveTowersVersion2(n - 1, startPole, endPole, tempPole);
// System.out.println(startPole + " -> " + endPole);
version2Moves++;// Increment for each move
version2RecursionCalls++;// Increment for each recursion call
solveTowersVersion2(n - 1, tempPole, startPole, endPole);
}
}
public static void main(String[] args) {
TowerProblem towersProblem = new TowerProblem();
System.out.print("Enter number of discs: ");
Scanner scanner = new Scanner(System.in);
int numberOfDisks = scanner.nextInt();
towersProblem.solveTowersVersion1(numberOfDisks, "Start", "Temp", "End");
towersProblem.solveTowersVersion2(numberOfDisks, "Start", "Temp", "End");
System.out.println("Version1 Moves: " + towersProblem.version1Moves + " Version2 Moves: " + towersProblem.version2Moves);
System.out.println("Version1 Recursions: " + towersProblem.version1RecursionCalls + " " + " Version2 Recusions: " + towersProblem.version2RecursionCalls);
}
}