Tower of Hanoi

“汉诺塔”算法

Game towerofhanoi

题目:汉诺塔:三根杆子a、b、c,a杆由下到上按照从大到小的顺序穿了n个碟子,要求将n个碟子从a杆全部移动到c杆,移动结束后,碟子仍然按照由下到上从大到小的顺序排列,每次只能移动一个碟子,且小碟子不能放在大碟子下面。程序的每一行输出应该为:

moving disk x from pole i to pole j

其中,x是碟子的编号,从1开始一直到n,编号小的碟子是小碟子,i、j是杆的编号,为a、b或c

看了一些帖子,发现有一帖子说明特别简单易懂。于是引用了他博文的图片进行学习。

图中看出,只要抽象出主要的三步就能化繁为简。这刚好印证了递归的精华所在,如果不使用递归,是很难实现的。很多人说递归很难,其实递归是帮助我们简化问题。

  • A柱子把”共n-1”个盘借助C盘移动到B盘,完成一个大过程
  • A柱子把剩下的”第n”个盘直接移动到C盘,完成一个大过程
  • B柱子上的”共n-1”个盘借助A移动到C盘,又完成一个大过程

重复上面的大过程直至只剩下一个盘,于是就到了递归的结束条件。

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
38
39
40
41
42
43
44
45
package main

import (
"fmt"
"strconv"
)

func hanoi(i int, steps *int, debug bool) {
move(i, "A", "B", "C", steps, debug)
}

// a b c分别是柱子,i代表disk
func move(i int, a string, b string, c string, steps *int, debug bool) {
*steps++
// 每个n-1的整体的最底下的disk的移动,从a移动到c
if i == 1 {
if debug {fmt.Println("moving disk" + strconv.Itoa(i) + " from pole " + a + " to pole " + c)}
return
}
// 将共i-1个disks从a按移动到b
move(i - 1, a, c, b, steps, debug)
if debug {fmt.Println("moving disk" + strconv.Itoa(i) + " from pole " + a + " to pole " + c)}
// 将共i-1个disks从b按移动到c
move(i - 1, b, a, c, steps, debug)
}

func activity(numOfDisks int, debug bool){
steps := 0
hanoi(numOfDisks, &steps, debug)
fmt.Println(steps)
}

func main(){
// n个碟子,3个木桩,求最小移动次数,结果是等于2的n次方减1
debug := true
activity(1, debug)
fmt.Println()
activity(2, debug)
fmt.Println()
activity(3, debug)
fmt.Println()
activity(4, debug)
fmt.Println()
activity(5, debug)
}
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
Result

moving disk1 from pole A to pole C
1


moving disk1 from pole A to pole B
moving disk2 from pole A to pole C
moving disk1 from pole B to pole C
3


moving disk1 from pole A to pole C
moving disk2 from pole A to pole B
moving disk1 from pole C to pole B
moving disk3 from pole A to pole C
moving disk1 from pole B to pole A
moving disk2 from pole B to pole C
moving disk1 from pole A to pole C
7


moving disk1 from pole A to pole B
moving disk2 from pole A to pole C
moving disk1 from pole B to pole C
moving disk3 from pole A to pole B
moving disk1 from pole C to pole A
moving disk2 from pole C to pole B
moving disk1 from pole A to pole B
moving disk4 from pole A to pole C
moving disk1 from pole B to pole C
moving disk2 from pole B to pole A
moving disk1 from pole C to pole A
moving disk3 from pole B to pole C
moving disk1 from pole A to pole B
moving disk2 from pole A to pole C
moving disk1 from pole B to pole C
15


moving disk1 from pole A to pole C
moving disk2 from pole A to pole B
moving disk1 from pole C to pole B
moving disk3 from pole A to pole C
moving disk1 from pole B to pole A
moving disk2 from pole B to pole C
moving disk1 from pole A to pole C
moving disk4 from pole A to pole B
moving disk1 from pole C to pole B
moving disk2 from pole C to pole A
moving disk1 from pole B to pole A
moving disk3 from pole C to pole B
moving disk1 from pole A to pole C
moving disk2 from pole A to pole B
moving disk1 from pole C to pole B
moving disk5 from pole A to pole C
moving disk1 from pole B to pole A
moving disk2 from pole B to pole C
moving disk1 from pole A to pole C
moving disk3 from pole B to pole A
moving disk1 from pole C to pole B
moving disk2 from pole C to pole A
moving disk1 from pole B to pole A
moving disk4 from pole B to pole C
moving disk1 from pole A to pole C
moving disk2 from pole A to pole B
moving disk1 from pole C to pole B
moving disk3 from pole A to pole C
moving disk1 from pole B to pole A
moving disk2 from pole B to pole C
moving disk1 from pole A to pole C
31

Reference

“汉诺塔”算法-之通俗易懂,简单的原理-java编程

Thanks, mate.
0%