![]() We may compute T 1 = 2T 0 + 1 = 1, T 2 = 2T 1 + 1= 3, T 3 = 2T 2 + 1 = 7 and so on sequentially. Therefore the minimum number of moves needed to solve the puzzle with N disks equals T N-1 + 1 + T N-1 = 2T N-1 + 1 moves. One then needs exactly T N-1 more steps to finish the task. It takes just one move to move the biggest disk from Src to Dst. Since we are trying to use as few steps as possible, we may assume that that portion of the task took exactly T N-1 moves. Indeed, when the time comes to move the bottom disk, (N - 1) smaller disks will have been moved from Src to Aux in at least T N-1 moves. The inequality suggests that it might be possible to move N disks with fewer than 2T N-1 + 1 moves. The recursive solution above involves moving twice (N - 1) disks from one peg to another and making Now let us try to derive a general formula. A trained mathematician would also note that T 0 = 0. One can easily convince oneself that T 2 = 3 and T 1 = 1. From the previous section T 3 = 7 and T 4 = 15. Let T N be the minimum number of moves needed to solve the puzzle with N disks. Of course "Move" means moving the topmost disk. To me the sheer simplicity of the solution is breathtaking. The function is recursive in that it calls itself repeatedly with decreasing values of N until a terminating condition (in our case N = 0) has been met. This actually serves as the definition of the function Solve. Then the body of the function might look like
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |