Write via Word Document with collegiate writing and using pseudocode describing
ID: 3702609 • Letter: W
Question
Write via Word Document with collegiate writing and using pseudocode describing three "poles"
and how the "Towers of Hanoi" uses recursion to make it work. The code is below. Thanks in advance.
/**
Describe how this program works, making sure that you include the word that describes calling a method from within that method.
"Google it!"
*/
public class TowersOfHanoi {
public static void main(String[] args) {
int nDisks = 3;
triTowers(nDisks, 'A', 'B', 'C');
}
public static void triTowers(int topN, char from, char inter, char to) {
if (topN == 1) {
System.out.printf("Moving disk 1 from pole %c to pole %c ", from, to);
} else {
triTowers(topN - 1, from, to, inter);
System.out.printf("Moving disk %d from pole %c to pole %c ", topN, from, to);
triTowers(topN - 1, inter, from, to);
}
}
}
Explanation / Answer
Solution:
This problem is about Tower of hanoi:
Generally, In Tower of hanoi problem, we are given three towers and some discs are placed in a tower which is called as source tower in order as larger ones are at the bottom and the smaller one is on the top and all the discs are placed in that order, which means no larger disc will be placed on the smaller disc.
Now we have to switch the tower which is known as destination tower destination tower in such a manner so that there is no violation of the stated rule, we have the third tower which is called spare tower through which we have to accomplish our objective.
Pseudo Code:
changeTower(disk, source, destination, spare)
If number if disk == 0, then
destination= source
Otherwise,
changeTower(disk - 1, source, spare, destination)
shift the disk from source to destination
changeTower(disk - 1, spare, destination, source)
end.
The base case is when n=1; this means that when we have only one disk in the source tower then only one move needs to be done which is shifting that disk to destination tower.
we can write is T(1)= 1,
in other cases when the disks is more than 1 (n>1)
then n-1 disks needed to move to spare tower and then they move n-1 disks to the destination tower again
So recurrence relation T(n)= 2T(n-1) - 1
The expression to be prove is 2^n -1
Startly we will prove true for n = 1.
For n = 1 the expression gives 2^1 - 1 = 1 and that is true.
Now check with n = k, that we rewrite expression as
p(k) = 2^k - 1
let us add next disk..then number of disks increased by 1...k+1
putting k+1 to previous expression
p(k+1) = 2*p(k) + 1
= 2(2^k - 1) + 1
= 2^(k+1) - 2 + 1
= 2^(k+1) - 1
after replacing k with k+1. so if n=k is true then it must be true for n=k+1...Hence it is in the form of 2^n -1.
Hence we proved by using mathematical Induction.
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.