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

c/c++蓝桥杯经典编程题100道（19）汉诺塔问题

news 来源：原创 2025/9/21 11:21:27

汉诺塔问题

->返回c/c++蓝桥杯经典编程题100道-目录

汉诺塔问题

一、题型解释

二、例题问题描述

三、C语言实现

解法1：递归法（难度★）

解法2：迭代法（难度★★★）

四、C++实现

解法1：递归法（使用STL容器记录步骤，难度★☆）

解法2：面向对象封装（难度★★）

五、总结对比表

六、特殊方法与内置函数补充

1. C语言中的结构体栈

2. C++的 std::vector

3. 汉诺塔数学公式

一、题型解释

汉诺塔（Tower of Hanoi）是经典的递归问题，描述如下：

三根柱子：A（起点）、B（辅助）、C（终点）。
若干盘子：初始时所有盘子按大小顺序叠放在A柱，大的在下，小的在上。
目标：将所有盘子从A柱移动到C柱，每次只能移动一个盘子，且任何时候大盘子不能放在小盘子上。

常见题型：

基础问题：计算移动步骤或最少步数（n个盘子需移动 2^n - 1 次）。
多柱扩展：四根或多根柱子的变种问题（如Frame-Stewart算法）。
路径限制：限制某些移动规则（如只能从A→B、B→C、C→A）。

二、例题问题描述

例题1：输入盘子数 n=3，输出移动步骤：

A → C  
A → B  
C → B  
A → C  
B → A  
B → C  
A → C

例题2：输入 n=4，输出最少移动次数 15。
例题3：验证移动序列 [A→B, A→C, B→C] 是否是 n=2 的有效解（输出 true）。

三、C语言实现

解法1：递归法（难度★）

通俗解释：

将问题分解为三步：
1. 将前 n-1 个盘子从A移动到B（借助C）。
2. 将第 n 个盘子从A移动到C。
3. 将 n-1 个盘子从B移动到C（借助A）。

#include <stdio.h>// 递归函数：将n个盘子从src移动到dst，使用aux作为辅助
void hanoi(int n, char src, char aux, char dst) {if (n == 1) { // 基线条件：只剩一个盘子直接移动printf("%c → %c\n", src, dst);return;}hanoi(n - 1, src, dst, aux); // 将n-1个盘子从src移动到aux（借助dst）printf("%c → %c\n", src, dst); // 移动第n个盘子到dsthanoi(n - 1, aux, src, dst); // 将n-1个盘子从aux移动到dst（借助src）
}int main() {int n = 3;hanoi(n, 'A', 'B', 'C');return 0;
}

代码逻辑：

基线条件：当 n=1 时，直接移动盘子。
递归分解：
- 第一步：将 n-1 个盘子从起点移动到辅助柱（递归调用）。
- 第二步：移动最大的盘子到目标柱。
- 第三步：将 n-1 个盘子从辅助柱移动到目标柱（递归调用）。
时间复杂度：O(2^n)，因为每一步分解为两个子问题。

解法2：迭代法（难度★★★）

通俗解释：

用栈模拟递归过程，手动管理每一步的状态（当前盘子数、源柱、辅助柱、目标柱）。

#include <stdio.h>
#include <stdlib.h>// 定义栈结构体，存储每一步的状态
typedef struct {int n;char src, aux, dst;
} StackFrame;void hanoiIterative(int n, char src, char aux, char dst) {StackFrame stack[100]; // 假设n不超过100层int top = -1; // 栈顶指针// 初始状态：移动n个盘子从src到dst，使用aux辅助StackFrame init = {n, src, aux, dst};stack[++top] = init;while (top >= 0) {StackFrame current = stack[top--]; // 弹出当前任务if (current.n == 1) {printf("%c → %c\n", current.src, current.dst);} else {// 分解为三个子任务（注意顺序与递归相反）// 子任务3：移动n-1个盘子从aux到dst，使用src辅助StackFrame task3 = {current.n - 1, current.aux, current.src, current.dst};stack[++top] = task3;// 子任务2：移动第n个盘子从src到dstStackFrame task2 = {1, current.src, current.aux, current.dst};stack[++top] = task2;// 子任务1：移动n-1个盘子从src到aux，使用dst辅助StackFrame task1 = {current.n - 1, current.src, current.dst, current.aux};stack[++top] = task1;}}
}int main() {hanoiIterative(3, 'A', 'B', 'C');return 0;
}

代码逻辑：

栈模拟递归：显式管理待处理的任务（类似递归调用栈）。
任务分解顺序：由于栈是后进先出，子任务需按相反顺序入栈。
优势：避免递归的栈溢出风险，适合大规模n。

四、C++实现

解法1：递归法（使用STL容器记录步骤，难度★☆）

通俗解释：

使用 vector 存储移动步骤，方便后续处理或输出。

cpp

#include <iostream>
#include <vector>
using namespace std;vector<string> steps; // 存储移动步骤void hanoi(int n, char src, char aux, char dst) {if (n == 1) {steps.push_back(string(1, src) + " → " + dst);return;}hanoi(n - 1, src, dst, aux);steps.push_back(string(1, src) + " → " + dst);hanoi(n - 1, aux, src, dst);
}int main() {hanoi(3, 'A', 'B', 'C');for (const string& step : steps) {cout << step << endl;}return 0;
}

代码逻辑：

与C语言递归逻辑相同，但使用 vector<string> 动态存储步骤。
输出灵活性：可随时访问或修改步骤记录。

解法2：面向对象封装（难度★★）

通俗解释：

将汉诺塔问题封装为类，支持多种操作（如统计步数、验证步骤）。

cpp

#include <iostream>
#include <vector>
using namespace std;class HanoiSolver {
private:vector<string> steps;void move(int n, char src, char aux, char dst) {if (n == 1) {steps.push_back(string(1, src) + " → " + dst);return;}move(n - 1, src, dst, aux);steps.push_back(string(1, src) + " → " + dst);move(n - 1, aux, src, dst);}
public:void solve(int n) {steps.clear();move(n, 'A', 'B', 'C');}void printSteps() {for (const string& step : steps) {cout << step << endl;}}
};int main() {HanoiSolver solver;solver.solve(3);solver.printSteps();return 0;
}

代码逻辑：

封装性：将步骤记录和求解逻辑封装在类中。
扩展性：可添加方法统计步数、验证移动序列等。

五、总结对比表

方法	时间复杂度	空间复杂度	优点	缺点
递归法	O(2^n)	O(n)	代码简洁，易理解	栈溢出风险
迭代法	O(2^n)	O(n)	避免递归栈溢出	代码复杂，需手动管理栈
STL容器记录	O(2^n)	O(2^n)	灵活处理步骤	内存占用高
面向对象封装	O(2^n)	O(2^n)	扩展性强，易于维护	代码稍长

六、特殊方法与内置函数补充

1. C语言中的结构体栈

作用：手动实现栈结构，存储递归状态（需注意栈大小限制）。

2. C++的 `std::vector`

动态数组：自动扩展容量，适合存储不定长的移动步骤。

3. 汉诺塔数学公式

最少步数：2^n - 1，可通过位运算快速计算（如 (1 << n) - 1）。

->返回c/c++蓝桥杯经典编程题100道-目录

c/c++蓝桥杯经典编程题100道（19）汉诺塔问题

汉诺塔问题 ->返回c/c蓝桥杯经典编程题100道-目录目录汉诺塔问题一、题型解释二、例题问题描述三、C语言实现解法1：递归法（难度★） 解法2：迭代法（难度★★★） 四、C实现解法1&#xff1…...

编程日记 2025/9/21 11:21:27

CSS盒模

CSS盒模型就像一个快递包裹，网页上的每个元素都可以看成是这样一个包裹，它主要由以下几个部分组成： 内容（content）：就像包裹里真正装的东西，比如文字、图片等。在CSS里，可用width&a…...

编程日记 2025/9/20 14:07:51

【go语言规范】关于接口设计

抽象应该被发现，而不是被创造。为了避免不必要的复杂性，需要时才创建接口，而不是预见到需要它，或者至少可以证明这种抽象是有价值的。 “The bigger the interface, the weaker the abstraction. 不要用接口进行设计，要…...

编程日记 2025/9/13 10:12:06

计算机视觉+Numpy和OpenCV入门

Day 1：Python基础Numpy和OpenCV入门 Python基础变量与数据类型、函数与类的定义、列表与字典操作文件读写操作（读写图像和数据文件） 练习任务：写一个Python脚本，读取一个图像并保存灰度图像。 import cv2 img cv2.im…...

编程日记 2025/9/21 11:20:52

计算机网络之网络层（网络层的功能，异构网络互联，路由与转发，SDN基本概念，拥塞控制）

计算机网络之网络层网络层（Network Layer）是计算机网络体系结构中至关重要的一层，它位于数据链路层（Data Link Layer）和传输层（Transport Layer）之间，主要负责数据包从源主机到目的…...

编程日记 2025/9/20 18:51:26

利用雪花算法+Redis 自增 ID，生成订单号

在我们的项目中，我们需要定义一些全局唯一的 ID，比如订单号，支付单号等等。这些ID有以下几个基本要求： 1、不能重复 2、不可被预测 3、能适应分库分表为了生成一个这样一个全局的订单号，自定义了一个分布式 ID …...

编程日记 2025/9/13 9:04:00

第35次CCF计算机软件能力认证 python 参考代码

题目列表1. 密码2. 字符串变换3. 补丁应用4. 通讯延迟5. 木板切割题目列表第35次CCF计算机软件能力认证 1. 密码 n = int(input()) for _ in range(n):s =...

编程日记 2025/9/21 4:18:18

【探商宝】：大数据与AI赋能，助力中小企业精准拓客引

引言：在数据洪流中，如何精准锁定商机？ 在竞争激烈的商业环境中，中小企业如何从海量信息中快速筛选出高价值客户？如何避免无效沟通，精准触达目标企业？ 探商宝——一款基于大数据与AI技术的企业信…...

编程日记 2025/9/13 9:03:56

npm 私服使用介绍

一、导读本文主要介绍 npm 私服的使用，至于 npm 私服搭建的过程，可以看本人之前的文章《Docker 部署 verdaccio 搭建 npm 私服》二、前置条件 npm私服地址：http://xxx.xxx.xxx.xxx:port/ 三、本地 npm 源切换使用nrm，可以方…...

编程日记 2025/9/16 7:55:01

【Python 打造高效文件分类工具】

【Python】打造高效文件分类工具一、代码整体结构二、关键代码解析（一）初始化部分（二）界面创建部分（三）核心功能部分（四）其他辅助功能部分三、运行与使用四、示图五、作者有话说 …...

编程日记 2025/9/13 9:03:52

水务+AI应用探索（一）| FastGPT+DeepSeek 本地部署

在当下的科技浪潮中，AI 无疑是最炙手可热的焦点之一，其强大的能力催生出了丰富多样的应用场景，广泛渗透到各个行业领域。对于水务行业而言，AI 的潜力同样不可估量。为了深入探究 AI 在水务领域的实际应用成效，切实掌握…...

编程日记 2025/9/13 9:03:50

基于若依开发的工程项目管理系统开源免费，用于工程项目投标、进度及成本管理的OA 办公开源系统，非常出色！

一、简介今天给大家推荐一个基于 RuoYi-Flowable-Plus 框架二次开发的开源工程项目管理系统，专为工程项目的投标管理、项目进度控制、成本管理以及 OA 办公需求设计。该项目结合了 Spring Boot、Mybatis、Vue 和 ElementUI 等技术栈，提供了丰富的功能…...

编程日记 2025/9/13 9:03:48

设计模式-工厂模式

设计模式 - 工厂模式工厂模式（Factory Pattern）是一种创建型设计模式，它通过定义一个用于创建对象的接口，让子类决定实例化哪一个类，从而使得一个类的实例化延迟到子类。工厂模式通过将对象创建的逻辑抽象化&#xf…...

编程日记 2025/9/20 22:21:43

基于opencv的HOG+角点匹配教程

1. 引言在计算机视觉任务中，特征匹配是目标识别、图像配准和物体跟踪的重要组成部分。本文介绍如何使用 HOG（Histogram of Oriented Gradients，方向梯度直方图） 和角点检测（Corner Detection） 进行特征匹…...

编程日记 2025/9/20 9:37:30

《深度学习》——调整学习率和保存使用最优模型

调整学习率在使用 PyTorch 进行深度学习训练时，调整学习率是一个重要的技巧，合适的学习率调整策略可以帮助模型更好地收敛。 PyTorch 提供了多种调整学习率的方法，下面将详细介绍几种常见的学习率调整策略及实例代码： torch.opt…...

编程日记 2025/9/21 3:12:34

Ubuntu22.04配置cuda/cudnn/pytorch

Ubuntu22.04配置cuda/cudnn/pytorch 安装cuda官网下载.run文件并且安装/etc/profile中配置cuda环境变量 cudnn安装官网找cuda版本对应的cudnn版本下载复制相应文件到系统文件中安装pytorch官网找cuda对应版本的pytorchpython代码测试pytorch-GPU版本安装情况安装cuda 官网下…...

编程日记 2025/9/13 6:31:17

通俗理解-L、-rpath和-rpath-link编译链接动态库

一、参考资料链接选项 rpath 的应用和原理 | BewareMyPower的博客使用 rpath 和 rpath-link 确保 samba-util 库正确链接-CSDN博客编译参数-Wl和rpath的理解_-wl,-rpath-CSDN博客 Using LD, the GNU linker - Options Directory Options (Using the GNU Compiler Colle…...

编程日记 2025/9/19 12:20:15

【Golang】GC探秘/写屏障是什么？

之前写了一篇【Golang】内存管理 ，有了很多的阅读量，那么我就接着分享一下Golang的GC相关的学习。由于Golang的GC机制一直在持续迭代，本文叙述的主要是Go1.9版本及以后的GC机制，该版本中Golang引入了混合写屏障大幅度地优化了S…...

编程日记 2025/9/13 6:31:13

Linux(Centos 7.6)命令详解：head

1.命令作用将每个文件的前10行打印到标准输出(Print the first 10 lines of each FILE to standard output) 2.命令语法 Usage: head [OPTION]... [FILE]... 3.参数详解 OPTION: -c, --bytes[-]K，打印每个文件的前K字节-n, --lines[-]，打印前K行而…...

编程日记 2025/9/18 7:32:39

【工具变量】上市公司网络安全治理数据(2007-2023年）

网络安全是国家安全体系的重要组成部分，是确保金融体系稳定运行、维护市场信心的关键。网络安全治理是指通过一系列手段和措施，维护网络安全，保护网络环境的稳定和安全，旨在确保公司网络系统免受未经授权的访问、攻击和破坏&#…...

编程日记 2025/9/13 6:31:09

watermark解释

在 Apache Flink 中，Watermark 是处理事件时间（Event Time）的核心机制，用于解决流处理中因数据乱序或延迟到达而导致的窗口计算不准确问题。理解 Watermark 的关键在于以下几点： 1. 事件时间 vs. 处理时间事件时间&…...

编程日记 2025/9/18 20:23:20

Transformer 模型介绍（四）——编码器 Encoder 和解码器 Decoder

上篇中讲完了自注意力机制 Self-Attention 和多头注意力机制 Multi-Head Attention，这是 Transformer 核心组成部分之一，在此基础上，进一步展开讲一下编码器-解码器结构（Encoder-Decoder Architecture） Transformer 模…...

编程日记 2025/9/13 6:31:05

Linux安装Minio

1、下载rpm包 2、rpm 安装 rpm -ivh xx.rpm3、通过查看minion状态，查看其配置文件位置 systemctl start minio可以根据情况自定义修改配置文件内容，这里暂时不做修改 4、创建数据文件和日志文件，一般在/usr/local/ 5、编写启动脚本 #!/bi…...

编程日记 2025/9/13 6:31:04

JAVA EE初阶 - 预备知识（三）

一、中间件中间件是一种处于操作系统和应用程序之间的软件，它能够为分布式应用提供交互、资源共享、数据处理等功能，是现代软件架构中不可或缺的一部分。下面从多个方面为你详细介绍中间件： 定义与作用定义：中间件是连接两个或…...

编程日记 2025/9/13 6:31:01

百度热力图数据获取，原理，处理及论文应用6

目录 0、数据简介0、示例数据1、百度热力图数据日期如何选择1.1、其他实验数据的时间1.2、看日历1.3、看天气 2、百度热力图几天够研究？部分文章统计3、数据原理3.1.1 ** 这个比较重要，后面还会再次出现。核密度的值怎么理解？**3.1.2 Csv->…...

编程日记 2025/9/14 20:37:49

tcp连接的11种状态及常见问题。

tcp链接整体流程，如下图所示： TCP协议在连接的建立和终止过程中涉及11种状态，这些状态反映了连接的不同阶段。以下是每种状态的详细说明： 1. CLOSED 初始状态，表示没有活动的连接或连接已完全关闭。当应用程序关闭连…...

编程日记 2025/9/21 11:08:52

宝塔面板开始ssl后,使用域名访问不了后台管理

宝塔面板后台开启ssl访问后，用的证书是其他第三方颁发的证书再使用域名/xxx 的形式：https://域名:xxx/xxx 访问后台，结果出现如下，不管使用 http 还是 https 的路径访问都进不后台管理这个时候可以使用 https://ip/xxx 的方式来…...

编程日记 2025/9/13 0:11:15

5.日常英语笔记

sprouted tater 发芽的土豆 fluid 液体，流体 The doctor recommended drinking plenty of fluids 医生建议多喝流质适应新环境 adapt to the new environment adjust to the new surroundings get used to the new setting accommodate oneself to the new circu…...

编程日记 2025/9/21 1:54:23

利用工业相机及多光谱图像技术助力医疗美容皮肤AI检测方案

随着年轻人对皮肤的管理要求越来越高，“科技护肤”已成为线下医疗美业护肤行业转型升级之趋势。如何利用先进的图像识别技术和AI大数据分析，为医生和消费者提供个性化的皮肤诊断分析和护肤建议，利用工业相机及多光谱成像技术完美实现这一可能…...

编程日记 2025/9/13 0:11:11

qt QOpenGLTexture详解

1. 概述 QOpenGLTexture 是 Qt5 提供的一个类，用于表示和管理 OpenGL 纹理。它封装了 OpenGL 纹理的创建、分配存储、绑定和设置像素数据等操作，简化了 OpenGL 纹理的使用。 2. 重要函数构造函数： QOpenGLTexture(const QImage &image,…...

编程日记 2025/9/13 0:11:09

【Zookeeper如何实现分布式锁？】

Zookeeper如何实现分布式锁？一、ZooKeeper分布式锁的实现原理二、ZooKeeper分布式锁的实现流程三、示例代码四、总结一、ZooKeeper分布式锁的实现原理 ZooKeeper是一个开源的分布式协调服务，它提供了一个分布式文件系统的接口，可以用来存储和管理分布式系统的配置信息。 …...

编程日记 2025/9/17 19:36:15

mysql 学习16 视图，存储过程，存储函数，触发器

视图， 存储过程， 存储函数触发器...

编程日记 2025/9/15 5:39:03

（前端基础）HTML（一）

前提 W3C:World Wide Web Consortium（万维网联盟） Web技术领域最权威和具有影响力的国际中立性技术标准机构其中标准包括：机构化标准语言（HTML、XML） 表现标准语言（CSS） 行为标准&#xf…...

编程日记 2025/9/13 0:11:01

go设置镜像代理

前言在 Go 开发中，如果直接从官方源（https://proxy.golang.org）下载依赖包速度较慢，可以通过设置镜像代理来加速依赖包的下载。以下是增加 Go 镜像代理的详细方法： 一、设置 Go 镜像代理 1. 使用环境变量设置代理…...

编程日记 2025/9/13 0:10:59

matlab数据处理：创建网络数据

% 创建网格数据 [X, Y] meshgrid(x_data, y_data); 如 x_data [1 2 3 4] X 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 XY_data [X(:), Y(:)]; % 将X和Y合并成一个向量 X(:)表示将矩阵排成一列 XY_data 1 …...

编程日记 2025/9/13 0:10:55

在企业内部私有化部署 DeepSeek 或其他 AI 大模型时，基于一般场景的最低硬件配置建议

1. 中央处理器（CPU） 核心数：至少 4 核心，支持多线程任务。频率：至少 2.5 GHz。CPU 型号：Intel Core i5 或更高（如 i7 或 i9），或 AMD Ryzen 5000 系列以上。多核支持&…...

编程日记 2025/9/17 13:22:59

DeepSeek 助力 Vue 开发：打造丝滑的颜色选择器（Color Picker）

前言：哈喽，大家好，今天给大家分享一篇文章！并提供具体代码帮助大家深入理解，彻底掌握！创作不易，如果能帮助到大家或者给大家一些灵感和启发，欢迎收藏关注哦 💕 目录 Deep…...

编程日记 2025/9/20 4:36:07

【ArcGIS Pro二次开发】(87)：样式_Style的用法

.Stylx类型的文件即为样式库文件，保存了符号样式。 1、根据名字获取当前工程中的style //获取当前工程中的所有style var ProjectStyles Project.Current.GetItems<StyleProjectItem>();//根据名字找出指定的style StyleProjectItem style ProjectStyles.F…...

编程日记 2025/9/16 8:42:46

Jetson Agx Orin平台JP6.0-r36.3版本修复了vi模式下的原始图像损坏（线条伪影）

1.问题描述这是JP-6.0 GA/ l4t-r36.3.0的一个已知问题通过vi模式捕获的图像会导致异常线条参考下面的快照来演示这些线伪影这个问题只能通过VI模式进行修复，不应该通过LibArgus看到。此外，这是由于内存问题。由于upstream已经将属性名称更改为“dma-noncoherent”…...

编程日记 2025/9/13 6:30:55

nlp|微调大语言模型初探索(2)，训练自己的聊天机器人

前言上篇文章记录了具体的微调语言大模型步骤，以及在微调过程中可能遇见的各种报错，美中不足的是只是基于开源数据集的微调，今天来记录一下怎么基于自己的数据集去微调大语言模型，训练自己的智能机器人！！&…...

编程日记 2025/9/18 16:23:38

如何搭建Wi-Fi CVE漏洞测试环境：详细步骤与设备配置

引言随着Wi-Fi技术的普及，Wi-Fi网络成为了现代通信的重要组成部分。然而，Wi-Fi网络的安全性始终是一个备受关注的话题。通过漏洞扫描和安全测试，网络管理员可以及早发现并修复Wi-Fi设备中存在的安全隐患。本篇文章将详细介绍如何搭建Wi-Fi …...

编程日记 2025/9/19 22:01:02

【三维重建】FeatureGS:特征值优化的几何精度和伪影减少3DGS的重构

文章：https://arxiv.org/pdf/2501.17655 标题：FeatureGS: Eigenvalue-Feature Optimization in 3D Gaussian Splatting for Geometrically Accurate and Artifact-Reduced Reconstruction 文章目录摘要一、引言二、相关工作：3D特征三、算法3…...

编程日记 2025/9/21 0:59:31