递归求汉诺塔问题 递归求青蛙跳台问题

1.递归求汉诺塔问题
在汉诺塔问题中，假设有A、B、C三根柱子，A柱子上由上到下从小到大摆放了n个圆盘，要借助B柱子将A柱子上的圆盘由移动到C柱子上，还是按由上到下从小到大摆放。
设想A上有一个圆盘，直接移到C上(a->c),只需要一次 2^1-1；
设想A上有两个圆盘，通过（A->B,A->C,B->C),需要三次 2^2-1；
设想A上有三个盘子，通过（A->C A->B C->B A->C B->A B->C A->C ),
需要七次 2^3-1；
如果有n个盘子，则可把问题归结于把（n-1）个放在B上，再将A上最大的放到C上，现在在B上的（n-1)个盘子，可归结于把（n-2)个放到A上，再将B上最大的放到C上，以此类推，用递归实现。代码如下

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
void Move(char pos1, char pos2)
{
	printf("%c->%c ", pos1, pos2);
}
//pos1开始位置
//pos2中间位置
//pos3结束位置
void Hanota(int n, char pos1, char pos2, char pos3)
{
	if (n == 1)
	{
		Move(pos1,pos3);
	}
	else
	{
		Hanota(n - 1, pos1, pos3, pos2);
		Move(pos1, pos3);
		Hanota(n - 1, pos2, pos1, pos3);
	}
}
int main()
{
	int n;
	printf("请输入盘子的数量n");
	scanf("%d", &n);
	Hanota(n, 'A', 'B', 'C');
	system("pause");
	return 0;
}

2.一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶，问这个青蛙跳上n级台阶一共有多少种跳法。
跳一级台阶一种方法；
跳两级台阶两种方法；1 1 或 2
跳三级台阶三种方法；1 1 1或1 2 或2 1；
跳四级台阶五种方法；1 1 1 1或1 2 1 或1 1 2或2 1 1或 2 2
跳n级台阶，可想为最后一次跳一阶或最后一次跳两阶，则可归结于跳（n-1）级台阶和跳（n-2)级台阶的跳法相加，以此类推，递归实现。代码如下

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

最后

以上就是玩命香水为你收集整理的递归求汉诺塔问题 递归求青蛙跳台问题的全部内容，希望文章能够帮你解决递归求汉诺塔问题 递归求青蛙跳台问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。