Tuesday, 13 December 2016

Exploring Tower of Hanoi - 1

This is more of an article than a blog but it is my exploration. On solving for different n's , I found that the bottom disk always moves only once. Similarly, second disk from the bottom moves 2 times. Third from the bottom always moves 4 times. And so on, they form the series => 1, 2, 4, 8, ... , 2^(n - 1) . The sum of these is of course equal to 2^n - 1 which was already mentioned above.

Now, we are given n disks and the bottom two disks are of same size then what will be the number of moves. The answer is simple from the above result. The bottom disk will move only once. Second disk from bottom has the same size that of bottom disk and it will also move only once. Third disk will move 2 times. Fourth disk will move 4 times. And they will for series like this => 1, 1, 2, 4, ... , 2^(n - 2). The sum of this series will be 2^(n - 1) + 1. So the minimum moves to transfer n disks from one tower to another given 3 tower, n disks such that bottom two disks have same size will be 2^(n - 1) + 1.

Similarly, if we are give n disks with top two disks same, minimum moves = 2^(n - 1) + 1 + 2^(n - 2). Also we can also find for any kth disk to same and more than one disk to be same.

I know that nobody would like to read somebody else's code but for the completeness of this blog I think that I should give the code as well. Here is a C implementation of very generalised form of Tower of Hanoi problem with as many disks of same size as the user wants : Github Gist

No comments:

Post a Comment