Question

(IN JAVA)

Legend says that this problem was originated either by Buddhist monks, Brahman priests, or the guardians of a Vietnamese temple, take your pick. In each case, they believed that if the puzzle could be solved using 64 disks, the world would end. Since the number of moves required to solve the Tower of Hanoi problem using “n” disks is 2ⁿ - 1, and assuming that each move would take roughly one second, then moving 64 disks from one peg to another would take almost 600 billion years to complete. (Astronomers tell us that universe as we know it today is no more than 14 billion years old, and the life of our sun is roughly 10 billion years, with 5 billion still to go.)

The most common algorithm to solve this problem involves multiple recursion. Here’s the pseudocode for such a method:

• Invoke the method specifying these 4 parameters for this level of recursion:
  1. n (the number of disks to move)
  2. the from peg
  3. the to peg
  4. an intermediate peg as necessary
• Base case: if n = 0, then just return (do nothing)
• Recursive case:
  • Step 1: invoke method again (a new level of recursion) using parameters
    1. n – 1 (the number of disks to move)
    2. from the current from peg
    3. to the current intermediate peg
    4. using the current to peg as necessary
  • Step 2: move the n^th peg from the current from peg to the current to peg
  • Step 3: invoke method again (a new level) using as parameters
    1. n – 1 (the number of disks to move)
    2. from the current intermediate peg
    3. to the current to peg
    4. using the current from peg as necessary

Write a method in Java that implements the above pseudocode. Show the moves required by adding a “print” statement in Step 2 of the recursive case showing the current fromand to pegs.

Write a “tester” program to display the moves required when n = 3, n = 4, and n = 5 (input from the user?). To make things easy, label the initial from peg A, the initial intermediatepeg B, and the initial to peg C.

Answer 1

import java.util.Scanner;
public class Tower
{
public static void TOH(int N,char P,char Q,char R) //function of tower of hanoi problem
   {
   if (N==0) //if n==0 return it
       return;
   else
       {
       TOH(N-1,P,R,Q); //recursive equation
       System.out.println("Move From " + P + " to " + Q); // printing move from which peg to which peg
       TOH(N-1,R,Q,P); // again invoking recursive function
       }
   }
public static void main(String args[])
   {
   while (true) //iterating loop until user enters the number which is less than or equal to 1
       {
       Scanner input=new Scanner(System.in);
       System.out.println("Enter the N value");
       int n=input.nextInt(); //input taking
       if (n<=1)
           break;   // if number less than or equal to 1 break
       TOH(n,'A','B','C'); //else call TOH() function
       }
   }
}

Code and Screenshot Ouptut:

Note : If you have any queries please post a comment thanks a lot....