汉诺塔————经典递归问题(C语言实现)

简介: 汉诺塔————经典递归问题(C语言实现)
问题背景

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

解题思路

假设总共需要移动n个盘子

1.将A柱上的n-1个盘子借助C柱移向B柱

2.将A柱上仅剩的最后一个盘子移向C柱

3.将B柱上的n-1个盘子借助A柱移向C柱

解题过程

1 .当只有一个盆的时候 我们只需要将那一个盆从a移动到c就可以

2. 当我们有两个盆的时候 我们要想将下面的一个盆移动到c 只需要将上面一个盆移动到b即可

伪代码表示如下

3 当我们有三个或者三个以上盆的时候应该怎么办呢?

这时候只需要将上面的n-1想象成一个整体 然后再带入两层汉诺塔的问题就可以啦

伪代码如下

那么完整代码如下:

我们设计一个程序 hanoi 它有四个参数 分别是 n 表示有多少层 A B C表示三个柱子

hanoi(n,a,b,c)表示将n个盘子再遵守规则的情况下 从a移动到c

注意这句话和我前面的提醒

体会

有点难理解,想了好久,又看了好久解释,这玩意真需要自己画图理解理解

目录
打赏
0
0
0
0
12
分享
相关文章
|
1月前
|
【C语言程序设计——函数】递归求斐波那契数列的前n项(头歌实践教学平台习题)【合集】
本关任务是编写递归函数求斐波那契数列的前n项。主要内容包括: 1. **递归的概念**:递归是一种函数直接或间接调用自身的编程技巧,通过“俄罗斯套娃”的方式解决问题。 2. **边界条件的确定**:边界条件是递归停止的条件,确保递归不会无限进行。例如,计算阶乘时,当n为0或1时返回1。 3. **循环控制与跳转语句**:介绍`for`、`while`循环及`break`、`continue`语句的使用方法。 编程要求是在右侧编辑器Begin--End之间补充代码,测试输入分别为3和5,预期输出为斐波那契数列的前几项。通关代码已给出,需确保正确实现递归逻辑并处理好边界条件,以避免栈溢出或结果
63 16
九/十:《初学C语言》— 扫雷游戏实现和函数递归基础
【8月更文挑战第5天】本篇文章用C语言采用多文件编写实现了一个基础的扫雷游戏(附源码),并讲解了关于函数递归的基础概念及其相对应的习题练习(附源码)
55 1
九/十:《初学C语言》— 扫雷游戏实现和函数递归基础
【c语言】一篇文章搞懂函数递归
本文详细介绍了函数递归的概念、思想及其限制条件,并通过求阶乘、打印整数每一位和求斐波那契数等实例,展示了递归的应用。递归的核心在于将大问题分解为小问题,但需注意递归可能导致效率低下和栈溢出的问题。文章最后总结了递归的优缺点,提醒读者在实际编程中合理使用递归。
109 7
|
4月前
|
c语言回顾-函数递归(上)
c语言回顾-函数递归(上)
60 2
|
4月前
|
c语言回顾-函数递归(下)
c语言回顾-函数递归(下)
65 0
【C语言篇】递归详细介绍(基础概念习题及汉诺塔等进阶问题)
要保持最小的步数,每一次汉诺塔问题(无论是最初还是递归过程中的),如果此时初始柱盘子数为偶数,我们第一步是把最上面的盘子移动到中转柱,如果为奇数,我们第一步则是将其移动到目标柱。
147 0
【C语言篇】递归详细介绍(基础概念习题及汉诺塔等进阶问题)
|
6月前
|
C语言中的递归
C语言中的递归
C语言编程—递归
递归是函数自我调用的编程技术,常用于解决分治问题,如计算阶乘和斐波那契数列。示例中展示了C语言的阶乘和斐波那契数列递归实现。递归需满足:问题可转化为规模更小的同类问题,存在结束条件以防止无限循环,并可能消耗大量时间和栈空间。栈用于存储函数调用信息,过多递归可能导致栈溢出。递归虽简洁,但非最优效率选择,递推算法通常是更好的替代方案。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等