汉诺塔

问题描述

有一个梵塔叫汉诺塔，汉诺塔上有三根柱子A、B和C，柱子A上有若干个圆盘，所有圆盘大小不等，且小的在上大的在下，如下图所示：

将柱子A上的所有圆盘借助柱子B移动到柱子C上，移动的过程中每次只能移动一个圆盘，移动后仍然是小的在上大的在下，如下图所示：

求所有圆盘的移动过程。

设计思路

当柱子A有1个圆盘时，只需要将圆盘从柱子A移动到柱子C。当柱子A有2个圆盘时，先将柱子A上面的圆盘从柱子A移动到柱子B，再将柱子A下面的圆盘从柱子A移动到柱子C，最后将柱子B的圆盘从柱子B移动到柱子C。

当柱子A有3个圆盘时，先将柱子A上面的两个圆盘从柱子A借助柱子C移动到柱子B，然后将柱子A最下面的圆盘从柱子A移动到柱子C，最后将柱子B的两个圆盘从柱子B借助柱子A移动到柱子C。

一般地，当柱子A有n个圆盘时，从上到下依次编号为1, 2, 3, ……, n，先将柱子A上面编号为1至n - 1的圆盘从柱子A借助柱子C移动到柱子B，然后将柱子A最下面编号为n的圆盘从柱子A 移动到柱子C，最后将柱子B的n - 1个圆盘从柱子B借助柱子A移动到柱子C。

所求的问题是：将柱子A的n个圆盘借助柱子B移动到柱子C。结合上面的一般性步骤，很容易想到使用递归。假设递归函数playHanoiTower(n, A, B, C)用于将n个圆盘从柱子A借助柱子B 移动到柱子C，函数move(n, A, C)用于将编号为n的圆盘从柱子A移动到柱子C，则上面的一般性步骤可以表示为：

当n = 1时，调用move(1, A, C)，将圆盘从柱子A移动到柱子C。
当n > 1时，

1) 调用playHanoiTower(n - 1, A, C, B)，将柱子A上面编号为1至n - 1的圆盘从柱子A借助柱子C移动到柱子B；

2) 调用move(n, A, C)，将柱子A上编号为n的圆盘从柱子A移动到柱子C；

3) 调用playHanoiTower(n - 1, B, A, C)，将柱子B的n - 1个圆盘从柱子B借助柱子A移动到柱子C。

Swift 3.0 代码实现

var  count = 1

// 将编号为n的圆盘从柱子from移动到柱子to
func move(n: Int, from: Character, to: Character) {
    print("第\(count)步：移动\(n)号圆盘，\(from)--->\(to)")
}

// 将n个圆盘从柱子from借助柱子dependOn移动到柱子to
func playHanoiTower(n: Int, from: Character, dependOn: Character, to: Character) {
    if n == 1 {
        move(n: 1, from: from, to: to)
    } else {
        playHanoiTower(n: n - 1, from: from, dependOn: to, to: dependOn)
        
        move(n: n, from: from, to: to)
        
        playHanoiTower(n: n - 1, from: dependOn, dependOn: from, to: to)
    }
}

playHanoiTower(n: 5, from: Character("A"), dependOn: Character("B"), to: Character("C"))

dxxs's Blog

汉诺塔问题

汉诺塔

问题描述

设计思路

Swift 3.0 代码实现

算法理解