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

这篇具有很好参考价值的文章主要介绍了经典算法-----汉诺塔问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

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

经典算法-----汉诺塔问题,数据结构与算法,算法,c语言,汉诺塔,分治算法,递归

汉诺塔问题

问题描述

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

下面展示一个三个的汉诺塔解决过程,如下图所示:
经典算法-----汉诺塔问题,数据结构与算法,算法,c语言,汉诺塔,分治算法,递归
经典算法-----汉诺塔问题,数据结构与算法,算法,c语言,汉诺塔,分治算法,递归
其他情况:
经典算法-----汉诺塔问题,数据结构与算法,算法,c语言,汉诺塔,分治算法,递归

解决思路(分治算法)

看上面这几个图,我们是否发现这么一个特点,要想把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--->c
	generate(n - 1, a, c, b);
	move(a, c);

	//第二个过程,当第一个过程完成了之后,就要把B柱子上的n-1个汉诺塔移回A柱子,这就是整体一个分支过程
	//此时b是起始柱,a是目标柱,c是辅助柱		b--->a
	generate(n - 1, b, a, c);
}

int main() {
	int n;
	printf("输入汉诺塔个数:");
	scanf("%d", &n);
	generate(n, 'A', 'B', 'C');
}

运行结果如下:
经典算法-----汉诺塔问题,数据结构与算法,算法,c语言,汉诺塔,分治算法,递归

好了,以上就是本期的全部内容了,这个汉诺塔是不是很有意思呢?你学会了吗?
分享一张壁纸:经典算法-----汉诺塔问题,数据结构与算法,算法,c语言,汉诺塔,分治算法,递归文章来源地址https://www.toymoban.com/news/detail-728671.html

到了这里,关于经典算法-----汉诺塔问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构(五)数据结构与算法中的经典题

    本文是在原本数据结构与算法闯关的基础上总结得来,加入了自己的理解和部分习题讲解。至此数据结构介绍已完结,后续会把数据结构算法题系列更完。 原活动链接 邀请码: JL57F5 根据要求完成题目 Q1. (单选)以下哪些数据结构支持随机访问? A. 数组 B. 单链表 C. 双向链表

    2024年01月20日
    浏览(42)
  • 【数据结构与算法】十大经典排序算法-希尔排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 希尔排序是一种插入排序的改进版本,旨在解决插入排序在处理大规模数据时的效率问题。通过将数组分为多个子序列并对

    2024年02月12日
    浏览(75)
  • 【数据结构与算法】十大经典排序算法-插入排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 插入排序(Insertion Sort)是一种简单直观的排序算法,其基本思想是将一个记录插入到已排好序的有序序列中,直到所有记录

    2024年02月13日
    浏览(80)
  • 【数据结构与算法】十大经典排序算法-冒泡排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌴 掘金 :HelloCode 🌞 知乎 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 冒泡排序(Bubble Sort)是一种简单的排序算法,它通过重复地交换相邻元素的位置来将最大(或最小)的元素逐步“冒泡”到

    2024年02月14日
    浏览(69)
  • 【数据结构与算法】十大经典排序算法-快速排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 快速排序(Quick Sort)是一种高效的排序算法,是对冒泡排序的优化。它采用分治法(Divide and Conquer)的思想,将待排序序列

    2024年02月13日
    浏览(62)
  • 数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。

    最短路径的算法有两个, Dijkstra算法 和 Floyd算法 。 Dijkstra算法 解决的是 单源 最短路径问题 。 Floyd算法解决的是 多源 最短路径问题,并且可以处理负权图 。 今天要讲的就是Dijkstra算法。 加: feng--Insist (大写的i),进java交流群讨论互联网+技术。可索要PPT等资料。 其他资料

    2024年02月11日
    浏览(51)
  • 数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)

    目录 问题描述  解题思路 伪代码  总体算法 DFS算法 伪代码解读 总体算法 DFS算法 具体实现(C语言) 在老电影“007之生死关头”(Live and Let Die)中有一个情节,007被毒贩抓到一个鳄鱼池中心的小岛上,他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄鱼的大脑

    2024年02月05日
    浏览(73)
  • 200个经典面试题(算法思想+数据结构)_1

    1. 爬楼梯 70. Climbing Stairs (Easy) 题目描述:有 N 阶楼梯,每次可以上一阶或者两阶,求有多少种上楼梯的方法。 定义一个数组 dp 存储上楼梯的方法数(为了方便讨论,数组下标从 1 开始),dp[i] 表示走到第 i 个楼梯的方法数目。 第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步

    2024年02月13日
    浏览(42)
  • 【数据结构与算法】:10道链表经典OJ

    思路1:遍历原链表,将 val 所在的节点释放掉。(太麻烦) 思路2:创建新链表,再遍历原链表,找到不为 val 的节点尾插到新链表。 思路1代码实现如下: 注意: 1.当链表为空时,直接返回NULL即可。 2.当尾插上最后一个有效节点时,此时它的 next 可能还与最后一个节点相链接,

    2024年04月14日
    浏览(36)
  • 【Elacticsearch】 原理/数据结构/面试经典问题整理

    对Elacticsearch 原理/数据结构/面试经典问题整理的文章; 映射 | Elasticsearch: 权威指南 | Elastic 目录 Elacticsearch介绍 原理 建立索引原理 查询索引原理 更新索引原理 删除索引原理 分片副本机制,集群发现选举机制 ,负载机制,容错机制,扩容机制 数据类型 数据结构 先介绍倒排

    2024年02月10日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包