C语言递归思想实现汉诺塔详解

2024-09-29 03:46:28

1.递归思想简介

在c语言中，程序调用自身的编程技巧称为递归（ recursion）。

递归的定义看上去似乎很抽象，使用代码描述能够让人容易理解，下面是一个函数递归的例子。

/*                                递归求n的阶乘                        */

int factorial(int n)  //定义一个求阶乘的函数叫做factorial(),需要一个整形参数，返回一个整形值
{
	if (n <= 1)       //递归结束的条件
	{
		return 1;
	}
	else
	{
		return n * factorial(n - 1);//在factorial()中再次调用自身，只不过参数由n变成n-1
	}
}

在这个例子中，函数 factorial()接收到一个整形数n，如n=5，暂时称作F(5)，这时n!=F(5)，而函数的功能如下：

判断5是否小于或等于1，如果是，将1返回；不是，进到else执行语句返回（这里可以将return看作等于）5× factorial(n - 1)，等价于 F(5)=5×F(4)用上面的方法计算F(4)=4×F(3)....以此类推直到达到限制条件n=1时有，F(1)=1

递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题。

由于每个小问题处理起来都有与大问题类似的行为逻辑，因此我们可以“大事化小”，而递归说白了，就是不断地在套娃。

但是，计算机的内存是有限的，由于每次调用函数都需要在栈区开辟一个空间，使得递归不能无限制地进行下去，没有递归结束的条件，当操作系统为进程分配的虚拟地址空间当中的栈空间被耗尽时，会发生堆栈溢出，产生段错误(segmentation fault)。

因此，使用递归时应注意：

必须存在限制条件，当满足这个限制条件的时候，递归便不再继续每次递归调用之后越来越接近这个限制条件

递归的好处在于：

代码简洁在某些特定问题上求解方便

递归的缺点在于

消耗大量时间和空间资源——效率较低可能伴随许多重复计算，工作量大——影响性能

2.汉诺塔问题

以下内容来自维基百科

最早发明这个问题的人是法国数学家爱德华·卢卡斯。

传说越南河内某间寺院有三根银棒，上串 64 个金盘。寺院里的僧侣依照一个古老的预言，以上述规则移动这些盘子；预言说当这些盘子移动完毕，世界就会灭亡。这个传说叫做梵天寺之塔问题（Tower of Brahma puzzle）。但不知道是卢卡斯自创的这个传说，还是他受他人启发。

若传说属实，僧侣们需要 $2^{64}-1$ 步才能完成这个任务；若他们每秒可完成一个盘子的移动，就需要 5849 亿年才能完成。整个宇宙现在也不过 137 亿年。

这个传说有若干变体：寺院换成修道院、僧侣换成修士等等。寺院的地点众说纷纭，其中一说是位于越南的河内，所以被命名为“河内塔”。另外亦有“金盘是创世时所造”、“僧侣们每天移动一盘”之类的背景设定

汉诺塔基本的玩法如图，其规则是：将圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

当圆盘数量只有3个的时候，求解的方法显而易见，但当数量增多时，问题变得有些棘手起来。但不管怎么移动，核心思想都是递归：

先从n块圆盘中将最大的一块移动到最后的柱子上接着从剩下n-1找到最大的一块移到柱子上......

3.汉诺塔递归的c语言实现

C语言代码如下：

/*                            汉诺塔问题（递归实现）                     */

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

void move(char, char); // 声明一个函数move，函数定义在下方，用于表示圆盘的交换

void Towers_Of_Hanoi(int n,char a,char b,char c)
{
	if (1 == n)                        //递归结束标志：当柱子上只有一块圆盘
	{
		move(a, c);                    //从a移动到c
	}
	else
		Towers_Of_Hanoi(n - 1, a, c, b);    //将最上面n-1个圆盘移动到b柱上
		move(a, c);                         //将a上面最后一块圆盘移动到c柱上
		Towers_Of_Hanoi(n - 1, b, a, c);    //将b柱上n-1个圆盘移动到a柱上
	}
}

void move(char x, char y)
{
	printf("%c-->%c\n", x, y);
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	Towers_Of_Hanoi(n, 'A', 'B', 'C');//n为A柱子上圆盘的数量，A,B,C代表三根柱子
	return 0;
}

程序运行结果为：

总结

到此这篇关于C语言递归思想实现汉诺塔详解的文章就介绍到这了,更多相关C语言汉诺塔内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C语言汉诺塔的简单了解

汉诺塔详解以4层为例以下为我的拙见,还希望大佬雅正要把汉诺塔移动到c 需要把1,2,3层移到b 把4移动到c 在吧123移动到b 但是一次只能动一块所以我们目前要做的就是把上面三块移动到b 那就需要把1 2移动到c 由此我们可以推出要把1,2移动到c,只需要把1移动到b 这里我们发现有很多重复的自相似动作我们就可以设计递归递归需要1,递归体 2 出口. 递归体移动n-1个盘子和1个盘子和n个盘子过程都是相似的但是每次放入的杆子不一样. 出口 n=1时只剩一个盘子,直接移动到c即可
C语言编写汉诺塔游戏

目录汉诺塔的游戏规则: 当A只有一个环的时候: 当A只有两个环的时候: 当A只有三个环的时候: 思路: 当n=1时: 当n=2时: 当n=3时: 当n=4时: 见代码运行截图总结汉诺塔的游戏规则: 有三根金刚石柱子A.B.C,在A柱子上从下往上按照大小依次减小的顺序摞着64片黄金环.大梵天命令婆罗门把环从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,在任何一个柱子上,小环上不能放大环,在三根柱子之间一次只能移动一个环. 即将A柱子上全部的环通过C柱子(C柱子作为中介)移动到B柱子
带你理解C语言中的汉诺塔公式

目录汉诺塔公式汉诺塔问题在数学层面的公式: C语言递归公式两层汉诺塔三层汉诺塔总结汉诺塔公式汉诺塔问题在数学层面的公式: 不用说,你看到这个公式一定一脸懵逼,我现在来讲解这个公式的作用. 先来回想一下大象放冰箱要几步,三步吧,打开冰箱,放进去,关上门就行了,我们先不要去思考一些细碎的步骤,将一个复杂的问题先简单化,再慢慢去分析. 那汉诺塔问题也是同样的简单三步:(假设有n个盘子) 一.把最大的盘子留在A柱,然后将其他的盘子全放在B柱. 二.把最大的盘子放到C柱. 三.然后将B柱上的
C语言编程递归算法实现汉诺塔

汉诺塔法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针.印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔.不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面.僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔.庙宇和众生也都将同归于尽. 这个传说挺有意思的,这个传说
C语言递归之汉诺塔和青蛙跳台阶问题

递归就是一个函数执行过程中调用自己,在c语言中有很多关于递归的经典问题,例如:斐波那契数列问题.汉诺塔问题等,在研究递归问题时我们要注意三点: 1.递归的结束条件 2.递归在每次进行过程中,都得离条件越来越近 3.相邻两次递归调用之间的关联关系汉诺塔问题: 有三根杆子A, B, C.A杆上有N个(N > 1)穿孔圆盘, 盘的尺寸由下到上依次变小.要求按下列规则将所有圆盘移至C杆: 1.每次只能移动一个圆盘: 2.大盘不能叠在小盘上面,可将圆盘临时置于B杆, 也可将从A杆移出的圆盘重新移回A杆,
C语言实现汉诺塔(图文详解)

目录思路: 当n=1时: 当n=2时: 当n=3时: 当n=4时: 见代码运行截图总结汉诺塔的游戏规则: 有三根金刚石柱子A.B.C,在A柱子上从下往上按照大小依次减小的顺序摞着64片黄金环.大梵天命令婆罗门把环从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,在任何一个柱子上,小环上不能放大环,在三根柱子之间一次只能移动一个环. 即将A柱子上全部的环通过中间柱子B(B柱子作为中介)移动到C柱子上当A只有一个环的时候: A->C 当A只有两个环的时候: A->B A->C
C语言递归思想实现汉诺塔详解

目录 1.递归思想简介 2.汉诺塔问题 3.汉诺塔递归的c语言实现总结 1.递归思想简介在c语言中,程序调用自身的编程技巧称为递归( recursion). 递归的定义看上去似乎很抽象,使用代码描述能够让人容易理解,下面是一个函数递归的例子. /* 递归求n的阶乘 */ int factorial(int n) //定义一个求阶乘的函数叫做factorial(),需要一个整形参数,返回一个整形值 { if (n <= 1) //递归结束的条件 { return 1; } else { ret
Java与C++分别用递归实现汉诺塔详解

目录 1.汉诺塔介绍 2.解塔步骤 3.C++实现(递归结果及显示步骤) (1)递归结果 (2)显示步骤 4.Java实现(递归结果及显示步骤) (1)递归结果 (2)显示步骤 1.汉诺塔介绍汉诺塔规则 1.有三根杆子A,B,C.A杆上有若干碟子 2.每次移动一块碟子,小的只能叠在大的上面 3.把所有碟子从A杆全部移到C杆上经过研究发现,汉诺塔的破解很简单,就是按照移动规则向一个方向移动金片: 如3阶汉诺塔的移动:A→C,A→B,C→B,A→C,B→A,B→C,A→C 2.解塔步骤圆盘:1
java 实现汉诺塔详解及实现代码

java 实现汉诺塔详解及实现代码汉诺塔问题:有三根柱子A,B,C,其中A上面有n个圆盘,从上至下圆盘逐渐增大,每次只能移动一个圆盘,并且规定大的圆盘不能叠放在小的圆盘上面,现在想要把A上面的n个圆盘全部都移动到C上面,输出移动的总步数以及移动的过程分析: //先求出移动的总步数 1,假设g(n)表示n个圆盘时的移动总的步数,当n=1时,g(1)=1; 2.现在可以把g(n)进行细分为三步: 1>先将n-1个圆盘从A通过C移动到B上面,相当于将n-1个圆盘从A移动到C,因此需要g(n-1)步
java 汉诺塔详解及实现代码

java 汉诺塔详解及实现代码实现效果图打印的方法在 moveTheTopOne() 方法中被调用,调用该方法前打印出移动的方向--从X号塔往Y号塔汉诺塔要求:将第一座塔上的所有盘子,借助第二座塔,全部搬运到第三座塔上. 规则:一次只能搬运一个盘子,不准将大盘子落在小盘子上. 汉诺塔实现代码: public class NewHanoi { public static int tiers = 4; // tiers 层数 private static List<String> pago
C语言用递归函数实现汉诺塔

目录汉诺塔(Hanoi)是什么? 那么,C语言如何实现汉诺塔呢? 汉诺塔的基本思路是: 具体代码见下(注意点在代码下面): 总结汉诺塔(Hanoi)是什么? 一个简单的汉诺塔就如上图所示,有三个放置点,放置物必须遵循上小下大的规则,依次将1中的放置物全部放置到3中.就比如该图中有4个放置物,若将A上的放置物全部移至C上,具体的步骤是:A->B A->C B->C A->B C->A C->B A->B A->C B->C B->A C->
Java递归来实现汉诺塔游戏,注释详细

我们很容易能想到,可以用递归来实现汉诺塔游戏.因为要将n(n>1)个盘子从"源"柱子移到"目标"柱子,我们要先把n-1个盘子从"源"柱子移到"辅助"柱子上,然后把最底下那一个盘子移到目标柱子上,最后把"辅助柱"上的n-1个盘子移动到目标柱子上.n==1时直接移到目标柱上,也是递归的出口. 有了以上思路的铺垫,就可以开始实现代码了. public class HanoiDemo { public sta
C语言递归在实践题目中应用详解

目录递归知识点题目第一题第二题第三题第四题第五题第六题第七题递归知识点递归概念:程序调用自身的编程技巧称为递归( recursion). 递归做为一种算法在程序设计语言中广泛应用. 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解, 递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量. 通俗理解就是:函数自己调用自己递归的主要思考方式就是大事化
Java使用递归法解决汉诺塔问题的代码示例

汉诺(Hanoi)塔问题:古代有一个梵塔,塔内有三个座A.B.C,A座上有n个盘子,盘子大小不等,大的在下,小的在上(如图). 有一个和尚想把这n个盘子从A座移到B座,但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘子始终保持大盘在下,小盘在上.在移动过程中可以利用B座,要求打印移动的步骤.如果只有一个盘子,则不需要利用B座,直接将盘子从A移动到C. 如果有2个盘子,可以先将盘子1上的盘子2移动到B:将盘子1移动到c:将盘子2移动到c.这说明了:可以借助B将2个盘子从A移动到C,当然,

C语言递归思想实现汉诺塔详解

目录

1.递归思想简介

2.汉诺塔问题

3.汉诺塔递归的c语言实现

总结

相关推荐

随机推荐