11/6/2022 0 Comments Hanoi towers without recursion![]() ![]() So after every three moves, we can go with the other three moves and so on till we exhaust all our moves. 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. 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. no larger disk should be placed on smaller disk and we must move only the top disk at a time. The legal movement must respect the constraints of the TOH problem i.e. The next problem, however, is to solve the Hanoi puzzle without recursion. Legal movement of top disk b/w auxiliary pole and destination pole. For n 3, for instance, the solution is just: 1 to 3, 1 to 2, 3 to 2, 1 to 3, 2 to 1, 2 to 3, 1 to 3 where a to b indicates moving the top disk on peg a to peg b. The function should not take more than O (n) time (n number of Moves actually required to solve the problem) and O (1) extra space. Legal movement of top disk b/w source pole and auxiliary pole. Todays question is to write a Non-recursive function to solve problem of Tower Of Hanoi. A trivial solution to Double Decker is to simply treat it as a standard instance of the Tower of Hanoi with 2n disks and, thus, will need the usual 2 2n 1 4n 1 move. Legal movement of top disk b/w source pole and destination pole. But now I'd like to know how it could work without recursion but with stack instead. for i = 1 to number of moves calculate in step 1: I already got the Towers of Hanoi with recursion, it's also working without any problems. (This is to ensure that moves are in clockwise for even disks and anticlockwise for odd disks)ģ. If numDisks is even then interchange the destination pole with the auxiliary pole. 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 |