6-1 汉诺塔
汉诺(Hanoi)塔问题是一个经典的递归问题。
设有A、B、C三个塔座;开始时,在塔座A上有若干个圆盘,这些圆盘自下而上,由大到小地叠在一起。要求将塔座A上的圆盘移到塔座B上,并仍按同样顺序叠放。在移动过程中要求遵守如下规则:
- 每次只能移动一个圆盘;
- 任何时刻都不允许将较大的圆盘压在较小的圆盘之上;
- 在满足前两条规则的前提下,可将圆盘移至A、B、C中任何一塔座上。
- 例如,3个圆盘的初始状态如下

则移动过程如下:
A->B
A->C
B->C
A->B
C->A
C->B
A->B
要求实现一个递归函数,模拟输出n(1<=n<=8)个圆盘从塔座A借助塔座C移动到塔座B上的过程(用A->B表示将圆盘从A移到B,其他类似)。
函数接口定义:
void hanoi(int n, char from, char to, char by);
其中参数 n是圆盘数 、from是原来叠放圆盘的塔座 、to是最终叠放圆盘的塔座 、by是可借助的塔座。
裁判测试程序样例:
#include<iostream>
using namespace std;//将n个圆盘借助by从from移到to
void hanoi(int n, char from, char to, char by);//输入n,输出将原来在A上的n个圆盘借助C移动到B上的移动过程,控制到文件尾
int main() {int n, cnt=0;while(cin>>n) {cnt++;if (cnt>1) cout<<endl;hanoi(n, 'A', 'B', 'C');}return 0;
}
输入样例:
3
4
输出样例:
A->B
A->C
B->C
A->B
C->A
C->B
A->BA->C
A->B
C->B
A->C
B->A
B->C
A->C
A->B
C->B
C->A
B->A
C->B
A->C
A->B
C->B
## 答案:
void hanoi(int n, char from, char to, char by)
{if(n == 1){cout << from << "->" << to << endl;return;}else{hanoi(n-1,from,by,to);cout << from << "->" << to << endl;hanoi(n-1,by,to,from);}
}
## 思路:
汉诺塔问题是一个经典的递归问题,它描述了一种将一堆圆盘从一个塔座移动到另一个塔座的问题,同时需要遵守一些规则。问题的规则如下:
- 有三个塔座,通常称为A、B、C。
- 初始时,在塔座A上有若干个圆盘,这些圆盘自下而上,由大到小地叠在一起。
- 目标是将塔座A上的所有圆盘移动到塔座B上,并仍然按照相同的顺序叠放。
- 每次只能移动一个圆盘。
- 任何时刻都不允许将较大的圆盘放在较小的圆盘之上。
- 在满足前两条规则的前提下,可以将圆盘从A、B、C中的任何一个塔座移动到另一个塔座。
汉诺塔问题的目标是找到一种移动方案,将所有圆盘从起始塔座A移动到目标塔座B,中间可以借助辅助塔座C。这个问题可以通过递归算法来解决。
下面是一个详细解释递归函数 hanoi 的实现和工作原理:
void hanoi(int n, char from, char to, char by) {if (n == 1) {cout << from << "->" << to << endl;return;}// 递归步骤:// 1. 将前 n-1 个圆盘从起始塔座(from)经过目标塔座(by)移动到辅助塔座(by)上hanoi(n - 1, from, by, to);// 2. 将最大的圆盘从起始塔座(from)移动到目标塔座(to)上,并输出移动过程cout << from << "->" << to << endl;// 3. 将前 n-1 个圆盘从辅助塔座(by)经过起始塔座(from)移动到目标塔座(to)上hanoi(n - 1, by, to, from);
}
工作原理解释:
-
如果
n等于 1,表示只有一个圆盘需要移动,直接将它从from移动到to,并输出移动过程。 -
如果
n大于 1,表示有多个圆盘需要移动。递归的过程如下:-
第一步:将前
n-1个圆盘从起始塔座from经过目标塔座to移动到辅助塔座by上。这一步使用了递归调用,因为它也是一个汉诺塔问题,只不过规模减小了。 -
第二步:将最大的圆盘从起始塔座
from移动到目标塔座to上,并输出移动过程。这是实际的移动步骤。 -
第三步:将前
n-1个圆盘从辅助塔座by经过起始塔座from移动到目标塔座to上。这一步同样使用了递归调用。
-
这个递归过程会一直持续到只剩下一个圆盘需要移动,然后问题就会逐级返回,完成了所有圆盘的移动。
通过这种递归方法,你可以模拟汉诺塔问题的解决过程,并输出移动步骤。

相关文章:
6-1 汉诺塔
汉诺(Hanoi)塔问题是一个经典的递归问题。 设有A、B、C三个塔座;开始时,在塔座A上有若干个圆盘,这些圆盘自下而上,由大到小地叠在一起。要求将塔座A上的圆盘移到塔座B上,并仍按同样顺序叠放。在…...
Linux之initd管理系统(海思、ZYNQ、复旦微)添加密码登录验证
设置root用户密码:passwd命令设置密码,即修改/etc/passwd文件 一、串口提示输入用户名密码方法 修改 /etc/inittab 方法一: 增加: ::askfirst:-/bin/login 注释: #::respawn:/sbin/getty -L ttyS000 115200 vt…...
怎么更改代理ip,代理ip如何切换使用?
我们要如何使用HTTP代理,对它进行切换使用呢? 如果你购买了青果网络的HTTP代理,可以在文档这边获取使用方法: 可以在这里调试: 也可以在这里选择key提取。 如果有的朋友们想利用利用python,每隔30秒使用API…...
【C++从0到王者】第三十三站:AVL树
文章目录 前言一、AVL 树的概念二、AVL树的实现1. AVL树的结点定义2. AVL树的插入之插入部分3. AVL树的插入之平衡因子的改变4. AVL树的插入之左旋5. AVL树的左旋抽象图6.AVL树的右旋抽象图7. AVL树的双旋8. AVL树的右左双旋9. AVL树的右左双旋的本质10. AVL树的左右双旋11. AV…...
手机机型响应式设置2
window.screen.height:屏幕高度 window.innerHeight:视口高度(去除浏览器头尾的高度) document.body.clientHeight:内容高度 vh:网页视口高度的1/100 vw:网页视口宽度的1/100 vmaxÿ…...
uni-app 之 解决u-button始终居中问题
uView中u-button始终居中问题如何解决的简单方法? 1:给该元素margin-right: 0;可以达到向右靠齐; 2:给该元素的父元素设置float: right image.png <u-button style"width: 50px; margin-left: 0;" plain"t…...
Python日期处理库:掌握时间的艺术
💂 个人网站:【工具大全】【游戏大全】【神级源码资源网】🤟 前端学习课程:👉【28个案例趣学前端】【400个JS面试题】💅 寻找学习交流、摸鱼划水的小伙伴,请点击【摸鱼学习交流群】 日期和时间在计算机编程…...
JOSEF约瑟 智能电流继电器KWJL-20/L KWLD26 零序孔径45mm 柜内导轨式安装
KWJL-20智能电流继电器 零序互感器: KWLD80 KWLD45 KWLD26 KWJL-20 一、产品概述 KWJL-20系列智能剩余电流继电器(以下简称继电器)适用于交流电压至660V或更高的TN、TT、和IT系统,频率为50Hz。通过零序电流互感器检测出超过…...
NLP技术如何为搜索引擎赋能
目录 1. NLP关键词提取与匹配在搜索引擎中的应用1. 关键词提取例子 2. 关键词匹配例子 Python实现 2. NLP语义搜索在搜索引擎中的应用1. 语义搜索的定义例子 2. 语义搜索的重要性例子 Python/PyTorch实现 3. NLP个性化搜索建议在搜索引擎中的应用1. 个性化搜索建议的定义例子 2…...
演唱会没买到票?VR直播为你弥补遗憾
听说周杰伦开了演唱会?没买到票的人是不是有着大大的遗憾呢?很多时候大型活动、演唱会都会因为场地限制而导致很多人未能有缘得见,而且加上票价成本高,“黄牛票”事件频出,我们的钱包受不住啊!!…...
myabtis的缓存级别
文章目录 MyBatis缓存的区别是什么作用范围方面有哪些差异生命周期数据进行了存储缓存的优缺点 MyBatis缓存的区别是什么 MyBatis 提供了一级缓存和二级缓存,这两者的主要区别在于其作用范围和生命周期。 一级缓存:一级缓存是 SqlSession 级别的缓存。…...
gin框架再探
Gin框架介绍及使用 | 李文周的博客 (liwenzhou.com) lesson03_gin框架初识_哔哩哔哩_bilibili 1.路由引擎 //路由引擎 rgin.Default() 2.一些http请求方法 get post put delete等等 遇到什么路径,执行什么函数 r.GET("/hello",func{做你想做的事返回…...
经典算法-----约瑟夫问题(C语言)
目录 前言 故事背景 约瑟夫问题 环形链表解决 数组解决 前言 今天我们来玩一个有意思的题目,也就是约瑟夫问题,这个问题出自于欧洲中世纪的一个故事,下面我们就去通过编程的方式来解决这个有趣的问题,一起来看看吧!…...
代码随想录 动态规划Ⅴ
494. 目标和 给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 或 - ,然后串联起所有整数,可以构造一个 表达式 : 例如,nums [2, 1] ,可以在 2 之前添加 ,在 1 之前添加 - …...
驱动DAY9
驱动文件 #include <linux/init.h> #include <linux/module.h> #include <linux/of.h> #include <linux/of_gpio.h> #include <linux/gpio.h> #include <linux/fs.h> #include <linux/io.h> #include <linux/device.h> #incl…...
03贪心:摆动序列
03贪心:摆动序列 376. 摆动序列 局部最优:删除单调坡度上的节点(不包括单调坡度两端的节点),那么这个坡度就可以有两个局部峰值。 整体最优:整个序列有最多的局部峰值,从而达到最长摆动序列。…...
javascript获取元素在浏览器中工作区域的左、右、上、下距离,或带滚动条的元素在页面中的大小
//获取元素在包含元素框中的大小 //第1个函数为获取元素在包含元素中左内边框的距离 function getELementLeft(element){//获取元素在包含元素左边距离var actualeftelement.offsetLeft;//获取元素的上级包含元素var currentelement.offsetParent;//循环到一直没有包含元素whil…...
VSCode 安装使用教程 环境安装配置 保姆级教程
一个好用的 IDE 不仅能提升我们的开发效率,还能让我们保持愉悦的心情,这样才是非常 Nice 的状态 ^_^ 那么,什么是 IDE 呢 ? what IDE(Integrated Development Environment,集成开发环境)是含代码…...
c盘中temp可以删除吗?appdata\local\temp可以删除吗?
http://www.win10d.com/jiaocheng/22594.html C盘AppData文件夹是一个系统文件夹,里面存储着临时文件,各种应用的自定义设置,快速启动文件等。近期有用户发现appdata\local\temp占用了大量的空间,那么该文件可以删除吗?…...
Java手写聚类算法
Java手写聚类算法 1. 算法思维导图 以下是聚类算法的实现原理的思维导图,使用Mermanid代码表示: #mermaid-svg-AK9EgYRS38PkRJI4 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-AK9EgYRS38…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...
