目录
一、程序
1.实现代码
2.程序执行结果
二、背景
1.汉诺塔问题描述
2.直观理解
3.思考过程
三、函数执行过程
举例 n=2
四、总结
递归问题
一、程序
1.实现代码
#include <stdio.h>
/*
函数名: move
功能: 移动一次盘子,并在屏幕上打印
参数:a:移动一次的起点
b:移动一次的终点
返回值:无
*/
void move(char a, char b)
{
printf("%c->%c\n", a, b);
}
/*
函数名: hanoi
功能: 把n个盘子从x柱子上经由y柱子移动到z柱子
参数:n:盘子个数
x:盘子位于x柱子上
y:要经过y柱子
z:最终全部移动到z柱子上
返回值:无
*/
void hanoi(int n, char x, char y, char z)
{
if (n == 1) {
move(x, z);
}
else {
hanoi(n - 1, x, z, y);//步骤一:把n-1个盘子从x柱子上经由z柱子移动到y柱子
move(x, z);//步骤二:把盘子从x柱子移动到z柱子
hanoi(n - 1, y, x, z);//步骤三:把n-1个盘子从y柱子上经由x柱子移动到z柱子
}
}
int main()
{
int n = 0;
printf("请输入盘子个数:");
scanf("%d", &n);//键盘输入盘子个数,存放在n中
hanoi(n, 'a', 'b', 'c');//调用函数
return 0;
}
2.程序执行结果
输入3
输入4
(可以输入更大的数)
二、背景
1.汉诺塔问题描述
给定三根柱子,记为 A,B,C ,其中 A柱子上有 n个盘子,且上面的盘子一定比下面的盘子小。
问:如何将 A 柱上的盘子经由 B柱移动到 C 柱。
移动时应注意:① 一次只能移动一个盘子 ;②大的盘子不能压在小盘子上。
2.直观理解
一个盘子时:
两个盘子时:
三个盘子时:
思考n个盘子时?
3.思考过程
这样一个复杂的问题可以拆解为三个步骤:
步骤一:把n-1个盘子从A柱移动到B柱
步骤二:把1盘子从A柱移动到C柱
步骤三:把n-1个盘子从B柱移动到C柱
其中步骤二可以一步完成,步骤一和步骤三无法一步完成。但是步骤一和步骤三又可以分别拆解为三个步骤。这样一直递归,直到每个步骤都可以完成。
综上,该问题解决方法为:
用函数描述为:
函数hanoi参数的值由n逐渐递减为n-1,n-2,n-3,......,2,1
三、函数执行过程
举例 n=2
(n更大时过程类似)
四、总结
递归问题
汉诺塔问题是典型的递归问题,递归就是将复杂的问题,找到可以重复的自相似部分,化解为简单的小问题。
递归问题的两个必要条件:
1.存在限制条件,当满足这个限制条件的时候,递归便不再继续;
2.每次递归调用之后越来越接近这个限制条件。
编写的递归代码必须满足以上两个条件,否则会造成递归无法结束,出现栈溢出错误。
上述代码满足了两个必要条件:
1.if(n==1)是限制条件;
2.每次函数的参数n减1,越来越接近限制条件n==1。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)