TD02

Some interesting problems

1. The Tower of Hanoi: We have three rods and n disks of different sizes. The puzzle begins with all the disks stacked on one rod of decreasing size, with the smallest one on the top. The objective of the puzzle is to move the entire stack to the last rod, with respect to the following rules:
   • Only one disk can be moved at each move.
   • Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
   • No disk can be placed on top of a smaller disk.

   How many moves do you need if n = 1, 2, 3 or 4? Write a function hanoi(n) that returns the minimal number of moves required to solve a Tower of Hanoi with n disks.