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…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
图解JavaScript原型:原型链及其分析 | JavaScript图解
忽略该图的细节(如内存地址值没有用二进制) 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么:保存在堆中一块区域,同时在栈中有一块区域保存其在堆中的地址(也就是我们通常说的该变量指向谁&…...
车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...
