Using your version of the Towers of Hanoi program from Exercise 12, answer the f
ID: 3593908 • Letter: U
Question
Using your version of the Towers of Hanoi program from Exercise 12, answer the following:
a. Fill in the table with the number of moves required to solve the problem, starting with the given number of rings.
b. Describe the pattern you see in the number of moves listed in your table.
c. Assuming n > 0, define the number of moves required to move n rings using a recursive mathematical formula.
d. Suppose you have a physical Towers of Hanoi puzzle with 11 rings. If it takes one second to move a ring from one peg to another, how long would it take you to “solve” the puzzle?
e. In Java the data type int uses 32 bits and can represent integers in the range -2,147,483,648 to 2,147,483,647. By experimenting with your program from Exercise 12, figure out the largest number of rings that the program can handle before “blowing up” - that is before the value in count overflows.
f. What is the number of moves reported for that number of rings? How close is that to the maximum int value? Explain.
CODE FROM EXAMPLE 12:
import java.util.Scanner;
public class Towers
{
private static String indent =""; //indentation for trace
public static void main(String [] args)
{
Scanner conIn = new Scanner(System.in);
//Number of rings on starting peg.
int n;
System.out.print("Input the number of rings: ");
if (conIn.hasNextInt())
n = conIn.nextInt();
else
{
System.out.println("Error: you must enter an integer.");
System.out.println("Terminating program. ");
return;
}
System.out.println("Towers of Hanoi with " + n + " ring ");
doTowers(n, 1, 2, 3);
}
public static void doTowers(
int n, //number of rings to move
int startPeg, //peg containing rings to move
int auxPeg, //Peg holding ring temporarily
int endPeg ) // peg receiving ring being moved
{
if (n > 0)
{
indent = indent + " ";
System.out.println(indent + "Get " + n + " rings moved from peg "
+ startPeg + " to peg " + endPeg);
//Move n-1 rings from starting peg to auxiliary peg.
doTowers(n-1, startPeg, endPeg, auxPeg);
//Move nth ring from starting peg to ending peg.
System.out.println(indent + "Move ring " + n + " from peg"
+ startPeg + "to peg" + "endPeg");
//Move n - 1 ring from auxiliary peg to ending peg
doTowers(n - 1, auxPeg, startPeg, endPeg);
indent = indent.substring(2);
}
}
}
Moves RingsExplanation / Answer
Solution:
Solution:
a)
b)
The number of moves required to solve the problem is always an odd number, and 1 less than the power of two.
c)
Number of moves= 2^(number of rings) - 1= 2^(n) - 1
d)
To solve 11 rings it will take= 2^11 - 1= 2047
considering each move is taking 1 second
time taken= 2047 seconds= 34 minutes 7 seconds
e)
Largest number will be 2^31 - 1= 2,147,483,647
and the number of rings can be solved within int data type is 31 rings.
f)
The number of moves is exactly same as the maximum value for 31 rings.
please upvote and raise your doubts within the comment.
Rings Moves 1 1 2 3 3 7 4 15 5 31 6 63 7 127 8 255Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.