算法

汉诺塔真是学递归的经典例子啊~这里再来一个 Ruby 版本的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

@step_nbr = 0

def hanoi(height, from_pole, to_pole, with_pole)
  if height >= 1
    hanoi(height - 1, from_pole, with_pole, to_pole)
    @step_nbr += 1
    puts "#{@step_nbr}: move disk from #{from_pole} to #{to_pole}"
    hanoi(height - 1, with_pole, from_pole, to_pole)
  end
end

puts 'Please enter the height of the tower:'
height = gets
hanoi(height.to_i, 'a', 'b', 'c')

汉诺塔，数据结构和算法里老生常谈的东西了，可惜我至今没有彻底透彻的搞清楚它的递归细节。现在利用学习 Go 语言的机会，再重新理清一下它的实现和递归的本质。

先上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

package main

import (
	"fmt"
	"os"
	"strconv"
)

var step int

func main () {
	var n int
	var err error

	if (len(os.Args) == 1) {
		n = 3
	} else {
		n, err = strconv.Atoi(os.Args[1])
		if (err != nil) {
			fmt.Fprintf(os.Stderr, "failed to get n.\n%s\n", err.Error())
			return
		}
	}
	step = 0
	hanoi(n, "A", "B", "C")
}

func hanoi (n int, x string, y string, z string) {
	if (n == 0) {
		return
	}

	hanoi(n - 1, x, z, y)
	step++
	fmt.Printf("%d: %s -> %s\n", step, x, y)
	hanoi(n - 1, z, y, x)
}

我现在理解的递归的本质就是用把 n 级的问题用 n-1 级定义出来，找出所谓的递归结构，进而找出递推公式。对于汉诺塔问题，就是要抽象出以下4个变量：n, x, y, z。n 代表问题规模，即 n 层盘子，x, y, z 分别表示源柱，目标柱和过渡柱。函数内部就是聚焦于这4个变量的操作：

1. 把 n-1 个盘子从源柱经过目标柱的过渡，挪到过渡柱（从而使源柱上只有第 n 个盘子）
2. 把第 n 个盘子从源柱上挪到目标柱上（程序输出这个单步的操作）
3. 把过渡柱上的 n-1 个盘子经过源柱挪到目标柱上

这样通过递归，n 的规模不断减小，直到 n == 0，同类问题的最小规模情况，对于这个最小规模情况，我们知道确切的答案，就是不做任何操作（直接 return），进而触发了递归的反向求值连锁反应。所以，递归其实就是这样一个过程：

• 第 n 层答案 = 第 n-1 层答案 + 固定已知计算
• 第 n-1 层答案 = 第 n-2 层答案 + 固定已知计算
• ……
• 第 0或1 层答案 = 一个确定已知答案

前面每层的答案都等待着下一层的答案再加上一个已知计算，一直到第1层或者第0层有一个已知答案，进而第2层因为第1层有了答案而有了答案，第3层因为第2层有了答案而有了答案……一直到第 n 层因为第 n-1 层有了答案而有了答案，于是整个问题有了解。