Leaky Cauldron
0%

汉诺塔问题

Posted on Edited on

题目

打印 n 层汉诺塔从最左边移动到最右边的全部过程

题解

假定三根柱子分别为 from , to 和 help , 该问题可划分为 3 个步骤

  1. 将 1~(n-1) 从 from 移动到 help 上
  2. 将 n 从 from 移动到 to 上
  3. 将 1~(n-1) 从 help 移动到 to 上

其中, 将 1~(n-1) 从 help 移动到 to 的过程又可分为多个子问题, 需不断调整三个柱子的角色.

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Hannoi {
    public static void hannoi(int n, String from, String to, String help) {
        if (n == 1) {
            System.out.println("move " + 1 + " from " + from + " to " + to);
        } else {
            hannoi(n - 1, from, help, to);
            System.out.println("move " + n + " from " + from + " to " + to);
            hannoi(n - 1, help, to, from);
        }
    }

    public static void main(String[] args) {
        int n = 3;
        hannoi(3, "left", "right", "mid");
    }
}

Python

1
2
3
4
5
6
7
def hannoi(n, source, target, assist):
    if n == 1:
        print('move 1 from ' + source + ' to ' + target)
    else:
        hannoi(n - 1, source, assist, target)
        print('move ' + str(n) + ' from ' + source + ' to ' + target)
        hannoi(n - 1, assist, target, source)