当前位置: 首页 > 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;端口开放和浏览器访问。 其他相关的华为云云…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关

在水泥厂的生产流程中&#xff0c;工业自动化网关起着至关重要的作用&#xff0c;尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关&#xff0c;为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多&#xff0c;其中不少设备采用Devicenet协议。Devicen…...