亲宝软件园·资讯

展开

C语言递归汉诺塔青蛙跳台阶 C语言递归之汉诺塔和青蛙跳台阶问题

一只当归 人气:0
想了解C语言递归之汉诺塔和青蛙跳台阶问题的相关内容吗,一只当归在本文为您仔细讲解C语言递归汉诺塔青蛙跳台阶的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:C语言递归,C语言汉诺塔,C语言青蛙跳台阶,下面大家一起来学习吧。

递归就是一个函数执行过程中调用自己,在c语言中有很多关于递归的经典问题,例如:斐波那契数列问题、汉诺塔问题等,在研究递归问题时我们要注意三点:
1.递归的结束条件
2.递归在每次进行过程中,都得离条件越来越近
3.相邻两次递归调用之间的关联关系

汉诺塔问题:

有三根杆子A, B, C。A杆上有N个(N > 1)穿孔圆盘, 盘的尺寸由下到上依次变小.要求按下列规则将所有圆盘移至C杆:
1.每次只能移动一个圆盘;
2.大盘不能叠在小盘上面,可将圆盘临时置于B杆, 也可将从A杆移出的圆盘重新移回A杆, 但都必须尊循上述两条规则。求移动的过程。

int step = 0; //设置全局变量step记录步数
void move(int i,char form,char to){
	printf("第%d步,将第%d个盘子从%c移动到%c\n", ++step,i,form, to);
}
void Hanio(int n,char a,char b,char c){
	if (n == 0)
	{
		return;
	}
	Hanio(n - 1,a,c,b); //第n-1个A柱上的盘子通过C柱移动到B柱
	move(n, a, c);  //将A柱上编号为n的盘子移动到C柱
	Hanio(n - 1, b, a, c); //再将B柱上的第n-1个盘子通过A柱移动到C柱
}
int main(){
	    int n;
		printf("请输入汉诺塔中有多少个圆盘:\n");
		scanf("%d", &n);
		Hanio(n, 'A', 'B', 'C'); //将n个圆盘从A柱通过B柱移动到C柱
		system("pause");
		return 0;
}

运行结果:

在这里插入图片描述

青蛙跳台阶问题:

一只青蛙一次可以跳上 1 级台阶,也可以跳上2 级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
当n = 1,只有1中跳法;当n = 2时,有两种跳法;当n = 3 时,有3种跳法;当n = 4时,有5种跳法;当n = 5时,有8种跳法。可以总结为f(n)=f(n-1)+f(n-2),本质上与斐波那契数列相同。

int Frog(int n){
	if (n <= 2 && n >= 0)
	{
		return n;
	}
	else if (n < 0)
	{
		printf("您的输入错误\n");
		return n;
	}else
	{
		return Frog(n - 1) + Frog(n - 2);
	}
}
int main(){
		int n;
		printf("请输入有几级台阶:\n");
		scanf("%d", &n);
		int result = Frog(n);
		if(n >= 0){ 
			printf("青蛙有%d种跳法\n", result);
		}
		system("pause");
		return 0;
}

运行结果

在这里插入图片描述

加载全部内容

相关教程
猜你喜欢
用户评论