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

Algorithm:河内之塔

1. 说明

河内之塔(Towers of Hanoi)是法国人 M.Claus(Lucas)于1883年从泰国带至法国的,河内为越战时北越的首都,即现在的胡志明市;1883年法国数学家 Edouard Lucas 曾提及这个故事,据说创丗纪时 Benares 有一座波罗教塔,是由三支钻石棒(Pag)所支撑,开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘(Disc),并命令僧侣将所有的金盘从第一根石棒移至第三根石棒,且搬运过程中遵守大盘子在小盘子之下的原则,若每日仅搬一个盘子,则当盘子全数搬运完毕之时,此塔将毁损,而也就是世界末日来临之时。

2. 解法

河内之塔是一个经典的递归问题。在这个问题中,目标是将所有盘子从起始棒(A)移动到目标棒(C),同时满足以下规则:
  • 每次只能移动一个盘子。
  • 不能将较大的盘子放在较小的盘子上。
  • 可以使用一个辅助棒(B)。

2.1 算法分析

  • 如果只有一个盘子,直接从A移动到C。
  • 如果有多个盘子:
总移动次数是:2^n - 1其中,n是盘子的数量。

2.2 C语言实现

#include <stdio.h> // 递归函数实现河内之塔 void hanoi(int n, char from, char to, char aux) { if (n == 1) { // 基本情况:只有一个盘子 printf("Move disk 1 from %c to %c\n", from, to); return; } // 将 n-1 个盘子从 from 移到 aux hanoi(n - 1, from, aux, to); // 将第 n 个盘子从 from 移到 to printf("Move disk %d from %c to %c\n", n, from, to); // 将 n-1 个盘子从 aux 移到 to hanoi(n - 1, aux, to, from); } int main() { int n; // 盘子的数量 printf("Enter the number of disks: "); scanf("%d", &n); printf("The sequence of moves:\n"); hanoi(n, 'A', 'C', 'B'); // A 是起点,C 是目标点,B 是辅助点 return 0; }

2.3 示例运行

输入盘子数量为3:
Enter the number of disks: 3 The sequence of moves: Move disk 1 from A to C Move disk 2 from A to B Move disk 1 from C to B Move disk 3 from A to C Move disk 1 from B to A Move disk 2 from B to C Move disk 1 from A to C

2.4 运行原理

以 n = 3 为例:
  • 将盘1和盘2移到辅助棒B:
  • 将盘3移到目标棒C。
  • 将盘1和盘2从辅助棒B移到目标棒C:
总共7次移动,符合公式 2^3 - 1 = 7,具体图示如下所示:

2.5 注意事项

  • 此代码适用于任何正整数的盘子数量,但盘子数量较大时,递归深度可能超过栈的限制。
  • 时间复杂度为 O(2^n),因此对大盘子数量的计算效率较低。

3. 附件

怎么判断”河内之塔“是个递归问题呢?

3.1 问题的分解特性

递归问题通常具有以下特征:一个大问题可以分解为若干个结构相似的子问题,且这些子问题的规模逐渐减小。我们可以把“河内之塔”问题这样分解,具体如下:
  • 要把所有盘子从A移动到C,首先需要将除了最大的盘子之外的盘子从A移动到B,然后将最大的盘子从A移动到C,最后将剩下的盘子从B移动到C。
  • 这个过程重复进行,直到只剩下一个盘子时,问题变得简单。

3.2 边界条件

递归算法需要明确的 基本情况(边界条件),也就是在递归中什么时候停止。
  • 在“河内之塔”中,当只有一个盘子时(即 n = 1),移动问题非常简单,直接将该盘子从起始棒移动到目标棒。

3.3 递归调用的结构

递归问题的关键是通过递归调用处理更小规模的子问题。在“河内之塔”中,问题的递归结构如下:
  • 将 n-1 个盘子从起始棒移动到辅助棒。
  • 将第 n 个盘子(即最大盘子)从起始棒移动到目标棒。
  • 将 n-1 个盘子从辅助棒移动到目标棒。
这种结构显然是递归的,因为它涉及到将一个较大的问题分解为两个相似的小问题,并通过递归方式处理这些小问题。

3.4 数学归纳法的验证

递归问题的一个常见特性是通过 数学归纳法证明其正确性。在“河内之塔”问题中,可以使用数学归纳法来证明:
  • 当 n = 1 时,移动一个盘子显然是正确的。
  • 假设对于 n = k 时,已经正确实现了将 k 个盘子从起始棒移动到目标棒。
  • 对于 n = k+1,我们可以将问题分解为两个部分:首先递归地将 k 个盘子从起始棒移动到辅助棒,然后将第 k+1 个盘子(最大盘子)从起始棒移动到目标棒,最后递归地将 k 个盘子从辅助棒移动到目标棒。
通过归纳法,我们可以确认这个过程适用于任意盘子的数量,证明了这是一个递归问题。

3.5 总结

判断“河内之塔”是递归问题的核心依据是:
  • 问题具有分解特性:大问题可以分解为更小的相同问题。
  • 存在明确的基本情况,当问题规模为1时可以直接求解。
  • 问题通过递归调用来逐步解决每个子问题,直到最小问题得到解决。
这些特点使得“河内之塔”可以非常自然地使用递归方法来解决。

相关文章:

Algorithm:河内之塔

1. 说明 河内之塔&#xff08;Towers of Hanoi&#xff09;是法国人 M.Claus&#xff08;Lucas&#xff09;于1883年从泰国带至法国的&#xff0c;河内为越战时北越的首都&#xff0c;即现在的胡志明市&#xff1b;1883年法国数学家 Edouard Lucas 曾提及这个故事&#xff0c;据…...

集中管理与实时审计:构建Linux集群(1300台服务器)日志平台的最佳实践

简介 随着企业IT基础设施的不断扩大&#xff0c;Linux服务器的数量也日益增多&#xff0c;传统的单机日志管理方式已无法满足对日志数据集中管理、审计和分析的需求。尤其是在大型集群环境中&#xff0c;如何高效地收集、存储和分析日志成为了一项重要的技术挑战。 背景 在实…...

在Scala中Array不可变的学习

package gjhs114import scala.collection.mutable.ArrayBuffer object Arrray114 {// 不可变数组&#xff1a;Array// def main(args: Array[String]): Unit {1 创建不可变数组// val arr1 Array(1,2,3)//2 访问.数组名&#xff08;下标&#xff09;。下标是从0开始到…...

vue3+vite 批量引入组件动态使用

import { ref, reactive, toRaw, markRaw, defineAsyncComponent, onMounted } from vue import type { Component } from vue// vue3vite 批量引入组件动态使用 const modules import.meta.glob<Component>(./details/*.vue) // 明确指定导入的模块类型为Component con…...

设计模式——方法链or流式接口

方法链或流式接口是一种编程模式或设计模式。核心思想是通过返回对象自身的应用&#xff0c;使得可以在一个表达式中连续调用多个方法。 c中实现这种模式 1.基本语法规则 &#xff08;1&#xff09;每个可链接的方法都返回对象自身的引用&#xff08;通常是*this&#xff09…...

JAVA OPCUA 服务端开发,客户端连接会话监听和订阅事件监听

前言 关于使用milo开源库,开发opc ua服务器,有网友咨询如何设置服务端如何监听客户端的连接或断开事件,如何监听客户端发起订阅事件的代码实现,于是我完善了这部分的空缺整理整了这篇教程,希望能解决有同样需求,但是遇到困难的网友!因为milo没有官方文档的教程且网上详…...

pytest相关总结

1.pytest -v -s -v将测试用例名称和用例中的输出进行展示&#xff0c;将每条用例脚本的内容逐行进行结果展示&#xff1b; -s 参数是为了显示用例执行层级的打印信息 pytest使用总结笔记 - fengf233 - 博客园 2....

cin/cout的性能优化和缓冲区同步问题

目录 背景导入 问题 1.1ios::sync_with_stdio(false) 1.2为什么要解除C/C IO流同步? 1.3使用场景 2.1cin和cout的绑定关系 2.2为什么要解除绑定关系? 2.3注意事项 背景导入 大家可以先看一下这段背景知识;后面我会谈谈自己的理解; 1.在C中&#xff0c;标准输⼊输出流…...

redisson-spring-data与Spring-Data-Redis的版本关系问题

redisson-spring-boot-starter https://github.com/redisson/redisson/tree/master/redisson-spring-boot-starter https://github.com/redisson/redisson/tree/master/redisson-spring-data#spring-data-redis-integration 将 Redisson 与 Spring Boot 库集成。依赖于Spring…...

Puppeteer代理认证的最佳实践和示例

在现代网络环境中&#xff0c;代理服务器的使用越来越普遍&#xff0c;尤其是在数据抓取、网页自动化测试和网络监控等领域。Puppeteer作为一个流行的Node库&#xff0c;它提供了高级的API来控制Chrome或Chromium浏览器。在某些情况下&#xff0c;我们需要通过代理服务器来执行…...

js 字符串 只显示数字

1. 使用正则表达式的match方法 原理&#xff1a;正则表达式\d用于匹配一个或多个数字。match方法会在字符串中查找与正则表达式匹配的部分&#xff0c;并返回一个包含所有匹配结果的数组。示例代码&#xff1a; let str "abc123def456"; let numbers str.match(/…...

STM32标准库-FLASH

FLASH模仿EEPROM STM32本身没有自带EEPROM&#xff0c;但是自带了FLASH存储器。 STM32F103ZET6自带 1M字节的FLASH空间&#xff0c;和 128K64K的SRAM空间。 STM32F4 的 SPI 功能很强大&#xff0c;SPI 时钟最高可以到 37.5Mhz&#xff0c;支持 DMA&#xff0c;可以配置为 SPI协…...

PowerShell:查找并关闭打开的文件

Get-SmbOpenFile 打开 Windows PowerShell 并运行 Get-SmbOpenFile | Format-List 若要仅显示特定文件共享的连接&#xff0c;请使用 Where-Object 运行 Get-SmbOpenFile。 Get-SmbOpenFile | Where-Object Path -eq "C:\Data\" | Format-List Get-SmbSession 显…...

【AI系统】昇腾异构计算架构 CANN

昇腾异构计算架构 CANN 本文将介绍昇腾 AI 异构计算架构 CANN&#xff08;Compute Architecture for Neural Networks&#xff09;&#xff0c;这是一套为高性能神经网络计算需求专门设计和优化的架构。CANN 包括硬件层面的达芬奇架构和软件层面的全栈支持&#xff0c;旨在提供…...

STM32 HAL库开发学习3.STM32启动浅析

STM32 HAL库开发学习3.STM32启动浅析 一、STM32启动模式&#xff08;也称自举模式&#xff09;1. MSP与PC指针赋值2. F1系列的启动模式&#xff1a;3. F4系列启动模式4. F7系列启动模式5. H7系列启动模式 二、STM32启动过程1. MSP 栈顶地址2. PC值3. Reset_Handler4. 启动文件内…...

FakeLocation 1.3.5 BETA 提示校园跑漏洞修复解决

任务一 作者对此又进行了更新&#xff0c;在本次更新中&#xff0c;我们依旧使用hookvip进行破解 本次的更新&#xff0c;使得包名强制写入更加严重&#xff0c;之前靠一些方法已经无法阻止appconfigs.xml的文件的修改&#xff0c;而且使得验证加强&#xff0c;和云端加强&…...

Figma入门-约束与对齐

Figma入门-约束与对齐 前言 在之前的工作中&#xff0c;大家的原型图都是使用 Axure 制作的&#xff0c;印象中 Figma 一直是个专业设计软件。 最近&#xff0c;很多产品朋友告诉我&#xff0c;很多原型图都开始用Figma制作了&#xff0c;并且很多组件都是内置的&#xff0c…...

腾讯元宝深度搜索AI多线程批量生成TXT原创文章软件

腾讯元宝深度搜索AI多线程批量生成TXT原创文章软件说明&#xff1a; 腾讯元宝深度搜索AI&#xff1a;能够理解用户意图&#xff0c;对搜索结果进行提炼和总结&#xff0c;直接提供用户所需的答案或信息摘要&#xff0c;从而提升用户体验。 腾讯元宝深度搜索AI&#xff1a;通过…...

Git操作学习1

一、一些Linux相关指令 在当前目录下&#xff0c;创建文件并写入内容&#xff1a;echo "这是第一个文件">file1.txt 查看文件的内容&#xff1a; cat file1.txt 会显示&#xff1a;这是第一个文件 修改文件名&#xff1a;mv file.txt file4.txt 把file.txt修改…...

【计算机网络】细说IP

文章目录 概述IP地址的组成IP地址的分类IP地址的作用 分类一、A类IP地址二、B类IP地址三、C类IP地址四、D类IP地址五、E类IP地址 协议报文子网掩码一、定义与功能二、表示方法三、子网掩码与IP地址的关系四、子网掩码的设置与配置五、实例说明 IPv6一、定义与背景二、地址格式与…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...

Python实现简单音频数据压缩与解压算法

Python实现简单音频数据压缩与解压算法 引言 在音频数据处理中&#xff0c;压缩算法是降低存储成本和传输效率的关键技术。Python作为一门灵活且功能强大的编程语言&#xff0c;提供了丰富的库和工具来实现音频数据的压缩与解压。本文将通过一个简单的音频数据压缩与解压算法…...

深入浅出WebGL:在浏览器中解锁3D世界的魔法钥匙

WebGL&#xff1a;在浏览器中解锁3D世界的魔法钥匙 引言&#xff1a;网页的边界正在消失 在数字化浪潮的推动下&#xff0c;网页早已不再是静态信息的展示窗口。如今&#xff0c;我们可以在浏览器中体验逼真的3D游戏、交互式数据可视化、虚拟实验室&#xff0c;甚至沉浸式的V…...

今日行情明日机会——20250609

上证指数放量上涨&#xff0c;接近3400点&#xff0c;个股涨多跌少。 深证放量上涨&#xff0c;但有个小上影线&#xff0c;相对上证走势更弱。 2025年6月9日涨停股主要行业方向分析&#xff08;基于最新图片数据&#xff09; 1. 医药&#xff08;11家涨停&#xff09; 代表标…...