图解汉诺塔问题（递归求解）

我会带着你远行 2022-11-30 12:47 284阅读 0赞

> 汉诺塔：汉诺塔(Tower of Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

下面来对汉诺塔问题进行解释和建立模型  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]  
这是示意图，a是起始柱，c是目标柱，b起到中转作用

在进行转移操作时，都必须确保大盘在小盘下面，且每次只能移动一个圆盘，最终c柱上有所有的盘子且也是从上到下按从小到大的顺序。

下面我用图来描述64个盘子的转移流程  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 2]  
这里我们先把上方的63个盘子看成整体，这下就等于只有两个盘子，自然很容易了，我们只要完成两个盘子的转移就行了，好了现在我们先不管第64个盘子，假设a柱只有63个盘子，与之前一样的解决方式，前62个盘子先完成移动目标。

嗯，就这样一步步向前找到可以直接移动的盘子，62,61,60，…，2,1，最终，最上方的盘子是可以直接移动到c柱的，那就好办了，我们的2号盘也能完成向c柱的转移，这时c柱上时已经转移成功的2个盘，于是3号盘也可以了，一直到第64号盘。

package main
    
    func move(id int, from string, to string)  {
        
    	print("num = ", id ," : " , from , "->", to, "\n")
    }
    
    func hanrou(n int, a, b, c string){
        
    	if(n == 0){
        
    		return
    	}else{
        
    		hanrou(n - 1, a, c, b)
    		move(n, a, c)
    		hanrou(n - 1, b, a, c)
    	}
    }
    
    func main() {
        
    	hanrou(3, "a", "b", "c")
    }

如果真要解释代码的每一步执行过程，那会很乱，两层递归，最后自己也会被绕的晕头转向，这个时候只要理解递归最终的解决的问题是什么就行了，中间的事交给程序，递归可以很绕也可以很直接，我们按照最直接的理解就行了。

最后关于递归算法，这中解决问题的方法也只有计算机才喜欢，我们虽然看着代码很简单，但真要深入理解也是很费脑细胞的，不过递归确实有中数学上的简洁美和逻辑美。

可视化过程

package main
    
    import (
    	"fmt"
    )
    
    // 柱子高度
    const N int = 10
    // 三根柱子的取值
    const A string = "A"
    const B string = "B"
    const C string = "C"
    
    
    var  arr [3][N]int =[3][N]int{
        {
        0,0,0,0,0,0,0,0,0},{
        0,0,0,0,0,0,0,0,0},{
        0,0,0,0,0,0,0,0,0}}
    
    func show()  {
        
    	fmt.Printf("%5s%5s%5s\n", "A", "B", "C")
    	for i := 0; i < N ;  i++ {
        
    		for j := 0; j < 3 ; j++ {
        
    			fmt.Printf("%5d", arr[j][i])
    		}
    		fmt.Println()
    	}
    
    	fmt.Println("---------------------")
    }
    
    /*
    * 初始化时有多少个盘子在A上
    */
    func newHanrouta(n int) {
        
    	for i := 0; i < n ; i++ {
        
    		arr[0][N - 1 - i] = n - i
    	}
    }
    
    // 将x柱子的最上面的那个移动到Y柱子上
    func move (X,Y string){
        
    	// 将X/Y/Z转换为0，1，2。表示arr[0], arr[1], arr[2]
    	// 已经直到 X, Y 仅仅可以取值 A, B, C
    	m := int(X[0]) - 'A'
    	n := int(Y[0]) - 'A'
    
    	// 找到X柱子上第一个不为0的数字， 结束循环
    	imove := -1
    	for i := 0; i< N ; i++ {
        
    		if arr[m][i] != 0 {
        
    			imove = i
    			break
    		}
    	}
    
    	if imove == -1 {
        
    		fmt.Println(X , "柱上已经没有盘子了")
    		return
    	}
    
    
    	// 从最下面开始数，直到找到第一个0, 结束循环
    	jmove := -1
    	for i := N - 1; i > -1 ; i-- {
        
    		if arr[n][i] == 0 {
        
    			jmove = i
    			break
    		}
    	}
    
    
    
    	if jmove == -1 {
        
    		fmt.Println(Y , "柱上已经没有位置来存放盘子了")
    		return
    	}
    
    	// imove与jmove交换位置
    	arr[m][imove], arr[n][jmove] = arr[n][jmove], arr[m][imove]
    }
    
    func hanrou(n int, A, B, C string)  {
        
    	if (n <= 0){
        
    		return
    	}
    
    	if n == 1 {
        
    		move(A, C)
    		show()
    	}else{
        
    		hanrou(n-1, A, C, B)
    		move(A, C)
    		show()
    		hanrou(n-1, B, A, C)
    	}
    }
    
    func main() {
        
    	newHanrouta(9)
    	show()
    	hanrou(9, A, B ,C)
    	show()
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/b43ecd6ca91d44a4bb071ecdf18daad1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/6e3c7a49d995475696c3898b86b214af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/9778bf7a5f204116b6600afd9ea0debb.png