用递归思想解决汉诺塔和青蛙跳台阶问题

37 阅读 0 评论 25 点赞

我是靠谱客的博主单薄咖啡，最近开发中收集的这篇文章主要介绍用递归思想解决汉诺塔和青蛙跳台阶问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.汉诺塔问题
有三个柱子，圆盘若干个从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
void move(char a, char b)  //打印移动方案
{
	printf("%c -> %cn", a, b);
}
void hanoi(int x, char a, char b, char c)
{
	if (x == 1)                   //若只有一个盘子则直接移动
		move(a, c);
	else
	{
		hanoi(x - 1, a, c, b);      //大于1，移动上面的盘子去借助的柱子上
		move(a, c);                 //将目标的盘子进行移动
		hanoi(x - 1, b, c, a);      //再将其他盘子移动到目标盘子上
	}
}
int main()
{
	int n = 0;
	char a = 'a';    //设定三根柱子a，b，c
	char b = 'b';
	char c = 'c';
	printf("请输入汉诺塔个数n");
	scanf("%d", &n);
	hanoi(n, a, b, c);
	system("pause");
	return 0;
}

2.青蛙跳问题
（1）假设有n级台阶，青蛙每次可以跳一级，也可以他跳二级，求共有多少种跳法。
分析：
已知如果
n = 1 则只有一种跳法
n = 2 有2种跳法
n = 3 时，可以认为前面分解称为跳一级与跳两级，则为n = 1与 n = 2时的和，有3种
…依次类推
当 n = n时，可以运用递归的思想
假设调的总数为f(x)，则f(n) = f( n- 1) + f(n - 2) n>2
代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
int fora(int n)
{
	if (n == 1)
		return 1;
	else if (n == 2)
		return 2;
	else
		return fora(n - 1) + fora(n - 2);
}
int main()
{
	int ret = 0;
	int n = 0;
	printf("请输入台阶上数n");
	scanf("%d", &n);
	ret = fora(n);
	printf("有%d种方案n", ret);
	system("pause");
	return 0;
}

（2）假设有n级台阶，青蛙每次可以跳一级，二级，三级，求共有多少种跳法。
分析与上述一样
n = 1 时，1种
n = 2 时，2种
n = 3 时，4种
…
f(n) = f( n - 1) + f( n - 2) + f( n - 3) n>3
代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
int fora(int n)
{
	if (n == 1)
		return 1;
	else if (n == 2)
		return 2;
	else if (n == 3)
		return 4;
	else
		return fora(n - 1) + fora(n - 2)+fora(n - 3);
}
int main()
{
	int ret = 0;
	int n = 0;
	printf("请输入台阶上数n");
	scanf("%d", &n);
	ret = fora(n);
	printf("有%d种方案n", ret);
	system("pause");
	return 0;
}

（3）假设有n级台阶，青蛙每次可以跳一级，二级，三级…n级，求共有多少种跳法。
分析
当
n = 1 时，f(1) = 1;
n = 2 时，f(2) = f(1) + 1
n = 3 时，f(3) = f(2) + f(1) + 1
…每次加一为当前次数在前一次的方法种，增加了一次能直接从最低一级跳到最高级的方法，因此+1
…
次数为 n 时
f(n) = f( n - 1) + f( n - 2) + f( n - 3) + f( n - 4)+…+ f(2) + f(1) + 1
f(n - 1) = f( n - 2) + f( n - 3) + f( n - 4)+…+ f(2) + f(1) + 1
两式相见得
f(n) - f(n - 1) = f(n - 1)
f(n) = 2 * f(n - 1) n>1
代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
int fora(int n)
{
	 if (n == 1)
		return 1;
	else
		return 2*fora(n - 1);
}
int main()
{
	int ret = 0;
	int n = 0;
	printf("请输入台阶上数n");
	scanf("%d", &n);
	ret = fora(n);
	printf("有%d种方案n", ret);
	system("pause");
	return 0;
}