C语言递归思想实现汉诺塔详解
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)。但不知道是卢卡斯自创的这个传说,还是他受他人启发。
若传说属实,僧侣们需要步才能完成这个任务;若他们每秒可完成一个盘子的移动,就需要 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语言汉诺塔内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
原文出处:https://blog.csdn.net/weixin_58165485/article/details/122609
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25
C语言正则表达式详解 regcomp() regexec() regfree()用法详解
C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror(),这里就为大家介绍一下,需要的朋友可以参考一下啊...2020-04-25- 这篇文章主要介绍了c语言实现找最大值最小值位置查找,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-04