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

【C语言】汉诺塔 —— 详解

一、介绍

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

面试题 08.06. 汉诺塔问题 - 力扣(LeetCode)


二、问题描述

有 A,B,C 三根柱子,A 上面有 n 个盘子,我们想把 A 上面的盘子移动到 C 上,但是必须要满足以下三个条件:

  • 每次只能移动一个盘子;
  • 盘子只能从柱子顶端滑出移到下一根柱子;
  • 盘子只能叠在比它大的盘子上。


三、解题思路

这是一道递归方法的经典题目。

1、如果 n = 1,只有一个盘子,那么就直接将它从 A 移到 C 上

2、如果 n = 2,这时我们就需要借助 B,因为小盘子必须时刻都在大盘子上面,共需要 4 步


3、如果 n > 2,思路和上面是一样的。我们将 n 个盘子看成两个部分,一部分有 1 个盘子,另一部分有 n-1 个盘子

可是,那 n-1 个盘子是如何从 A 移动到 B 再移动到 C 的呢? 

将最初的 n 个盘子从 A 移到 C 的问题,转化成了将 n-1 个盘子从 A 移到 C 的问题, 以此类推,直至转化成 1 个盘子的问题时,这个问题也就解决了。这里利用了分治的思想。

  1. 当 n = 1 时,直接将盘子从 A 移到 C 上;
  2. 当 n > 1 时,
  • 先把上面的 n-1 个盘子从 A 借助 C 移动到 B(化为子问题,进行递归);
  • 再将 A 上最后一个盘子从 A →C;
  • 再将 B 上 n - 1 个盘子从 B 借助 A 移动到 C(化为子问题,进行递归)。

四、代码

#include<stdio.h>void move(char A, char C, int n)
{printf("把第%d个圆盘从%c——>%c\n", n, A, C);
}void HanoiTower(char A, char B, char C, int n)
{if (n == 1){move(A, C, n);}else{// 1.把A上n-1个圆盘从A柱借助C移动到B上HanoiTower(A, C, B, n - 1);// 2.将A最后一个圆盘从A->Cmove(A, C, n);// 3.把B上n-1个圆盘从B借助A移动到C上HanoiTower(B, A, C, n - 1);}
}int main()
{int n = 0;printf("输入A柱上的圆盘的个数:");scanf("%d\n", &n);//将n个圆盘从A柱借助B柱移动到C柱上HanoiTower('A', 'B', 'C', n);return 0;
}

五、扩展

如果想要计算移动了多少次盘子,只需要加入多一个 move() 函数即可。 

相关文章:

【C语言】汉诺塔 —— 详解

一、介绍 汉诺塔&#xff08;Tower of Hanoi&#xff09;&#xff0c;又称河内塔&#xff0c;是一个源于印度古老传说的益智玩具。大焚天创造世界的时候做了三根金刚石柱子&#xff0c;在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。 大焚天命令婆罗门把圆盘从下面开始按…...

【云备份】

文章目录 [toc] 1 :peach:云备份的认识:peach:1.1 :apple:功能了解:apple:1.2 :apple:实现目标:apple:1.3 :apple:服务端程序负责功能:apple:1.4 :apple:服务端功能模块划分:apple:1.5 :apple:客户端程序负责功能:apple:1.6 :apple:客户端功能模块划分:apple: 2 :peach:环境搭建…...

第四十六章 命名空间和数据库 - 系统提供的数据库

文章目录 第四十六章 命名空间和数据库 - 系统提供的数据库系统提供的数据库ENSLIBIRISAUDITIRISLIBIRISLOCALDATAIRISSYS (the system manager’s database 系统管理器的数据库)IRISTEMP 第四十六章 命名空间和数据库 - 系统提供的数据库 系统提供的数据库 IRIS 提供以下数据…...

【贪心的商人】python实现-附ChatGPT解析

1.题目 贪心的商人 知识点:贪心 时间限制:1s 空间限制: 256MB 限定语言:不限 题目描述: 商人经营一家店铺,有number种商品,由于仓库限制 每件商品的最大持有数量是item[index], 每种商品的价格在每天是item_price[item_index][day], 通过对商品的买进和卖出获取利润,请给…...

解决nvm切换node版本失败的终极办法-秒杀网上99%的水文

nvm是一款强大的node多版本管理器&#xff0c;可以轻易选择你需要的node版本&#xff0c;这对win7平台简直就是超好的福音&#xff1a;可以突破node 14.15以上的安装限制。 但是nvm安装有一个巨大的坑点&#xff1a;nvm use 版本号以后&#xff0c;并没有生效&#xff0c;nvm …...

2023蓝帽杯半决赛电子取证+CTF部分题解

文章目录 电子取证123456789101112131415 CTFWeb | MyLinuxBotWeb | AirticleShareCrypto | ezrsaPwn | AdminPwn | uafmisc|排排坐吃吃果果 电子取证 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 CTF Web | MyLinuxBot Web | AirticleShare import requests import times reques…...

OCTA数据集(Rose)+ OCTA-Net

ROSE: A Retinal OCT-Angiography(视网膜眼底相干光层析血管成像术) Vessel Segmentation(血管分割) Dataset and New Model 论文&#xff1a;ROSE: A Retinal OCT-Angiography Vessel Segmentation Dataset and New Model 代码和数据集&#xff1a;ROSE1&2 - 医疗影像/眼…...

java Spring Boot 手动启动热部署

好 接下来 我们讲一个对开发非常重要的东西 热部署 因为 我们在开发过程中总会希望快点看到效果 或者 你的企业项目一般很大很复杂&#xff0c;重启是一件非常麻烦的事 或者你在和前端同事联调&#xff0c;有一点小问题 你改完就要重启 前端还得等你&#xff0c;非常不友好 那…...

Autosar诊断实战系列20-UDS首帧数据接收及流控帧发送代码级分析

本文框架 前言1. 长帧数据的首帧接收2. 首帧数据的处理及流控帧发送2.1 首帧数据的处理2.2 流控帧数据的发送前言 在本系列笔者将结合工作中对诊断实战部分的应用经验进一步介绍常用UDS服务的进一步探讨及开发中注意事项, Dem/Dcm/CanTp/Fim模块配置开发及注意事项,诊断与Bs…...

C/C++ 数据结构 - 队列

1.队列 https://blog.csdn.net/LiuBo_01/article/details/80412290 1 #include <stdio.h>2 #include <stdlib.h>3 4 typedef struct Node5 {6 int data;7 struct Node* next;8 }N;9 10 typedef struct11 {12 N* front;13 N* rear;14 }Q;15 16 //…...

免杀对抗-DLL劫持免杀

C&Py-DLL劫持-语言-调用加载 1.使用visual studio创建项目 2.将文件名重命名为.c后缀 3.将如下加载器代码生成dll文件 加载器代码&#xff1a; #include "pch.h" #include <Windows.h> #include <stdio.h> #include <string.h>#pragma comment…...

Anaconda添加channels后出现unexpected urllib3 DEBUG logging from conda-build

1.问题描述 anaconda更新之后添加channels后出现bug: (base) ~/zlib-feedstock % conda build recipe 2>&1 | tee out ... INFO:conda_build.metadata:Attempting to finalize metadata for libzlib DEBUG:urllib3.connectionpool:Starting new HTTPS connection (1):…...

python 将二维数组的数据保存到csv文件中

import csv# 将数据保存为有标题(第一行为标题)的csv文档 lst [[日期, 最高气温, 最低气温, 天气, 风向],[2022-10-01 星期六, 34℃, 25℃, 雾, 东风 1级],[2022-10-02 星期日, 37℃, 26℃, 晴, 东南风 1级],[2022-10-03 星期一, 38℃, 24℃, 晴, 南风 1级],[2022-10-04 星期二…...

UGUI交互组件Button

一.初识Button对象 从菜单中创建Button对象&#xff0c;Button的文本由子节点Text对象显示&#xff0c;Button对象的组件除了基础组件外&#xff0c;还有Image用来显示Button常规态的图片&#xff0c;还有Button组件用来控制点击过渡效果和点击事件的响应。 二.Button组件的属…...

认知智能最新研究成果

声明&#xff1a;以下内容仅代表个人对现象和本质探索&#xff0c;不代表对学术成果评价。曾有幸和马文明斯基的学生段老师和方老师一起讨论过人工智能问题。随着自己对问题进一步理解&#xff0c;刚好18年左右开始接触认知智能理论核心认知计算部分。 第一&#xff1a;算法是一…...

Armv8/Armv9 Cache知识大纲分享--思维导图

关键词&#xff1a;cache学习、mmu学习、cache资料、mmu资料、arm资料、armv8资料、armv9资料、 trustzone视频、tee视频、ATF视频、secureboot视频、安全启动视频、selinux视频&#xff0c;cache视频、mmu视频&#xff0c;armv8视频、armv9视频、FF-A视频、密码学视频、RME/CC…...

如何使用百度“云一朵”来分析PDF文件

PDF 文件是一种常见的文件格式&#xff0c;用于存储文档、图像和其他内容。在许多情况下&#xff0c;我们需要对 PDF 文件进行分析&#xff0c;以提取其中的信息。百度“云一朵”提供了一个 PDF 分析 API&#xff0c;可以帮助我们轻松地对 PDF 文件进行分析。 在本博客文章中&…...

IIS解决上传文件大小限制

IIS解决上传文件大小限制 目的&#xff1a;通过配置文件和IIS来解决服务器对上传文件大小的限制 1&#xff1a;修改配置文件&#xff08;默认为4M 值的大小根据自己情况进行修改&#xff09; <httpRuntime maxRequestLength"2048000" /> 2&#xff1a;修改IIS配…...

多源最短路径的原理及C++实现

时间复杂度 O(n3),n是端点数。 核心代码 template<class T, T INF 1000 * 1000 * 1000> class CNeiBoMat { public: CNeiBoMat(int n, const vector<vector<int>>& edges,bool bDirectfalse,bool b1Base false) { m_vMat.assign(n, vector<…...

JMeter性能测试

性能测试前言 老师开局一句话&#xff1a;性能测试和你会不会JMeter一点关系没有…… 作者坚持技多不压身的原则&#xff0c;还是多学一点JMeter吧&#xff0c;看老师到底要怎么讲下去&#xff0c;什么并发量、吞吐量啥的…… 性能测试的核心思想&#xff1a;在于创造大量并发去…...

Cocos Creator3.8 实战问题(四)巧用九宫格图像拉伸

一、为什么要使用九宫格图像拉伸 相信做过前端的同学都知道&#xff0c;ui &#xff08;图片&#xff09;资源对包体大小和内存都有非常直接的影响。 通常ui 资源都是图片&#xff0c;也是最占资源量的资源类型&#xff0c;游戏中的ui 资源还是人机交互的最重要的部分&#xff…...

Linux shell编程学习笔记7:只读变量

在编程过程中&#xff0c;我们经常会使用到一些常量&#xff0c;也就是值不需要改变的变量&#xff0c;在许多编程语言提供了常量的定义方式&#xff0c;比如c/c的define MAXNUM 99999 或 const int a 7&#xff0c;javasccipt的const a7&#xff0c; 等等。 跟以上这些方法…...

Scala第十七章节

Scala第十七章节 scala总目录 文档资料下载 章节目标 了解集合的相关概念掌握Traversable集合的用法掌握随机学生序列案例 1. 集合 1.1 概述 但凡了解过编程的人都知道程序 算法 数据结构这句话, 它是由著名的瑞士计算机科学家尼古拉斯沃斯提出来的, 而他也是1984年图灵…...

BGP高级特性——4字节AS号

目录 4字节AS号 相关概念 两种过渡属性 4字节AS号的格式 4字节AS号建立邻居 4字节AS号路由传递 配置命令 4字节AS号 相比于2字节AS号&#xff0c;范围更大。由1~65535扩展到1~4294967295 支持4字节AS号的BGP设备兼容仅支持2字节AS号的BGP设备 相关概念 Speaker&#…...

cesium源码无法更新的解决方案

一、环境&#xff1a; 中国移动的宽带 win10操作系统 二、问题复现步骤&#xff1a; 1、开了VPN&#xff0c;设置为全局代理 2、在vscode中执行git pull命令 3、结果显示无法更新 三、解决方案&#xff1a; 1、安装Github官方开发的软件Github Desktop 下载地址&#xf…...

大数据-玩转数据-双流JOIN

一、双流JOIN 在Flink中, 支持两种方式的流的Join: Window Join和Interval Join 二、Window Join 窗口join会join具有相同的key并且处于同一个窗口中的两个流的元素. 注意: 1.所有的窗口join都是 inner join, 意味着a流中的元素如果在b流中没有对应的, 则a流中这个元素就不会…...

from PIL import Image,文字成图,ImageFont import jieba分词,input优雅python绘制图片

开始的代码 import os from PIL import Image, ImageDraw, ImageFont import jiebadef generate_image_with_white_bg(text, font_path, output_path):# 设置图片大小和背景颜色image_width 800image_height 600bg_color (255, 255, 255) # 白色# 创建图片对象image Imag…...

渗透测试信息收集方法笔记

一、指纹识别 1、钟馗之眼https://www.zoomeye.org/ 2、天眼查https://www.tianyancha.com/ 3、工具&#xff1a;御剑WEB指纹识别系统正式版&#xff0c;可以查网站用了哪些框架&#xff0c;什么版本&#xff0c;有哪些漏洞 4、kali whatweb 二、信息泄露 1、csdn https://www.…...

协议栈——连接服务器

如对方的ip和port配置信息&#xff0c;这里的连接是指通信前的准备工作 上一篇介绍查看套接字的命令时&#xff0c;可以看到很多信息&#xff0c;但是刚刚创建出来的套接字是什么信息都没有的&#xff0c;协议栈也因此不知道和谁通信&#xff1b; 客户端填补信息 这一步中调…...

数据结构--队列与循环队列的实现

数据结构–队列的实现 1.队列的定义 比如有一个人叫做张三,这天他要去医院看病,看病时就需要先挂号,由于他来的比较晚,所以他的号码就比较大,来的比较早的号码就比较小,需要到就诊窗口从小号到大依次排队,前面的小号就诊结束之后,才会轮到大号来,小号每就诊完毕就销毁,每新来…...

苹果做安卓游戏下载网站好/百度推广客户端手机版

本文主要向大家介绍了C/C知识点之1003 Emergency(25 分)C语言版本(提问求解答)&#xff0c;通过具体的内容向大家展示&#xff0c;希望对大家学习C/C知识点有所帮助。1003 Emergency(25 分)As an emergency rescue team leader of a city, you are given a special map of your…...

wordpress 培训插件/网站排名优化方法

1. 编写程序&#xff0c;声明一个method方法&#xff0c;在方法中打印一个108 的型矩形&#xff0c; 在main方法中调用该方法。 2. 修改上一个程序&#xff0c;在method方法中&#xff0c;除打印一个108的型矩形外&#xff0c;再 计算该矩形的面积&#xff0c;并将其作为方法返…...

中企动力科技股份有限公司销售/互联网优化

1. Class类的使用 1.1 class的获取有三种方式 F fnew F();//方法一 任何一个类都有一个隐含的静态成员变量classClass c1F.class;//方法二 已经知道该类的对象通过getClass方法Class c2f.getClass();System.out.println(c1c2); //true//方法三 Class.forName()方…...

net网站开发教学视频/韶山百度seo

字符串的方法 charAt();返回字符串指定索引的字符&#xff1b;concat();连接两个或多个字符串&#xff1b;indexOf();返回字符串中检索指定字符第一次出现的位置&#xff1b;lastIndexOf();返回字符串中检索指定字符最后一次出现的位置&#xff1b;subString();提取字符串中两个…...

网站开发的成品/域名注册阿里云

希尔排序的实质就是分组插入排序&#xff0c;该方法又称缩小增量排序&#xff0c;因DL&#xff0e;Shell于1959年提出而得名。 该方法的基本思想是&#xff1a;先将整个待排元素序列分割成若干个子序列&#xff08;由相隔某个“增量”的元素组成的&#xff09;分别进行直接插入…...

网站的服务/环球军事网最新消息

1.写文件 f open(out.txt,w) f.write(%s %d %d %d %d 0 0 0 0 0 0 0%(bbx.name,bbx.x,bbx.y,bbx.w,bbx.h)) f.close() 2.读文件 第一种 f open("foo.txt") # 返回一个文件对象 line f.readline() # 调用文件的 readline()方法 while li…...