Beautifull Java code for "Tower of Hanoi" problem by Keshav

A code by Keshav, from Cetpa Infotech.

The Tower of Hanoi 

Tower of Hanoi is a mathematical game.

 it consist of 3 rods and different size of disks

and they will in ascending order from top to bottom

which can slide onto any rod.

There is some rules: 

==>only one disk can slide at a time from one rod to another.

==>disks should be in ascending order from top to bottom

==>only top of the disk can slide.

To know more about "Tower of Hanoi" please click on this link want to know more about tower of hanoi

Note: Please create a Java project in Eclipse and save this class as TowerOfHanoi.java file

import java.util.Scanner;

import java.util.InputMismatchException;

public class TowerOfHanoi {

/* 

 lets define a method toh() which will be call recursively. 

 this method will take three arguments. 1st argument will be

 number of disk (nod), 2nd argument will be source rod or 

 can say starting rod, 3rd argument will be middle rod and

 4th argument will be last rod or destination rod.

  

 so it will be like

 toh(number_of_disk,starting_rod,middle_rod,last_rod)

  

 number_of_disk==> nod

  

 note: slide of a disk will be source to destination.

  

 At the end of the program we will see how to calculate 

 time complexity of this program.

 */

static int moves = 0;

static int toh(int nod,String st,String mi,String la)

{

// if ther is only one disk

if(nod==1)

{

System.out.println("Step "+(moves+1)+"==> Move "+st+" to "+la);

moves++;

}

// otherwise

else

{

/* here st means A

    la means C

    mi means B 

*/

 

toh(nod-1,st,la,mi);

/* here st means A

     mi means B

     la means C 

*/

toh(1,st,mi,la);

/* here mi means B

     st means A

     la means C 

*/

toh(nod-1,mi,st,la);

}

return moves;

}

public static void main(String[] args) {

// nod means number_of_disks

int nod;

// lets get the number of disk

Scanner sc=new Scanner(System.in);

System.out.print("enter number of disk to be moved :");

try

{

nod=sc.nextInt();

}

catch(InputMismatchException e)

{

System.out.println("you have given wrong input");

System.out.println("try again");

// lets initialize the nod with 0 and terminate the jvm

nod=0;

System.exit(0);

}

// it indicates starting rod

// let give a name to it as "A"

String start="A";

// it indicates middle rod

// let give a name to it as "B"

String middle="B";

// it indicates last rod

// let give a name to it as "C"

String last="C";

int moves = toh(nod,start,middle,last);

System.out.println("No of moves are "+moves);

}

}

// end of the programe

lets calculate time complexity of this code =>

as we have call 3 methods as follows 

toh(nod-1,st,la,mi);==>it will execute T(n-1) time

toh(1,st,mi,la); ==>it will execute only 1 time

toh(nod-1,mi,st,la);==>it will execute T(n-1) time

where n indicates number_of_disk

so overall time will be

T(n)=T(n-1)+1+T(n-1)=2T(n-1)+1

so the time complexity we will get as O(2^n).