汉诺塔问题

2020-11-12 00:00:00 1.3k 字 5 分钟

汉诺塔问题介绍

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

image-20201112130124165

问题分析

这里我们只考虑最常用的解法，递归方法，把所有的圆盘n分为两个部分：

  • 上层的n-1个圆盘
  • 最下层的第n个圆盘

解题步骤：

1、

​ 把n-1个圆盘，从a移动到b

​ 把第n个圆盘，从a移动到c

2、

​ 把n-1个圆盘，从b移动到c

n-1个圆盘的移动又会用相同的解题步骤来解决，直到一个圆盘为止

程序实现

  • c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
#include<string.h>


void hanno(int n,char a[],char b[],char c[]){

    if(n == 1){
        printf("圆盘从%s移动到%s\n",a,c);
    }
    else{
        hanno(n - 1,a,c,b);
        printf("圆盘从%s移动到%s\n",a,c);
        hanno(n - 1,b,a,c);
    }
}

int main(){

    hanno(3,"a","b","c");
    return 0;
}

结果如下：

image-20201113110615041

  • java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package com.smithbee.day07;

public class HannoTower {
    public static void main(String[] args){
        hannoo(3,"a","b","c");
    }
    public static void hannoo(int n,String a,String b,String c){
        if(n == 1){
            System.out.println(a + "移动到" + c);//问题的最基础的解决方式，也是递归算法结束的条件
        }else{
            hannoo(n - 1,a,c,b);//步骤一，将n-1个圆盘从a移动到b
            System.out.println(a + "移动到" + c);//步骤一，将第n个圆盘从a移动到c
            hannoo(n - 1,b,a,c);//步骤二，将n-1个圆盘从b移动到c
        }
    }
}

结果如下：

image-20201112135922522

  • python 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#汉诺塔问题

def hanno(n,a,b,c):
   
    if n == 1:
        
        print('圆盘从{0}移动到{1}'.format(a,c))
    else:
        hanno(n - 1,a,c,b)
        
        print('圆盘从{0}移动到{1}'.format(a,c))
        hanno(n - 1,b,a,c)
        
hanno(3,'a','b','c')

结果如下：

image-20201112140003370

  • c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;

void hanno(int n,string a,string b,string c);

int main(){

    hanno(3,"a","b","c");
    return 0;
}
void hanno(int n,string a,string b,string c){

    if(n == 1){
        cout << "圆盘从" << a << "移动到" << c <<endl;
    }
    else{
        hanno(n - 1,a,c,b);
        cout << "圆盘从" << a << "移动到" << c <<endl;
        hanno(n - 1,b,a,c);
    }

}

结果如下：

image-20201112141556314

  • go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package main
import "fmt"

func hanno(n int,a string,b string,c string) int {

	if n == 1 {
		fmt.Printf("圆盘从%s移动到%s\n",a,c)
	} else {
		hanno(n - 1,a,c,b)
		fmt.Printf("圆盘从%s移动到%s\n",a,c)
		hanno(n - 1,b,a,c)
	}
	return 0
}

func main() {
	hanno(3,"a","b","c")
}

结果如下：

image-20201112144604382

递归

  • 递归算法的四条基本准则

1.基准情形。必须有某些基准情形，它无需递归就能解出。
2.不断推进。对于那些需要递归求解的情形，每一次递归调用都必须要使求解的状况朝接近基准情形的方向推进。
3.设计法则。假设所有的递归调用都能运行。
4.合成效益法则。在求解同一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作
——-摘自《数据结构与算法分析（机械工业出版社 Mark Allen Weiss著）》

  • 递归算法的理解

1.在求f(n, other variables)的时候，你就默认f(n -1, other variables)已经被求出来了——至于怎么求的，这个是计算机通过回溯求出来的。

PS:这里用到了一种叫做栈(stack)的先进后出的数据结构，所以递归输出的答案一般是自下而上的。

2.递归和二叉树是密切相关的。可以尝试通过二叉树的数据结构来理解递归是如何将一个问题拆分成若干子问题，求解再回溯的。这里可以参考以下快速排序(QuickSort)的过程（快速排序的核心思想是分治，分治即分而治之，通过递归将原问题分解为若干容易求解的子问题，再通过递归将这些子问题联系起来并向二叉树的上层回溯，最终求解出原问题）

  • 递归算法的注意

1.递归的结束条件（不写会死循环，TLE）

2.递归最后一层和其他有关系的层的关系怎样用非递归函数来表达

比如：斐波纳契亚数列，（1）当n==1和n==2的时候f(n)=1，这就是递归的终止条件。给了终止条件，计算机才能进行求解子问题并回溯，最终求出f(n)