Towers of Hanoi

作者 QIFAN 日期 2016-10-11
Towers of Hanoi

Cracking the Code Interview 8.6

In the classic problem of the Towers of Hanoi, you have 3 towers and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (i.e., each disk sits on top of an even larger one). You have the following
constraints:
(1) Only one disk can be moved at a time.
(2) A disk is slid off the top of one tower onto another tower.
(3) A disk cannot be placed on top of a smaller disk.
Write a program to move the disks from the first tower to the last using Stacks.

模拟移金字塔。可以将三个塔看成三个stack,其中的disk看成数字,也就是在整个移动过程中,大的数字始终要在小数字的下面。

思路

从简单的例子想起。

  • Case 1: stack 1里只有一个数字
    只需将1从stack 1(origin)移动到stack 3(destination)

  • Case 2:stack 1里有1,2
    先将1从stack 1(origin)移到到stack 2(buffer),将2从stack 1(origin)移动到stack 3(destination), 再将1从stack 2(buffer)移动到stack 3

  • Case 3:stack 1里有1,2,3
    先将1,2从stack 1(origin)移动到stack 2(buffer)(和case 2)的情况类似,将3移动到stack 3(destination),再将1,2从stack 2(buffer)移动到stack 3(destination)

  • Case 4:stack 1里有1,2,3,4
    先将1,2,3从stack 1(origin)移动到stack 2(buffer)(和case 2)的情况类似,将4移动到stack 3(destination),再将1,2,3从stack 2(buffer)移动到stack 3(destination)

N个数字移动的基本思想可以概括为:先将n-1个数字从stack 1(origin)移到到stack 2(buffer),将数字n从stack 1(origin)移动到stack 3(destination), 再将前n-1个数字从stack 2(buffer)移动到stack 3

Solution

使用递归,这里只写伪代码

move(int n, Stack origin, Stack destination, Stack buffer) {
// base case
if (n <= 0) return;
// move top n-1 from origin to buffer
move(n-1, Stack origin, buffer, destination);
// move bottom one from origin to destination
moveBottom(origin, destination);
// move top n-1 from buffer to destination
move(n-1, buffer, destination, origin);
}