The problem is stated as follows.
There are three identical rods, and we are given N disks of varying sizes. All the disks are initially stacked up onto one of the rods in the descending order of the disk size from bottom to top, i.e., the largest on the bottom and the smallest on the top. We are to move all the disks from one rod to another with three rules:
1. Only one disk can be moved at a time.
2. Only the top-most disk can be moved from one rod and be placed onto a different rod.
3. No disk can be placed on top of a smaller disk.
With these rules, what is the method for moving some arbitrary N disks? What is the minimum number of moves required to do so?
It is rather a difficult problem at first glance. Probably the simplest way to solve this mathematically is by induction.
As with any other mathematical induction problem, one starts with the base case: N=1. We simply move the only disk from one rod to another. That's it. Very simple. So, the it requires f(1)=1 move, where f(n) represents the minimum number of moves required to solve the problem for n disks.
Next, we assume that we have a way of solving the case for some N=n. Utilizing this, can we solve the case for N=n+1? You bet! Assume that initially n+1 disks are stacked onto rod 1. We break the process of moving n+1 disks into three steps:
1. Move the upper n disks to a different rod, say rod 2 using the aforementioned assumption.
2. Move the largest disk to the other rod, say rod 3.
3. Move the n disks on rod 2 onto rod 3, again using the same method.
Note that these processes all obey the three rules for the Tower of Hanoi. In addition, this must be the minimum number of moves; there simply is no way to do it with fewer moves while still obeying the rules.
So, if it requires f(n) moves to solve the problem for the case of N=n, then we readily see that f(n+1)=2*f(n)+1, i.e., it requires 2*f(n)+1 moves to solve the problem for the case of N=n+1. Now, I will argue that f(n)=2^n-1. Let's prove this by induction.
Base case: f(1) = 2^1-1 = 1
Assumption: f(n) = 2^n-1
Next case: f(n+1) = 2*f(n)+1 = 2*(2^n-1)+1 = 2^(n+1)-1
That's it. We have proved it using induction. Now, it is time to implement in program. We do this by recursion. With it, I can get the step by step move instruction for moving, say 4 disks from rod 1 to 3.
$ javac Hanoi.java
$ java Hanoi 4
Move #1: disk1; rod 1==>2
Move #2: disk2; rod 1==>3
Move #3: disk1; rod 2==>3
Move #4: disk3; rod 1==>2
Move #5: disk1; rod 3==>1
Move #6: disk2; rod 3==>2
Move #7: disk1; rod 1==>2
Move #8: disk4; rod 1==>3
Move #9: disk1; rod 2==>3
Move #10: disk2; rod 2==>1
Move #11: disk1; rod 3==>1
Move #12: disk3; rod 2==>3
Move #13: disk1; rod 1==>2
Move #14: disk2; rod 1==>3
Move #15: disk1; rod 2==>3
Total moves required is 15
Below is the implementation in Java.
// Hanoi.java
public class Hanoi
{
static int moves = 0;
/** implements the Tower of Hanoi problem via recursion
* the argument to the program should be an integer
N > 0
*/
public static void main (String[] args)
{
int N;
if (args.length == 0)
{
System.out.println ("Error: Provide a
positive integer number N");
System.exit(-1);
}
N = Integer.parseInt(args[0]);
if (N < 1)
{
System.out.println ("Error: N must be
positive");
System.exit(-1);
}
int moves = moveDisks (N, 1, 3);
if (moves != Hanoi.moves)
{
System.out.println ("Error: Something is
wrong with the implementation!!");
System.exit(-1);
}
System.out.println ("Total moves required is
" + moves);
return;
}
/** recursively move n disks to a different rod
* three rods are indexed 1,2,3
*
* @param n is the number
of disks to move
* @param from is the rod
index from which to move
* @param to is the rod
index to which to move
* @return the minimum number
of moves
*/
static int moveDisks (int n, int from, int to)
{
if (n == 1)
{
/* base case */
moves++;
System.out.println ("Move #" + moves + ": disk1; rod " + from + "==>" + to);
return 1;
}
/* index number of the remaining rod */
int rem = 1;
for (int i=1; i<=3; i++)
{
if (rem == from || rem == to)
rem++;
else
break;
}
/* move n-1 disks from FROM to REM */
int sum = moveDisks (n-1, from,
rem);
/* move the largest disk */
moves++;
System.out.println ("Move #" + moves + ": disk" + n + "; rod " + from + "==>" + to);
sum++;
/* move the n-1 disks back from REM to TO */
sum += moveDisks (n-1, rem, to);
return sum;
}
}
No comments:
Post a Comment