Divide-and-Conquer Algorithms and Tower of Hanoi Puzzle in core-java

What is Divide-and-Conquer Algorithms?

Divide-and-Conquer Algorithms:

The Divide-and-Conquer approach is commonly used with recursion.The recursive binary search is an example of the divide-and-conquer . actually you divide big problem into small problem and solve them separately.A divide and conquer approach usually involves a method that contains two recursive calls to itself,one for each half of the problem.

The Tower of Hanoi:

The Towers of hanoi is an ancient puzzle consisting of a number of disks placed on three columns.Three disks all have different diameters and holes in the middle so they will fir over the columns.

The Recursive Algorithm to solve this problem:

The solution to the Towers of Hanoi puzzle can be expressed recursively using the notion of sub trees.Suppose you want to move all the disks from a source tower to a destination tower .you have an intermediate tower available .

1. Move the sub tree consisting of the top n-1 disks from S to I.
2. Move the remaining disk from S to D.
3. Move the sub tree from I to D.

Code Sample:

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */

public class TowerofHanoiApp
{
   static int nDisks=3;
 
public static void main(String[] args)
{
doTowerofHanoi(nDisks,'A','B','C');
}

private static void doTowerofHanoi(int topN, char from, char inter, char to)
{

if(topN == 1)
System.out.println("Disk 1 from "+from + " to "+to);
else
{
doTowerofHanoi(topN-1, from, to, inter);
System.out.println("Disk" + topN + "from" + from +" to" + to);
doTowerofHanoi(topN-1, inter, from, to);
}
}


}