汉诺塔问题

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。梵天创造世界的时候做了三根柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。（以上介绍来自百度百科）

这是一个五层的汉诺塔示意gif图：

hanoi.gif

假如要让我们用程序模拟这个过程。应该怎样去做呢?

首先可以把每一个柱子具象化为数组，三个柱子就是三个数组。其实具象化为栈比较好， 因为柱子只能从最上端取出，也只能从最上端放入，但是我们主要讨论汉诺塔，不再做栈的实现，相应的，我们对数组进行规定，只进行pop和push操作，这样我们也能得到类似栈的效果。(实际上在JS中，如果不借助node-gyp用C++实现栈结构，用JS数组实现栈结构也是最简单的)

首先我们定义三根柱子:

// JavaScript
let a = []            // 假设a为源柱
let b = []            // 中间柱
let c = []            // 假设c为目标柱
let count = 0         // count用于计算总共移动的次数

# Python
a = []                # 假设a为源柱
b = []                # 中间柱
c = []                # 假设c为目标柱
count = 0             # count用于计算总共移动的次数

1.仅有一个圆盘需要被移动的情况

现在我们假设 a数组中存放着一个数 a = [1], 那么要把 a中的 一个大小为1的盘子移动到 c中，我们只需要直接做这个移动操作： a → c ，即一步即可完成汉诺塔， 进行移动后三个数组分别为:

• a == [ ]
• b == [ ]
• c == [1]

相应的, 我们需要定义“移动”圆盘的代码实现：

// JavaScript
/**
 * @function 在两根柱子间移动一片圆盘
 * @param {需要移动的源数组} source 
 * @param {要移动到的目标数组} target 
 */
const move = (source, target) => {
  target.push(source.pop())             // 用目标数组push 源数组的pop值来抽象移动
  count ++                              // 每移动一次总移动次数count 自加一次
}

# Python
def move(source: list, target: list) -> None:    
    global count                      # 引用全局的count变量
    target.append(source.pop())       # 进行移动
    count = count + 1                 # 移动次数+1

则我们第一步的函数可以简单定义:

// JavaScript
const once = (one ,two, three) => {
  move(one, three)
}
once (a, b, c)  //直接调用

# Python
def once(one: list, two: list, three: list) -> None:
    move(one, three)
once(a, b, c)  # 直接调用

2.假设两层的汉诺塔要怎么做呢？

// JavaScript
const twice = (one, two, three) => {
  once(one, three, two)    // 首先将第一个最小的圆盘移动到第二根柱子
  move(one, three)          // 将剩下的最大的圆盘移动到第三根柱子
  once(two, one, three)   // 将第一次移动的圆盘移动到第三根柱子上
}

# Python
def twice(one: list, two: list, three: list) -> None:
    once(one, three, two)
    move(one, three)
    once(two, one, three)
  

两层的情况我们必须考虑的是，要保证大圆盘在小圆盘下，我们要借助一个中间柱子来暂时存放小的圆盘，然后移动大圆盘到目标的柱子，再将小圆盘移动到目标柱。

3.三层的情况

// JavaScript
const third = (one, two, three) => {
  twice(one, three, two)
  move(one, three)
  twice(two, one, three)
}

# Python
def third(one: list, two: list, three: list) -> None: 
    twice(one, three, two)
    move(one, three)
    twice(two, one, three)

到第三层，我们可以理解为，先将上面的两层移动到第二根柱子，这样我们才能把最大的底座移动到第三根柱子上，然后再将第二根柱子上的两块圆盘， 借助第一根柱子（此时把它看做中转柱）移动到第三根柱子。

4.四层的情况

// JavaScript
const fourth = (one, two, three) => {
  third(one, three, two)
  move(one, three) 
  third(two, one, three)
}

# Python
def fourth(one: list, two: list, three: list) -> None:
    third(one, three, two)
    move(one, three)
    third(two, one, three)

同理，我们的需要是，先把最下面的最大的圆盘移动到目标柱，为此，我们需要把上面的三层圆盘先移动到第二根柱子上，怎么移动呢？将第三根柱子暂时当做中间柱，将第二根柱子看做目标柱，其实就是调用第三次的方法！然后将最大的圆盘移动到第三根柱子上，接着把第二根柱子上的圆盘借助第一根柱子做中转柱 移动到第三根柱子上。

5.规律

发现规律了吗?其实我们几步都在做同样的事情!
那么就天然符合递归!

// JavaScript
const hanoi = (n, src, sav, tar) => {
  if (n == 1) {
    move(src, tar)
  } else {
    hanoi(n - 1, src, tar, sav)
    move(src, tar)
    hanoi(n - 1, sav, src, tar)
  }
}

# Python
def hanoi(n: int, src: list, sav: list, tar: list) -> None:
    if n == 1:
        move(src, tar)
    else:
        hanoi(n - 1, src, tar, sav)
        move(src, tar)
        hanoi(n - 1, sav, src, tar)

n用作递归的结束条件，其实n表示的就是问题规模，可以看到，每一次我们执行完hanoi，问题的规模都会缩小一次!
调用方法:

// 给a柱子添加圆盘，由大到小排列
for (let i = 4; i >= 0; i--) {
  a.push(i)
}

hanoi(a.length, a, b, c)  // 调用

# 给a柱子添加圆盘，由大到小排列
for index in reversed(range(0, 4)):
    a.append(index)

hanoi(len(a), a, b, c)