【C语言】汉诺塔 —— 详解

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

【C语言】汉诺塔 —— 详解,C语言学习,c语言,开发语言,学习,汉诺塔

一、介绍

汉诺塔(Tower of Hanoi),又称河内塔,是一个源于印度古老传说的益智玩具。大焚天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。 大焚天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

面试题 08.06. 汉诺塔问题 - 力扣(LeetCode)


二、问题描述

有 A,B,C 三根柱子,A 上面有 n 个盘子,我们想把 A 上面的盘子移动到 C 上,但是必须要满足以下三个条件:

  • 每次只能移动一个盘子;
  • 盘子只能从柱子顶端滑出移到下一根柱子;
  • 盘子只能叠在比它大的盘子上。

【C语言】汉诺塔 —— 详解,C语言学习,c语言,开发语言,学习,汉诺塔


三、解题思路

这是一道递归方法的经典题目。

1、如果 n = 1,只有一个盘子,那么就直接将它从 A 移到 C 上

2、如果 n = 2,这时我们就需要借助 B,因为小盘子必须时刻都在大盘子上面,共需要 4 步

【C语言】汉诺塔 —— 详解,C语言学习,c语言,开发语言,学习,汉诺塔


3、如果 n > 2,思路和上面是一样的。我们将 n 个盘子看成两个部分,一部分有 1 个盘子,另一部分有 n-1 个盘子

【C语言】汉诺塔 —— 详解,C语言学习,c语言,开发语言,学习,汉诺塔

可是,那 n-1 个盘子是如何从 A 移动到 B 再移动到 C 的呢? 

将最初的 n 个盘子从 A 移到 C 的问题,转化成了将 n-1 个盘子从 A 移到 C 的问题, 以此类推,直至转化成 1 个盘子的问题时,这个问题也就解决了。这里利用了分治的思想。

  1. 当 n = 1 时,直接将盘子从 A 移到 C 上;
  2. 当 n > 1 时,
  • 先把上面的 n-1 个盘子从 A 借助 C 移动到 B(化为子问题,进行递归);
  • 再将 A 上最后一个盘子从 A →C;
  • 再将 B 上 n - 1 个盘子从 B 借助 A 移动到 C(化为子问题,进行递归)。

四、代码

#include<stdio.h>

void move(char A, char C, int n)
{
	printf("把第%d个圆盘从%c——>%c\n", n, A, C);
}

void HanoiTower(char A, char B, char C, int n)
{
	if (n == 1)
	{
		move(A, C, n);
	}
	else
	{
		// 1.把A上n-1个圆盘从A柱借助C移动到B上
		HanoiTower(A, C, B, n - 1);

		// 2.将A最后一个圆盘从A->C
		move(A, C, n);

		// 3.把B上n-1个圆盘从B借助A移动到C上
		HanoiTower(B, A, C, n - 1);
	}
}

int main()
{
	int n = 0;
	printf("输入A柱上的圆盘的个数:");
	scanf("%d\n", &n);

	//将n个圆盘从A柱借助B柱移动到C柱上
	HanoiTower('A', 'B', 'C', n);

	return 0;
}

五、扩展

如果想要计算移动了多少次盘子,只需要加入多一个 move() 函数即可。 文章来源地址https://www.toymoban.com/news/detail-729174.html

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

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

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

相关文章

  • 11、动手学深度学习——语言模型和数据集:代码详解

    我们了解了如何将文本数据映射为词元,以及将这些词元可以视为一系列离散的观测,例如单词或字符。 假设长度为 T T T 的文本序列中的词元依次为 x 1 , x 2 , … , x T x_1, x_2, ldots, x_T x 1 ​ , x 2 ​ , … , x T ​ 。于是, x t x_t x t ​ ( 1 ≤ t ≤ T 1 leq t leq T 1 ≤ t ≤ T )可以

    2024年02月17日
    浏览(39)
  • HarmonyOS学习路之方舟开发框架—学习ArkTS语言(基本语法 五)

    如果每个组件的样式都需要单独设置,在开发过程中会出现大量代码在进行重复样式设置,虽然可以复制粘贴,但为了代码简洁性和后续方便维护,我们推出了可以提炼公共样式进行复用的装饰器@Styles。 @Styles装饰器可以将多条样式设置提炼成一个方法,直接在组件声明的位

    2024年02月17日
    浏览(53)
  • HarmonyOS学习路之方舟开发框架—学习ArkTS语言(基本语法 一)

    ArkTS是HarmonyOS优选的主力应用开发语言。ArkTS围绕应用开发在 TypeScript (简称 TS )生态基础上做了进一步扩展,继承了 TS 的所有特性,是 TS 的超集。因此,在学习 ArkTS 语言之前,建议开发者具备 TS 语言开发能力。 当前, ArkTS 在 TS 的基础上主要扩展了如下能力: 基本语法:

    2024年02月16日
    浏览(66)
  • HarmonyOS学习路之方舟开发框架—学习ArkTS语言(基本语法 四)

    当创建了自定义组件,并想对该组件添加特定功能时,例如在自定义组件中添加一个点击跳转操作。若直接在组件内嵌入事件方法,将会导致所有引入该自定义组件的地方均增加了该功能。为解决此问题,ArkUI引入了@BuilderParam装饰器,@BuilderParam用来装饰指向@Builder方法的变量

    2024年02月17日
    浏览(52)
  • HarmonyOS学习路之方舟开发框架—学习ArkTS语言(基本语法 二)

    在ArkUI中,UI显示的内容均为组件,由框架直接提供的称为系统组件,由开发者定义的称为自定义组件。在进行 UI 界面开发时,通常不是简单的将系统组件进行组合使用,而是需要考虑代码可复用性、业务逻辑与UI分离,后续版本演进等因素。因此,将UI和部分业务逻辑封装成

    2024年02月04日
    浏览(53)
  • HarmonyOS学习路之方舟开发框架—学习ArkTS语言(基本语法 三)

    在开始之前,先明确自定义组件和页面的关系: 自定义组件: @Component 装饰的 UI 单元,可以组合多个系统组件实现 UI 的复用。 页面:即应用的 UI 页面。可以由一个或者多个自定义组件组成, @Entry 装饰的自定义组件为页面的入口组件,即页面的根节点,一个页面有且仅能有

    2024年02月16日
    浏览(59)
  • HarmonyOS学习路之方舟开发框架—学习ArkTS语言(状态管理 二)

    @Prop装饰的变量可以和父组件建立单向的同步关系。@Prop装饰的变量是可变的,但是变化不会同步回其父组件。 @Prop装饰的变量和父组件建立单向的同步关系: @Prop变量允许在本地修改,但修改后的变化不会同步回父组件。 当父组件中的数据源更改时,与之相关的@Prop装饰的变

    2024年02月14日
    浏览(45)
  • HarmonyOS学习路之方舟开发框架—学习ArkTS语言(状态管理 六)

    AppStorage是应用全局的UI状态存储,是和应用的进程绑定的,由UI框架在应用程序启动时创建,为应用程序UI状态属性提供中央存储。 和LocalStorage不同的是,LocalStorage是页面级的,通常应用于页面内的数据共享。而对于AppStorage,是应用级的全局状态共享。 AppStorage是在应用启动

    2024年02月20日
    浏览(51)
  • 智能合约学习笔记一 、——{Solidity语言详解——(1—2)小练习}

    1.根据提示,在指定位置写出编译版本,要求使用^符号,版本要求在0.6.0及以上。 2.根据提示,在指定位置写出所定义的合约名称。 3.为了查看程序的效果,我们使用在线 Solidity 开发工具 Remix IDE 编译和运行 Solidity 程序。中文在线版:在浏览器打开下方链接: Remix - 中文版

    2024年02月02日
    浏览(38)
  • 一般开发Unity 使用什么语言,需要学习什么知识

    一般来说,开发Unity使用的是C#语言。要学习Unity开发,你需要学习的知识包括: C#语言的基础知识 Unity的基本使用方法 常用的游戏编程模式,如游戏循环、场景切换、碰撞检测等 了解游戏对象、资源、动画、物理等概念 了解常用的游戏开发插件和工具,如脚本编辑器、版本

    2024年02月13日
    浏览(55)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包