The Towers of Hano is a classical problem used to illustrate the power of puzzle
ID: 3688489 • Letter: T
Question
The Towers of Hano is a classical problem used to illustrate the power of puzzle goes as follows. power of recursion. The There are three poles and 64 discs of different sizes. Inially,all the discs are placed on the first pole with the largest disc at the bottom and the smalest one at the top.We need to movie all the discs from the first pole to the third pole, with the smallest disc at the bottom. We can move only one disc at at any point of time, a larger disc cannot be p pole must The s at the top and the largest a time (which should be the topmost disc) and laced over a smaller one i.e all the discs on a be placed in such a way that the smallest is at the top and the largest at the bottom. e second pole can be used as an intermediate pole to help us in transferring the discs. This puzzle can be solved using recursion. For a moment, assume that there are just two The solution consists of discs (disc 1 and 2; disc 2 being the larger one) on the first pole. The solution consists. three steps. Step 1: Move disc Step 2: Move disc Step 3: Move disc 1 from pole1 to pole 3 Move disc 1 from pole 1 to pole 2 Move disc 2 from pole 1 to pole 3 Now, assume that disc 1 is not a single disc but a collection of discs. The procedure would be similar to the above three steps, but steps 1 and 3 would be a collection of steps. Step 1 would be to move the n-1 discs (assuming that there were a total of n discs) from pole 1 to pole 2. For moving these (n -1) discs, we again follow the same strategy of considering them as 1 disc plus a set of n-2 discs. Step 3 would also be similar. This gives us the recursive solution. Recursive Algorithm The recursive solution to move n discs from the start pole to the end pole using an auxiliary pole is given below. Base Case-When n-1 Move the disc from start pole to end poleExplanation / Answer
Run this following code find time and number of moves.
1.Run Program with 64 disk takes huge time
2. Time taken to solve for
Number of Disk
4
8
16
32
64
Time taken to solve (in milliseconds)
1
9
4071
Will take huge time(run the following program in your system and note it)
Will take huge time(run the following program in your system and note it)
3. Number of Moves
Number of Disk
4
8
16
32
64
Number of Moves
15
255
65535
2^32-1
2^64-1
4.Yes, there is relation between number of disk and number of moves. If n is the number of disc then 2^n – 1 is the moves
import java.io.FileOutputStream;
import java.util.Scanner;
public class TowerofHanoi {
long count = 0; // initialize counter to zero
public void solve(int n, String start, String auxiliary, String end) {
count = count + 1;
if(n == 1) {
System.out.println(start + " -> " + end);
}else{
solve(n-1, start, end, auxiliary);
System.out.println(start + " -> " + end);
solve(n-1, auxiliary, start, end);
}
}
public static void main(String[] args) throws Exception{
TowerofHanoi toh = new TowerofHanoi();
System.out.println("Enter Number of disk : ");
Scanner scan = new Scanner(System.in);
int disc = scan.nextInt();
//calculate time taken to execute
long startTime = System.currentTimeMillis(); //start timer
toh.solve(disc, "A", "B", "C"); //call function
long endTime = System.currentTimeMillis(); // end timer
long timeTaken = endTime - startTime; //time taken to execute code
System.out.println("time taken = " + timeTaken + " miliseconds"); //print time taken
System.out.println("Number of Moves = " + toh.count); // number of moves
}
}
Number of Disk
4
8
16
32
64
Time taken to solve (in milliseconds)
1
9
4071
Will take huge time(run the following program in your system and note it)
Will take huge time(run the following program in your system and note it)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.