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

经典算法-----汉诺塔问题

前言

今天我们学习一个老经典的问题-----汉诺塔问题,可能在学习编程之前我们就听说过这个问题,那这里我们如何去通过编程的方式去解决这么一个问题呢?下面接着看。

在这里插入图片描述

汉诺塔问题

问题描述

这里是引用汉诺塔问题源自印度一个古老的传说,印度教的“创造之神”梵天创造世界时做了 3 根金刚石柱,其中的一根柱子上按照从小到大的顺序摞着 64 个黄金圆盘。梵天命令一个叫婆罗门的门徒将所有的圆盘移动到另一个柱子上,移动过程中必须遵守以下规则:
每次只能移动柱子最顶端的一个圆盘;
每个柱子上,小圆盘永远要位于大圆盘之上;

下面展示一个三个的汉诺塔解决过程,如下图所示:
在这里插入图片描述
在这里插入图片描述
其他情况:
在这里插入图片描述

解决思路(分治算法)

看上面这几个图,我们是否发现这么一个特点,要想把A柱子(起始柱)上的汉诺塔转移到C柱子(目标柱)上,而且还要满足汉诺塔的基本条件,那就把第三个柱子作为辅助柱(B柱),假设A柱子上有n个汉诺塔,这时候先把A柱子除了最下面的一层,其余的全部汉诺塔先放到B柱子上面,然后再把A柱子最下面的汉诺塔放到C柱子上,然后把B柱子上面的汉诺塔重新放回给A柱子当中(这个过程,C柱作为辅助柱子,B是起始柱,A是目标柱),这个过程就完成了一次放置,此时A柱子上面就剩下n-1个汉诺塔,再次重复以上的过程,最后就完成了汉诺塔的转移。

汉诺塔问题中,3 个圆盘至少需要移动 7 次,移动 n 的圆盘至少需要操作 2^n-1 次。

在汉诺塔问题中,当圆盘个数不大于 3 时,多数人都可以轻松想到移动方案,随着圆盘数量的增多,汉诺塔问题会越来越难。也就是说,圆盘的个数直接决定了汉诺塔问题的难度,解决这样的问题可以尝试用分治算法,将移动多个圆盘的问题分解成多个移动少量圆盘的小问题,这些小问题很容易解决,从而可以找到整个问题的解决方案。

代码实现(C语言)

#include<stdio.h>//打印移动的过程
void move(char x, char y) {printf("%c--->%c\n", x, y);
}//递归移动
void generate(int n,char a, char b, char c) {if (n == 0)return;	//如果移动完成了就返回,开始递归运算//第一个过程,先把A柱子上的前n-1个汉诺塔移到B柱子上,再把最底下的那个汉诺塔移动到C上//此时a是起始柱子,c是目标柱,b是辅助柱		a--->cgenerate(n - 1, a, c, b);move(a, c);//第二个过程,当第一个过程完成了之后,就要把B柱子上的n-1个汉诺塔移回A柱子,这就是整体一个分支过程//此时b是起始柱,a是目标柱,c是辅助柱		b--->agenerate(n - 1, b, a, c);
}int main() {int n;printf("输入汉诺塔个数:");scanf("%d", &n);generate(n, 'A', 'B', 'C');
}

运行结果如下:
在这里插入图片描述

好了,以上就是本期的全部内容了,这个汉诺塔是不是很有意思呢?你学会了吗?
分享一张壁纸:在这里插入图片描述

相关文章:

经典算法-----汉诺塔问题

前言 今天我们学习一个老经典的问题-----汉诺塔问题&#xff0c;可能在学习编程之前我们就听说过这个问题&#xff0c;那这里我们如何去通过编程的方式去解决这么一个问题呢&#xff1f;下面接着看。 汉诺塔问题 问题描述 这里是引用汉诺塔问题源自印度一个古老的传说&#x…...

博客之站项目测试报告

项目背景项目功能测试计划Bug总结升级自动化测试正常登录流程 项目背景 1&#xff1a;博客之站系统是采用前后端分离的方式来实现&#xff1b;使用MySQL、Redis数据库储存相关数据&#xff1b;同时部署到云服务器上。 2&#xff1a;包含注册页、登录页、博客列表页、个人列表页…...

k8s晋级之管理容器的计算资源

概述 在 Kubernetes 中创建工作负载时&#xff0c;您可以为 Pod 中的每一个容器指定其所需要的内存&#xff08;RAM&#xff09;大小和 CPU 数量。如果这些信息被指定了&#xff0c;Kubernetes 调度器可以更好的决定将 Pod 调度到哪一个节点。对于容器来说&#xff0c;其所需要…...

计算机竞赛 深度学习火车票识别系统

文章目录 0 前言1 课题意义课题难点&#xff1a; 2 实现方法2.1 图像预处理2.2 字符分割2.3 字符识别部分实现代码 3 实现效果4 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 图像识别 火车票识别系统 该项目较为新颖&#xff0c;适…...

盒子阴影和网页布局

盒子阴影 box-shadow: 10px 10px 10px 4px rgba(0,0,0,.3);//最后一个是透明度 传统网页布局的三种方式 标准流 就是按照规定好的默认方式排列 1.块级元素&#xff1a;div、hr、p、h1~h2、ul、ol、dl、form、table 行内元素会按照书顺序&#xff0c;从左到右顺序排列&#…...

Ph.D,一个Permanent head Damage的群体

一个群体 Permanent head Damage 的博士生群体 Permanent head Damage Ph.D 博士生一年级的同学们&#xff0c;不要担忧或高兴得太早&#xff0c;抱歉你们还没有经历Qualification——预备考试&#xff0c;你们暂且不能被称为博士&#xff0c;只能称自己是要努力成为博士预备…...

visual studio禁用qt-vsaddin插件更新

visual studio里qt-vsaddin插件默认是自动更新的&#xff0c;由于qt-vsaddin插件新版本的操作方式与老版本相差较大&#xff0c;且新版本不稳定&#xff0c;容易出Bug&#xff0c;所以需要禁用其自动更新&#xff0c;步骤如下&#xff1a;     点击VS2019菜单栏上的【扩展】–…...

Docker通过Dockerfile创建Redis、Nginx--详细过程

创建Nginx镜像 我们先创建一个目录&#xff0c;在目录里创建Dockerfile [rootdocker-3 ~]# mkdir mynginx [rootdocker-3 ~]# cd mynginx [rootdocker-3 ~]# vim Dockerfile Dockerfile的内容 FROM daocloud.io/library/centos:7 RUN buildDepsreadline-devel pcre-devel o…...

关于使用 uniapp Vue3 开发分享页面 语法糖 setup 开发获取ref踩坑

上代码 前端代码 <!-- 分享弹出 --> <uni-popup ref"share" type"share" safeArea backgroundColor"#fff"><uni-popup-share></uni-popup-share> </uni-popup>处理函数 import {onNavigationBarButtonTap} from…...

Springboot+vue的时间管理系统(有报告)。Javaee项目,springboot vue前后端分离项目。

演示视频&#xff1a; Springbootvue的时间管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot vue前后端分离项目。 项目介绍&#xff1a; 本文设计了一个基于Springbootvue的前后端分离的时间管理系统&#xff0c;采用M&#xff08;model&#xff0…...

企业如何实时监管员工聊天转账行为

你还在担心员工飞单、私单吗&#xff1f; 你还在担心员工辱骂删除客户吗&#xff1f; 你还在担心员工离职会带走公司客户吗&#xff1f; 你还在担心员工工作不认真&#xff0c;工作量无法统计吗&#xff1f; 。。。。。。。。 在当今互联网时代&#xff0c;企业微信的应用已…...

2.2.3.1vim + ctags + cscope + taglist

在window下,我们一般用Source Insight来查看代码而在linux下,使用vim来查看代码,vim是一个简单的文本浏览/编辑器,它可以通过插件的形式,搭建一个完全的类Source Insight环境,通过快捷键的形式,快速查看、定位变量/函数,本文就是基于vim,通过ctags+cscope+taglist+Ner…...

JAVA面经整理(4)

一)Volitaile关键字的作用: 1)保证多线程环境下共享变量的可见性&#xff0c;对于一个线程对于一个共享表变量的修改&#xff0c;其他线程可以立即看到修改之后的共享变量的值 2)可以增加内存屏障来放置多个指令之间的重排序 volatile的使用:常常用于一写多读的情况下&#xff…...

Python3数据科学包系列(一):数据分析实战

Python3中类的高级语法及实战 Python3(基础|高级)语法实战(|多线程|多进程|线程池|进程池技术)|多线程安全问题解决方案 Python3数据科学包系列(一):数据分析实战 Python3数据科学包系列(二):数据分析实战 认识下数据科学中数据处理基础包: (1)NumPy 俗话说: 要学会跑需先…...

【LittleXi】【MIT6.S081-2020Fall】Lab: locks

【MIT6.S081-2020Fall】Lab: locks 【MIT6.S081-2020Fall】Lab: locks内存分配实验内存分配实验准备实验目的1. 举一个例子说明修改前的**kernel/kalloc.c**中如果没有锁会导致哪些进程间竞争(races)问题2. 说明修改前的kernel/kalloc.c中锁竞争contention问题及其后果3. 解释a…...

图像压缩:Transformer-based Image Compression with Variable Image Quality Objectives

论文作者&#xff1a;Chia-Hao Kao,Yi-Hsin Chen,Cheng Chien,Wei-Chen Chiu,Wen-Hsiao Peng 作者单位&#xff1a;National Yang Ming Chiao Tung University 论文链接&#xff1a;http://arxiv.org/abs/2309.12717v1 内容简介&#xff1a; 1&#xff09;方向&#xff1a;…...

C++ 类和对象篇(四) 构造函数

目录 一、概念 1. 构造函数是什么&#xff1f; 2. 为什么C要引入构造函数&#xff1f; 3. 怎么用构造函数&#xff1f; 3.1 创建构造函数 3.2 调用构造函数 二、构造函数的特性 三、构造函数对成员变量初始化 0. 对构造函数和成员变量分类 1. 带参构造函数对成员变量初始化 2. …...

Swing程序设计(5)绝对布局,流布局

文章目录 前言一、布局管理器二、介绍 1.绝对布局2.流布局总结 前言 Swing窗体中&#xff0c;每一个组件都有大小和具体的位置。而在容器中摆放各种组件时&#xff0c;很难判断其组件的具体位置和大小。即一个完整的界面中&#xff0c;往往有多个组件&#xff0c;那么如何将这…...

linux基础知识之文件系统 df/du/fsck/dump2fs

du du [选项][目录或者文件名] -a 显示每个子文件等磁盘占用量&#xff0c;默认只统计子目录的磁盘占用量 -h 使用习惯单位显示磁盘占用量&#xff0c;如KB&#xff0c;MB或者GB -s 统计总占用量&#xff0c;不列出子目录和文件占用量 面向文件 du -a 16 ./.DS_Store 8 ./requi…...

华为云云耀云服务器L实例评测|Elasticsearch的Docker版本的安装和参数设置 端口开放和浏览器访问

前言 最近华为云云耀云服务器L实例上新&#xff0c;也搞了一台来玩&#xff0c;期间遇到各种问题&#xff0c;在解决问题的过程中学到不少和运维相关的知识。 本篇博客介绍Elasticsearch的Docker版本的安装和参数设置&#xff0c;端口开放和浏览器访问。 其他相关的华为云云…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...

阿里云Ubuntu 22.04 64位搭建Flask流程(亲测)

cd /home 进入home盘 安装虚拟环境&#xff1a; 1、安装virtualenv pip install virtualenv 2.创建新的虚拟环境&#xff1a; virtualenv myenv 3、激活虚拟环境&#xff08;激活环境可以在当前环境下安装包&#xff09; source myenv/bin/activate 此时&#xff0c;终端…...