We’ll get to strictHanoi() after we’ve sorted out simpleHanoi(). The second, stricter variant allows us to move disks only to a neighboring peg. Our first variation - let’s call it simpleHanoi() - will allow us to jump from peg A to peg C, even if we couldn’t land on peg B due to there being a smaller disk on B than the one we are moving. Clarke’s short story The Nine Billion Names of God.)īefore we get started, we need to be more explicit about the rules for moving disks. It’s a good thing they didn’t use a computer to avoid any mistakes! (A good case for keeping monks away from computers is made in Arthur C. Which means the world will be around for quite a while yet, at least if the disks have to be physically manipulated. Now, executing the minimum number of moves for 64 disks, at one move per second, would take something like 585 billion years. Upon completing the task, their reward would be the end of the world. Lucas fancifully set the task to a group of monks in a temple, where they manually move a stack of 64 golden disks from A to C. A larger disk can never be placed on top of a smaller disk. ![]() You have to move the disks from A to C, with the order of stacking preserved. Assume n number of disks are stacked by decreasing size on peg A. The problem was first posed by Édouard Lucas in 1883. Then we’ll spend some time understanding how that solution actually works - as we’ll see, getting the answer and knowing how it works can be two very different things.įirst, a little history. So for this puzzle we’ll be deriving the answer from first principles, which is more beneficial (and perhaps easier) than reverse-engineering the solution. ![]() The real learning, as I’ve tried to emphasize in every section of this guide to recursion, comes from an ability to work through the process by which we come to the solution. “The code is so short - how hard could it be?” are common Famous Last Words people say when they start digging into the puzzle. In this guide I’ve gone through dozens of algorithms, and I think the Tower problem is still very difficult to understand, partly because the problem and the solution are both easily stated. While I’ve studied recursion for only a brief time, I’ve become more and more surprised that many tutorials on the subject include this as only the third or fourth example (the other two are usually factorials and Fibonacci sequence). ![]() Finally, we lay siege to the Tower of Hanoi.
0 Comments
Leave a Reply. |