汉诺塔问题

文章目录

汉诺塔问题
汉诺塔是什么？
一、怎么解决汉诺塔问题
二、解题步骤
总结

汉诺塔是什么？

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

在这里插入图片描述

提示：以下是本篇文章正文内容，下面案例可供参考

一、怎么解决汉诺塔问题

1.1 操作规则

首先得知道汉诺塔怎么移动的，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
汉诺塔是一个经典递归问题，所以我们得先了解函数递归

1.2 函数递归

递归的两个必要条件

存在限制条件，当满足这个限制条件的时候，递归便不再继续
每次递归调用之后越来越接近这个限制条件

   public void recursion(参数0) {
    if (终止条件) {
        return;
    }
    recursion(参数1);
}

例题(斐波那契数列）

总所周知斐波那契数列是从第三个起的数等于前面两数之和。

Fib（n）=Fib(n - 1) + Fib(n - 2);

int Fib(int n)
{
	if(n==0)return 0;
	if (n <= 2)
	return 1;
	else 
	return Fib(n - 1) + Fib(n - 2);
}

//法二
//由于第一个代码在进行比较大的数据，会有大量重复计算，所以减少了计算

int fib(int n) {
	int a = 1, b = 1, c = 1;
	while (n > 2) {
		c = a + b;
		a = b;		
		b = c;
		n--
			}
	return c;
}

二、解题步骤

2.1 代码如下（示例）：

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>

void hanoi(int n, char a, char b, char c) {
	if (n == 1) {
		printf("%c-->%c\n", a, c);//把最底层的盘子移到c
	}
	else {
		hanoi(n - 1, a, c, b);//将n-1个盘子进过c柱移到b柱
		printf("%c-->%c\n", a, c);//把最底层的盘子移到c
		hanoi(n - 1, b, a, c); //将n - 1个盘子进过b柱移到c柱
	}
}

int main() {
	int m;
	scanf("%d", &m);  
	hanoi(m, 'A', 'B', 'C');
	return 0;
}

2.2 图解

首先来看看那运行结果

在这里插入图片描述
当有3个盘子的时候总共运行了7次
当有4个盘子的时候总共运行了15次
当有4个盘子的时候总共运行了21次

不难发现

2^n-1

也就说汉诺塔是有规律的，有规律就有机会使用递归。
在回顾汉诺塔的操作方式，总是先把n-1经过c柱到b柱(a->c->b)，然后让最后一个移动到c柱(a->c)，再把b柱的n-1盘子经过a柱到c柱（b->a->c）

在这里插入图片描述

2.3 调试

当第一次进行调试进入函数，会进入hanoi(2, a, c, b)，然后进入函数hanoi(1, a, c, b)，再进入n=1时就会打印第一步先把a柱最上面一个直接移到c柱，结束后再回到n=2的函数继续执行移动把第二个先移到c柱。
在这里插入图片描述
hanoi(1, b, a, c)移动后再往下走就是移动第二个盘子，再把它移动b柱