2. (2 pts) Let\'s reconsider the Towers of Hanoi problem. Recall that the monks

Question

2. (2 pts) Let's reconsider the Towers of Hanoi problem. Recall that the monks had 64 discs, and once they solved the problem, the world would end. Thankfully, they didn't solve the problem, and we'll see why here. (a) In class, we saw that the Towers of Hanoi problem required 31 moves for 5 discs. Thinking recursively, how many moves are required for 6 discs? Briefly show how you used recursion to come up with your answer. (b) Given your answer above, how many moves are required to move n discs as a function of n? (c) Now back to the monks. If they had 64 discs and moved one disc per minute (remember these were pretty heavy for monks), how long would it take for them to solve the problem if they didn't stop to do anything else? Express your answer rounded to the nearest year. GMaolo2335422

Explanation / Answer

Solution:

1)

a)

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.

Algorithm:

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

T(1)= 1

T(2)=2T(1) - 1

=3

T(3)=2T(2) - 1

=7

T(4)=2T(3) - 1

=15

T(5)=2T(4) - 1

=31

after observing the pattern, we can conclude that

T(n) = 2n - 1.

We can verify this easily by plugging it into our recurrence.

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

b)

As proven above it takes (2^n) - 1 moves to sort the tower.

so at n=6

it will tak (2^6) - 1= 63

c)

to solve with 64 disks it will take

(2^64) - 1= 1.8446744e+19 minuts

let's change this in years.

by dividing it by (60*24*365)

it will take 35096545000000 years to solve by the monks.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

T(1)= 1

T(2)=2T(1) - 1

=3

T(3)=2T(2) - 1

=7

T(4)=2T(3) - 1

=15

T(5)=2T(4) - 1

=31

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.