C语言：青蛙跳台与汉诺塔问题

                                                                青蛙跳台

 

原理：一只青蛙跳n个台阶，青蛙可以一次性跳1个台阶，也可以跳2个台阶，问，有多少种跳法，可以跳过n个台阶。

分析：青蛙跳台本质上是递归问题，那它为什么是递归问题呢？

①假如有一个台阶，那青蛙只有一种跳法。

②假如有两个台阶，青蛙有两种跳法，1.一个一个台阶跳。2.跳两个台阶

③假如有三个台阶，青蛙有三种跳法，1.一个一个台阶跳。2.一次跳两个台阶再跳一个台阶。3.一次跳一个台阶再跳两台阶。

④假如有四个台阶，青蛙有五种跳法(这里就不再推啦，有兴趣的小伙伴可以推一推)

⑤假如有五个台阶，青蛙有九种跳法(这里就不再推啦，有兴趣的小伙伴可以推一推)

 …….

 

#include

int frog_diving_tower(int n)
{
	if (n == 1)
	{
		return 1;
	}

	if (n == 2)
	{
		return 2;
	}

	return frog_diving_tower(n - 1) + frog_diving_tower(n - 2);
}

int main()
{
	int n = 0;
	printf("请输入台阶个数：");
	scanf("%d", &n);

	int ret = frog_diving_tower(n);

	printf("一共有%d种跳法",ret);
	return 0;
}

升华：一只青蛙跳n个台阶，青蛙可以一次性跳1个台阶，也可以跳2个台阶，也可以跳3个台阶，问，有多少种跳法，可以跳过n个台阶。

#include

int frog_diving_tower(int n)
{
	if (n == 1)
	{
		return 1;
	}

	if (n == 2)
	{
		return 2;
	}

	if (n == 3)
	{
		return 3;
	}

	return frog_diving_tower(n - 1) + frog_diving_tower(n - 2) + frog_diving_tower(n - 3);
}

int main()
{
	int n = 0;
	printf("请输入台阶个数：");
	scanf("%d", &n);

	int ret = frog_diving_tower(n);

	printf("一共有%d种跳法",ret);
	return 0;
}

注释：不难看出其中的规律，只要改动int frog_diving_tower(int n)这个函数就行。

                                                                  汉诺塔

 原理：有三个柱子A，B，C，而A柱上有n个圆盘，要求把A柱的圆盘放在C盘上，并且要求小的圆盘放在大的圆盘上，问：A柱上的n个圆盘放在C盘上，需要移动多少次，求最小次数。

分析：汉诺塔问题本质上还是递归问题，那它为什么是递归问题呢？

①假如有一个圆盘：需要移动1次。A-C。

②假如有两个圆盘：需要移动3次。A-B，A-C，B-C

③假如有三个圆盘：需要移动7次。A ->C，A->B，C->B，A->C，B->A，B->C，A->C

……

 注意：

 代码实现

//这里one是A柱
//这里two是B柱
//这里there是C柱
#include

void move(char x, char y)
{
	printf("%c->%c ", x, y);//这里模拟圆盘移动过程 
}

void hanoi(int n, char one, char two, char three) 
{
	if (n == 1)
		move(one, three);
	else
	{
		hanoi(n - 1, one, three, two); //将A柱上n-1个盘子移到B柱上（借助 C）
		move(one, three);              //将A柱上剩下的1个盘子移到C柱上
		hanoi(n - 1, two, one, three); //将B柱上n-1个盘子移到C柱上（借助 A）
	}
}

int main()
{
	int n = 0;
	printf("请输入圆盘个数:");
	scanf("%d", &n);

	hanoi(n, 'A', 'B', 'C');  

	return 0;
}

       不知不觉就到了尾声啦，作为小白的我，可能写的不是很好，不对的地方还请各位小伙伴留言给我谢谢啦。

 

 

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: 详解C++类&对象（中篇)——超详细前言：类的6个默认成员函数一， 构造函数 二， 析构函数 三， 拷贝构造函数 四， 赋值运算符重载 五， const成员函数 六，取地址及const取地址操作符重载 七，练习——实现日期计算器结语

目录 前言：类的6个默认成员函数 一， 构造函数 1. 概念 2. 特性 二， 析构函数 2.1 概念 2.2 特性 2.3 牛刀小试  三， 拷贝构造函数 3.1概念 3. 2 特点 四， 赋值运算符重载 4. 1 运算符重载  五， const成员函数 六…