汉诺塔问题详解--递归实现_汉诺塔用递归工具计算算法 han-程序员宅基地

汉诺塔问题详解--递归实现

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

思考：
有三根柱子（A，B，C）。A柱子上面套着n个圆盘。这些圆盘大小各异，按从小到大的顺序自上而下摆放。

现在要把套在A柱上的n个圆盘全部移动到B柱上。并且移动圆盘时必须遵守下述规则：

一次只能移动柱子最上端的一个圆盘。
小圆盘上不能放大圆盘。
将一个圆盘从一根柱子移到另一根柱子，算是移动1次，那么，将n个圆盘全部从A移动到B至少需要移动几次呢？

首先：我们应该先从小汉诺塔入手。
一开始就考虑n个圆盘的话头脑会混乱，所以我们先缩小问题的规模，从3个圆盘开始思考。
即：暂时不考虑n个圆盘的问题，而是先找出3个圆盘的“3层汉诺塔”的解法。

经过尝试我们可以得到“3层汉诺塔”的解法，移动7次即可解决问题，即：

仔细观看这个移动过程，我们仿佛在做“重复且相似的事情”。之所以会有这种感觉是因为我们看到了一丝规律：
我们仔细看看图中①②③和⑤⑥⑦的移动过程：

①②③中，移动3次将2个圆盘从A柱移动到了C柱。
⑤⑥⑦中，移动3次将2个圆盘从C柱移动到了B柱。

再仔细看看移动2个圆盘的规律：

虽然移动的目的地不同，但是这两个行为动作却是非常相似的。而这种“移动2个圆盘”的动作不就是“2层汉诺塔”的解法吗。
用同样的思路我们可以进一步解决“5层汉诺塔”的问题，即：

首先，将4个圆盘从A柱移到C柱（解出4层）
然后，将（5个中）最大的圆盘从A柱移到B柱
最后，将4个圆盘从C柱移到B柱（解出4层）
“4层汉诺塔”，“3层汉诺塔”“2层汉诺塔”…也是用同样的解法。当然“1层汉诺塔”只需要移动一次圆盘就完成了。

通过这种方式我们可以总结出n层汉诺塔的解法：
我们用x,y,z来分别代表起点柱，目标柱，中转柱。注意：x,y,z并不具体代表A,B,C柱子，在不同情况下会不固定的对应A,B,C中的某一个。
解决n层汉诺塔的步骤，即：利用z柱将n个圆盘从x柱转移至y柱。
将n个圆盘从x柱，经由z柱中转，移到y柱时：

当n=0时：
* 不做任何操作
当n>0时：
* 首先，将n-1个圆盘从A柱移到C柱（解出n-1层）
* 然后，将（n个中）最大的圆盘从A柱移到B柱
* 最后，将n-1个圆盘从C柱移到B柱（解出n-1层）

由以上步骤可知：为了解出n层汉诺塔，要使用n-1层汉诺塔的解法。
那么，我们可以用H(n)表示解出n层汉诺塔所需的最少移动次数。
当n=0时，H(0)=0;
当n=1时，H(1)=1;
当n=2时，H(2)=H(1) + 1 + H(1) = 3;
当n=3时，H(3)=H(2) + 1 + H(2) = 7;
。
。
。
最终我们可以得到：

即：

这就是我们这个问题的递推公式。
当然，仔细的朋友已经发现：
0 = 1 - 1；
1 = 2 - 1；
3 = 4 - 1；
7 = 8 - 1；
。。。
即：H(n) = 2^n - 1;

前面的思路其实已经相当于伪代码了。既然我们的思路已经这么清晰了，那我们来尝试写写代码吧：

#include <iostream>
#include <cstdio>
using namespace std;
int hanoi(int n, char x, char y, char z);
int num = 0;
int main()
{
    
	int n;
	printf("请输入汉诺塔的层数：");
	cin >> n;
	hanoi(n, 'A', 'B', 'C');
	printf("共移动了 %d 次。\n", num);
	return 0;
}
// n表示要将多少个"圆盘"从起始柱子A移动至目标柱子B
// x表示起始柱子,y表示目标柱子,z表示过渡柱子
int hanoi(int n, char x, char y, char z)
{
    
	if (n == 0)
	{
    
	}
	else
	{
    
		hanoi(n - 1, x, z, y);// 递归处理,一开始的时候,先将n-1个盘子移至过渡柱z上
		printf("第%d步：  将 %d 号圆盘从 %c 移至 %c \n",num+1, n, x, y); // 然后再将最底下的大盘子直接移至目标柱子y
		num++;
		hanoi(n - 1, z, y, x); // 然后重复以上步骤,递归处理放在过渡柱z上的n-1个盘子,
							   // 这时x已经为空，所以x被当成过渡柱了
	}
	return 0;
}

假设我们算的是4层汉诺塔，运行结果如下：
在这里插入图片描述

本文链接：https://blog.csdn.net/qq_41879343/article/details/88671673

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

电子模块|压力传感器模块HX711---C51&&STM32驱动_单片机hx711驱动-程序员宅基地

文章浏览阅读2.2k次。HX711是一款专为高精度称重传感器而设计的24位A/D转换器芯片。与同类型其它芯片相比，该芯片集成了包括稳压电源、片内时钟振荡器等其它同类型芯片所需要的外围电路，具有集成度高、响应速度快、抗干扰性强等优点。降低了电子秤的整机成本，提高了整机的性能和可靠性。该芯片与后端MCU芯片的接口和编程非常简单，所有控制信号由管脚驱动，无需对芯片内部的寄存器编程。输入选择开关可任意选取通道A或通道B，与其内部的低噪声可编程放大器相连。_单片机hx711驱动

微信小程序 java springboot 57.高校毕业生就业信息的设计与实现（完整源码+数据库文件+万字文档+保姆级视频部署教程+配套环境）-程序员宅基地

文章浏览阅读263次，点赞6次，收藏5次。针对高校教师成果信息管理混乱，出错率高，信息安全性差，劳动强度大，费时费力等问题，采用高校毕业生就业信息可以有效管理，使信息管理能够更加科学和规范。高校毕业生就业信息使用 Java 语言进行编码，使用 Mysql 创建数据表保存本系统产生的数据。系统可以提供信息显示和相应服务，其管理高校毕业生就业信息信息，查看高校毕业生就业信息信息，管理高校毕业生就业信息。总之，高校毕业生就业信息集中管理信息，有着保密性强，效率高，存储空间大，成本低等诸多优点。数据库工具：Navicat；开发语言：Java；

ERROR: Failed to resolve: com.github.CymChad:BaseRecyclerViewAdapterHelper:2.9.46-程序员宅基地

文章浏览阅读1.6w次，点赞3次，收藏3次。今天弄一个demo 导入brvah 出现的错误，又去看了下教程是自己忘记添加jitpack仓库了_error: failed to resolve: com.github.cymchad:baserecyclerviewadapterhelper:2

对人脸检测和人脸识别的理解_人脸检测和人脸属性识别的意义-程序员宅基地

文章浏览阅读1.5k次。人脸检测是指对输入图像中判断是否存在人脸区域，并进一步确定人脸的位置、大小、姿态等信息。这些算法大致分为三种类别：基于肤色的检测方法、基于形状的检测方法、基于统计理论的检测方法。人脸识别技术是基于人的脸部特征，一个完整的人脸识别过程一般包括人脸检测和人脸识别两大部分。人脸识别就是将待识别的人脸与已知的人脸进行比较，得出相似程度的相关信息。人脸自动识别系统包括三个主要的环节：首先是图像预处_人脸检测和人脸属性识别的意义

ZipArchive(解压文件)-程序员宅基地

文章浏览阅读1.3k次。一、首先介绍minizip 的使用方法ziparchive是基于开源代码”MiniZip”的zip压缩与解压的Objective-C 的Class,使用起来非常的简单方法：从http://code.google.com/p/ziparchive/ 上下载ZipArchive.zip，解压后将代码加入工程中，并且把zlib库添加到工程中使用方法：1. 压缩:ZipArchive可..._zip archive是什么意思

【Python基础】HTTP知识扫盲_python 顺序输出 http 访问踪迹中 http get 请求中的资源对象序列及对应的大小序-程序员宅基地

文章浏览阅读142次。【Python基础】Http基础文章目录HTTP协议介绍1. HTTP 协议的介绍2. HTTP 协议的作用3. 浏览器访问web服务器的通信过程4. 小结URL介绍1. URL的概念2. URL的组成3. 小结HTTP协议通讯过程1. 谷歌浏览器开发者工具的使用2. 查看HTTP协议的通信过程3. 小结HTTP请求报文1. HTTP 请求报文介绍2. HTTP GET 请求报文分析3. HTTP POST 请求报文分析4. 小结HTTP响应报文1. HTTP响应报文分析2. HTTP 状态码介绍3. 小_python 顺序输出 http 访问踪迹中 http get 请求中的资源对象序列及对应的大小序