The Recursive solution for the Tower of Hanoi problem has been discussed in another post. Here I am discussing two non recursive algorithms to solve the problem.
- Iterative Solution
Alternate moves between the smallest disk and a non-smallest disk is carried out in the iterative solution. When moving the smallest disk, always move it to the next position in the same direction. If there is no peg position in the chosen direction, move the disk to the opposite end, but then continue to move in the correct direction. Doing this will complete the puzzle using the fewest number of moves to do so.
Figure Below Shows the Output for 3 Disks
- Binary Solution
- There is one binary digit for each disk.
- The most significant bit represents the largest disk. A value of 0 indicates that the largest disk is on the initial peg, while a 1 indicates that it's on the final peg.
- The bit string is read from left to right, and each bit can be used to determine the location of the corresponding disk.
- A bit with the same value as the previous one means that the corresponding disk is stacked on top the previous disk on the same peg.
- A bit with a different value to the previous one means that the corresponding disk is one position to the left or right of the previous one. The initial peg is on the left and the final peg is on the right. The right peg counts as one peg "left" of the left peg, and vice versa. Let n be the number of greater disks that are located on the same peg as their first greater disk and add 1 if the largest disk is on the left peg. If n is even, the disk is located one peg to the left, if n is odd, the disk located one peg to the right.
Figure Below Shows the Output for 3 Disks
Hi, can someone please write this above algorithm in small basic coding.
ReplyDelete