![]() ![]() So after every three moves, we can go with the other three moves and so on till we exhaust all our moves. I'll just state the algorithm here.You may need to know the stack data structure in C to implement it There are three poles.The source pole,The auxiliary pole and The Destination pole. To make space we must have a legal movement b/w auxiliary and destination pole.Īfter these three trivial steps, if we run through the algorithm we will notice that after every three moves, the destination pole is in a state that it can accept a new disk. Yes ,the Tower of Hanoi problem can be solved using iteration in C. We can think of them by starting the trivial cases when i = 1, 2 and 3.įor i = 1, since we have appropriately decided the sense of movement in step 2 of algorithm, we can safely make a legal movement b/w source and destination.įor i = 2, since the auxiliary pole is empty we can shift the disk to it and have a legal movement b/w source and auxiliary pole.įor i = 3, we need to make space for the remaining disks of source so that they could be shifted to the destination. Why the sub cases a, b, c of step 3 of the algorithm work? When the top disk of one pole is smaller than the other we move the smaller of two disks to the pole with larger disk. When one of the two poles is empty we must move the disk from non empty pole to the empty pole. of disks to be transferred: 3 Non-Recursive Move top disk from needle A to needle C Move top disk from needle A to needle B Move top disk from needle C to needle B Move top disk from needle A to needle C Move top disk from needle B to needle A Move top disk. no larger disk should be placed on smaller disk and we must move only the top disk at a time. printf(' There's nothing to move.') Enter the no. The legal movement must respect the constraints of the TOH problem i.e. Legal movement of top disk b/w auxiliary pole and destination pole. ![]() Legal movement of top disk b/w source pole and auxiliary pole. Legal movement of top disk b/w source pole and destination pole. for i = 1 to number of moves calculate in step 1: (This is to ensure that moves are in clockwise for even disks and anticlockwise for odd disks)ģ. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: 1) Only one disk can be moved at a time. If numDisks is even then interchange the destination pole with the auxiliary pole. Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. ![]() With the help of above two observations we can devise the algorithm as: TowerOfHanoi(source, destination, auxiliary, numDisks)ġ. Then for the even number of disks the movement of disks will start in clockwise direction and if the number of disks is odd then the movement will start in anticlockwise direction. This can be evaluated by the recurrence of the recursive solution. of moves required are $2^n - 1$ where n is the number of disks. The iterative solution can be figured out analyzing the recursive solution. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |