当前位置: 首页 > news >正文

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);}
}

## 思路:

汉诺塔问题是一个经典的递归问题,它描述了一种将一堆圆盘从一个塔座移动到另一个塔座的问题,同时需要遵守一些规则。问题的规则如下:

  1. 有三个塔座,通常称为A、B、C。
  2. 初始时,在塔座A上有若干个圆盘,这些圆盘自下而上,由大到小地叠在一起。
  3. 目标是将塔座A上的所有圆盘移动到塔座B上,并仍然按照相同的顺序叠放。
  4. 每次只能移动一个圆盘。
  5. 任何时刻都不允许将较大的圆盘放在较小的圆盘之上。
  6. 在满足前两条规则的前提下,可以将圆盘从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);
}

工作原理解释:

  1. 如果 n 等于 1,表示只有一个圆盘需要移动,直接将它从 from 移动到 to,并输出移动过程。

  2. 如果 n 大于 1,表示有多个圆盘需要移动。递归的过程如下:

    • 第一步:将前 n-1 个圆盘从起始塔座 from 经过目标塔座 to 移动到辅助塔座 by 上。这一步使用了递归调用,因为它也是一个汉诺塔问题,只不过规模减小了。

    • 第二步:将最大的圆盘从起始塔座 from 移动到目标塔座 to 上,并输出移动过程。这是实际的移动步骤。

    • 第三步:将前 n-1 个圆盘从辅助塔座 by 经过起始塔座 from 移动到目标塔座 to 上。这一步同样使用了递归调用。

这个递归过程会一直持续到只剩下一个圆盘需要移动,然后问题就会逐级返回,完成了所有圆盘的移动。

通过这种递归方法,你可以模拟汉诺塔问题的解决过程,并输出移动步骤。

相关文章:

6-1 汉诺塔

汉诺&#xff08;Hanoi&#xff09;塔问题是一个经典的递归问题。 设有A、B、C三个塔座&#xff1b;开始时&#xff0c;在塔座A上有若干个圆盘&#xff0c;这些圆盘自下而上&#xff0c;由大到小地叠在一起。要求将塔座A上的圆盘移到塔座B上&#xff0c;并仍按同样顺序叠放。在…...

Linux之initd管理系统(海思、ZYNQ、复旦微)添加密码登录验证

设置root用户密码&#xff1a;passwd命令设置密码&#xff0c;即修改/etc/passwd文件 一、串口提示输入用户名密码方法 修改 /etc/inittab 方法一&#xff1a; 增加&#xff1a; ::askfirst:-/bin/login 注释&#xff1a; #::respawn:/sbin/getty -L ttyS000 115200 vt…...

怎么更改代理ip,代理ip如何切换使用?

我们要如何使用HTTP代理&#xff0c;对它进行切换使用呢&#xff1f; 如果你购买了青果网络的HTTP代理&#xff0c;可以在文档这边获取使用方法&#xff1a; 可以在这里调试&#xff1a; 也可以在这里选择key提取。 如果有的朋友们想利用利用python&#xff0c;每隔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&#xff1a;屏幕高度 window.innerHeight&#xff1a;视口高度&#xff08;去除浏览器头尾的高度&#xff09; document.body.clientHeight&#xff1a;内容高度 vh&#xff1a;网页视口高度的1/100 vw&#xff1a;网页视口宽度的1/100 vmax&#xff…...

uni-app 之 解决u-button始终居中问题

uView中u-button始终居中问题如何解决的简单方法&#xff1f; 1&#xff1a;给该元素margin-right: 0;可以达到向右靠齐&#xff1b; 2&#xff1a;给该元素的父元素设置float: right image.png <u-button style"width: 50px; margin-left: 0;" plain"t…...

Python日期处理库:掌握时间的艺术

&#x1f482; 个人网站:【工具大全】【游戏大全】【神级源码资源网】&#x1f91f; 前端学习课程&#xff1a;&#x1f449;【28个案例趣学前端】【400个JS面试题】&#x1f485; 寻找学习交流、摸鱼划水的小伙伴&#xff0c;请点击【摸鱼学习交流群】 日期和时间在计算机编程…...

JOSEF约瑟 智能电流继电器KWJL-20/L KWLD26 零序孔径45mm 柜内导轨式安装

KWJL-20智能电流继电器 零序互感器&#xff1a; KWLD80 KWLD45 KWLD26 KWJL-20 一、产品概述 KWJL-20系列智能剩余电流继电器&#xff08;以下简称继电器&#xff09;适用于交流电压至660V或更高的TN、TT、和IT系统&#xff0c;频率为50Hz。通过零序电流互感器检测出超过…...

NLP技术如何为搜索引擎赋能

目录 1. NLP关键词提取与匹配在搜索引擎中的应用1. 关键词提取例子 2. 关键词匹配例子 Python实现 2. NLP语义搜索在搜索引擎中的应用1. 语义搜索的定义例子 2. 语义搜索的重要性例子 Python/PyTorch实现 3. NLP个性化搜索建议在搜索引擎中的应用1. 个性化搜索建议的定义例子 2…...

演唱会没买到票?VR直播为你弥补遗憾

听说周杰伦开了演唱会&#xff1f;没买到票的人是不是有着大大的遗憾呢&#xff1f;很多时候大型活动、演唱会都会因为场地限制而导致很多人未能有缘得见&#xff0c;而且加上票价成本高&#xff0c;“黄牛票”事件频出&#xff0c;我们的钱包受不住啊&#xff01;&#xff01;…...

myabtis的缓存级别

文章目录 MyBatis缓存的区别是什么作用范围方面有哪些差异生命周期数据进行了存储缓存的优缺点 MyBatis缓存的区别是什么 MyBatis 提供了一级缓存和二级缓存&#xff0c;这两者的主要区别在于其作用范围和生命周期。 一级缓存&#xff1a;一级缓存是 SqlSession 级别的缓存。…...

gin框架再探

Gin框架介绍及使用 | 李文周的博客 (liwenzhou.com) lesson03_gin框架初识_哔哩哔哩_bilibili 1.路由引擎 //路由引擎 rgin.Default() 2.一些http请求方法 get post put delete等等 遇到什么路径&#xff0c;执行什么函数 r.GET("/hello",func{做你想做的事返回…...

经典算法-----约瑟夫问题(C语言)

目录 前言 故事背景 约瑟夫问题 环形链表解决 数组解决 前言 今天我们来玩一个有意思的题目&#xff0c;也就是约瑟夫问题&#xff0c;这个问题出自于欧洲中世纪的一个故事&#xff0c;下面我们就去通过编程的方式来解决这个有趣的问题&#xff0c;一起来看看吧&#xff01…...

代码随想录 动态规划Ⅴ

494. 目标和 给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 或 - &#xff0c;然后串联起所有整数&#xff0c;可以构造一个 表达式 &#xff1a; 例如&#xff0c;nums [2, 1] &#xff0c;可以在 2 之前添加 &#xff0c;在 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贪心&#xff1a;摆动序列 376. 摆动序列 局部最优&#xff1a;删除单调坡度上的节点&#xff08;不包括单调坡度两端的节点&#xff09;&#xff0c;那么这个坡度就可以有两个局部峰值。 整体最优&#xff1a;整个序列有最多的局部峰值&#xff0c;从而达到最长摆动序列。…...

javascript获取元素在浏览器中工作区域的左、右、上、下距离,或带滚动条的元素在页面中的大小

//获取元素在包含元素框中的大小 //第1个函数为获取元素在包含元素中左内边框的距离 function getELementLeft(element){//获取元素在包含元素左边距离var actualeftelement.offsetLeft;//获取元素的上级包含元素var currentelement.offsetParent;//循环到一直没有包含元素whil…...

VSCode 安装使用教程 环境安装配置 保姆级教程

一个好用的 IDE 不仅能提升我们的开发效率&#xff0c;还能让我们保持愉悦的心情&#xff0c;这样才是非常 Nice 的状态 ^_^ 那么&#xff0c;什么是 IDE 呢 &#xff1f; what IDE&#xff08;Integrated Development Environment&#xff0c;集成开发环境&#xff09;是含代码…...

c盘中temp可以删除吗?appdata\local\temp可以删除吗?

http://www.win10d.com/jiaocheng/22594.html C盘AppData文件夹是一个系统文件夹&#xff0c;里面存储着临时文件&#xff0c;各种应用的自定义设置&#xff0c;快速启动文件等。近期有用户发现appdata\local\temp占用了大量的空间&#xff0c;那么该文件可以删除吗&#xff1f…...

Java手写聚类算法

Java手写聚类算法 1. 算法思维导图 以下是聚类算法的实现原理的思维导图&#xff0c;使用Mermanid代码表示&#xff1a; #mermaid-svg-AK9EgYRS38PkRJI4 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-AK9EgYRS38…...

VeighNa量化框架实战:如何免费获取TuShare金融数据(附完整接入代码)

VeighNa量化框架实战&#xff1a;零成本高效获取TuShare金融数据的完整指南 在量化交易领域&#xff0c;数据获取往往是第一个需要跨越的门槛。对于个人开发者和小型团队而言&#xff0c;如何在预算有限的情况下获取高质量的金融数据&#xff0c;成为决定项目成败的关键因素之一…...

STC89C52单片机+槽型光耦,手把手教你DIY一个低成本电机转速测量仪

STC89C52单片机槽型光耦DIY电机转速测量仪实战指南 从零搭建低成本测速系统的完整方案 电机转速测量在工业控制、机器人开发、智能小车等领域都是基础但关键的环节。市面上专业测速仪动辄上千元的价格让许多电子爱好者望而却步。其实&#xff0c;利用手头常见的STC89C52单片机…...

ThinkPad装Win10企业版后,手把手教你用PowerShell搞定Lenovo Vantage(附依赖包下载)

ThinkPad安装Win10企业版后手动部署Lenovo Vantage的完整指南 当你在ThinkPad上安装了纯净的Windows 10企业版系统后&#xff0c;可能会发现无法通过常规方式安装Lenovo Vantage这款官方管理工具。本文将详细介绍如何通过PowerShell命令手动安装Lenovo Vantage及其所有必需的依…...

安全第一:OpenClaw+GLM-4.7-Flash的本地化数据处理方案

安全第一&#xff1a;OpenClawGLM-4.7-Flash的本地化数据处理方案 1. 为什么我们需要本地化AI解决方案 上个月我帮一位律师朋友处理合同审查任务时&#xff0c;遇到了一个棘手问题——他需要分析上百份涉及商业机密的文件&#xff0c;但担心使用云端AI服务会导致数据泄露。这…...

Python 字典遍历全攻略:5 种常用方法 + 性能对比 + 实战优化技巧

在 Python 开发中&#xff0c;字典&#xff08;dict&#xff09; 是最常用的数据结构之一&#xff0c;以键值对形式存储数据&#xff0c;具备查询快、易操作的特点。而字典的遍历是日常开发中高频操作 —— 从简单的数据读取&#xff0c;到大规模数据处理、接口返回值解析&…...

从漏极、栅极到源极开关:手把手教你选对单端电荷泵拓扑(基于噪声与速度权衡)

从漏极、栅极到源极开关&#xff1a;单端电荷泵拓扑的噪声与速度权衡实战指南 在锁相环(PLL)设计中&#xff0c;电荷泵的性能往往成为整个系统相位噪声和杂散特性的瓶颈。特别是当设计目标同时包含低带内相位噪声和高开关速度时&#xff0c;单端电荷泵的拓扑选择就变得尤为关键…...

AI辅助开发深度探索:在快马平台上对比评测类qoderwork官网的AI代码生成能力

最近在研究AI辅助开发时&#xff0c;发现一个很有意思的现象&#xff1a;同样是生成一个网页项目&#xff0c;不同AI模型给出的代码风格和实现思路差异很大。这让我萌生了一个想法——能不能搭建一个平台&#xff0c;专门用来对比评测不同AI模型的代码生成能力&#xff1f;就像…...

开源键盘固件终极配置指南:轻松自定义你的机械键盘

开源键盘固件终极配置指南&#xff1a;轻松自定义你的机械键盘 【免费下载链接】vial-qmk QMK fork with Vial-specific features. 项目地址: https://gitcode.com/gh_mirrors/vi/vial-qmk 想要完全掌控你的机械键盘&#xff0c;打造独一无二的输入体验吗&#xff1f;Vi…...

如何突破分子观察瓶颈?PyMOL开源版的3大核心优势

如何突破分子观察瓶颈&#xff1f;PyMOL开源版的3大核心优势 【免费下载链接】pymol-open-source Open-source foundation of the user-sponsored PyMOL molecular visualization system. 项目地址: https://gitcode.com/gh_mirrors/py/pymol-open-source PyMOL开源版作…...

Qwen2.5-Coder-1.5B代码修复实战:常见Bug自动诊断与修复

Qwen2.5-Coder-1.5B代码修复实战&#xff1a;常见Bug自动诊断与修复 你有没有过这样的经历&#xff1f;深夜赶项目&#xff0c;代码跑起来一堆红字&#xff0c;对着报错信息一头雾水&#xff0c;查了半天文档还是找不到问题在哪。或者&#xff0c;接手一个老项目&#xff0c;里…...