![]() ![]() Knuth and Oren Patashnik: Concrete Mathematics: A Foundation for Computer Science (2nd ed.): $\S 1.1$ 1986: David Wells: Curious and Interesting Numbers .The world may well have (figuratively) crumbled to dust long before that time. It is clear that steps $1$ and $3$ above each take $T_ - 1$ moves: $(1): \quad$ Move the tower of $n - 1$ disks from off the top of the $n$th disk onto another of the pegs $(2): \quad$ Move the $n$th disk to the destination peg $(3): \quad$ Move the tower of $n - 1$ disks from where it was put temporarily onto the top of the $n$th disk. Now, we note that in order to move a tower of $n$ disks, we need to do the following: ![]() Let $T_n$ be the number of moves needed to transfer $n$ disks from one peg to another. Variant $(1): \quad$ Only one disk can be moved at a time $(2): \quad$ No disk may be placed on a peg with a smaller disk beneath it $(3): \quad$ The disks must all be moved from the peg $1$ to peg $3$ $(4): \quad$ A move consists of transferring a disk from the peg $1$ to peg $2$, or back, or from peg $2$ to peg $3$, or back $(5): \quad$ No disk can cross over peg $2$ if it contains a smaller disk.įor a tower of $n$ disks, it takes $2^n - 1$ moves. How many moves are needed to move all the disks onto a different peg? ![]() $(1): \quad$ Only one disk can be moved at a time $(2): \quad$ No disk may be placed on a peg with a smaller disk beneath it. The object of the exercise is to move the disks onto a different peg, obeying the rules: There is a tower of $n$ disks, stacked in decreasing size on one of $3$ pegs. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |