And a little later...
and a bit later still...
"The Pyramid of Eternity" is better known as the Towers of Hanoi and it's often used as example of recursion, particularly in programming courses. Here's the Wikipedia explanation:
A key to solving this puzzle is to recognize that it can be solved by breaking the problem down into a collection of smaller problems and further breaking those problems down into even smaller problems until a solution is reached. For example:
- label the pegs A, B, C — these labels may move at different steps
- let n be the total number of discs
To move n discs from peg A to peg C:
- number the discs from 1 (smallest, topmost) to n (largest, bottommost)
- move n−1 discs from A to B. This leaves disc n alone on peg A
- move disc n from A to C
The above is a recursive algorithm: to carry out steps 1 and 3, apply the same algorithm again for n−1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for n = 1. This step, moving a single disc from peg A to peg B, is trivial.
- move n−1 discs from B to C so they sit on disc n
Post a Comment