C语言怎么实现汉诺塔

魁首哥

作者

C语言怎么实现汉诺塔

这篇文章主要介绍了C语言怎么实现汉诺塔的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇C语言怎么实现汉诺塔文章都会有所收获，下面我们一起来看看吧。

1.递归思想简介

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

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

/*递归求n的阶乘*/intfactorial(intn)//定义一个求阶乘的函数叫做factorial(),需要一个整形参数，返回一个整形值{if(n<=1)//递归结束的条件{return1;}else{returnn*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>voidmove(char,char);//声明一个函数move，函数定义在下方，用于表示圆盘的交换voidTowers_Of_Hanoi(intn,chara,charb,charc){if(1==n)//递归结束标志：当柱子上只有一块圆盘{move(a,c);//从a移动到c}elseTowers_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柱上}}voidmove(charx,chary){printf("%c-->%c\n",x,y);}intmain(){intn=0;scanf("%d",&n);Towers_Of_Hanoi(n,'A','B','C');//n为A柱子上圆盘的数量，A,B,C代表三根柱子return0;}

程序运行结果为：