How do we go about solving this problem recursively? How would you goĪbout solving this problem at all? What is our base case? Let’s thinkĪbout this problem from the bottom up. You do not need fancy disksĪnd poles-a pile of books or pieces of paper will work.įigure 4.11: An Example Arrangement of Disks for the Tower of Hanoi This puzzle before, you should try it now. Rules specify, the disks on each peg are stacked so that smaller disksĪre always on top of the larger disks. Middle of a move from the first peg to the third. There is more to this puzzle than meets the eye.įigure 4.11 shows an example of a configuration of disks in the AtĪ rate of one move per second, that is \(584,942,417,355\) years! Clearly The number of moves required to correctly move a Would crumble into dust and the world would vanish.Īlthough the legend is interesting, you need not worry about the worldĮnding any time soon.
When they finished their work, the legend said, the temple The priests worked very efficiently, day and night, moving one diskĮvery second. They could only move one diskĪt a time, and they could never place a larger disk on top of a smaller TheirĪssignment was to transfer all 64 disks from one of the three poles toĪnother, with two important constraints.
Of time, the priests were given three poles and a stack of 64 goldĭisks, each disk a little smaller than the one beneath it. Temple where the puzzle was presented to young priests. He was inspired by a legend that tells of a Hindu The Tower of Hanoi puzzle was invented by the French mathematicianĮdouard Lucas in 1883.
0 kommentar(er)
