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

约定不等于承诺〃 2024-03-22 03:32 64阅读 0赞

**青蛙跳台**

![1fd28dab7fb343b68fc590bfc25081d1.webp][]

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

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

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

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

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

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

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

.......

![666ba2d04b9c4257afa3cd5e85f7fb4a.png][]

#include<stdio.h>
    
    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<stdio.h>
    
    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)这个函数就行。![6f274cb377264b89bdf6563b15d1021b.png][]

**汉诺塔**

**![1661e84ef0064574aaaef468b306d782.webp][]**

原理：有三个柱子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

......

1683443499141

![2d6d4437ed8e43f692641037e5940bd6.png][]

注意：![f3c7095dbe814eba9b112d0dabfe787c.png][]

代码实现

//这里one是A柱
    //这里two是B柱
    //这里there是C柱
    #include<stdio.h>
    
    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;
    }

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

![7c1f82abc6e64bafad623fb77ecfae70.gif][]

[1fd28dab7fb343b68fc590bfc25081d1.webp]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/9aad494d5b224689905b0eb6a9dc4dc8.png
[666ba2d04b9c4257afa3cd5e85f7fb4a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/37c4804583864922b280ab35e6752157.png
[6f274cb377264b89bdf6563b15d1021b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/54c9ff3964a74bc4bb15801ab15e5e3d.png
[1661e84ef0064574aaaef468b306d782.webp]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/72e4cc3effeb4b88b0c61b11a633fa03.png
[2d6d4437ed8e43f692641037e5940bd6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/5a405ca969c04e338dd5e37d4313f6a3.png
[f3c7095dbe814eba9b112d0dabfe787c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/3a97621d5ea8460c9178b4293242713d.png
[7221dfce3a9741758214cd250913d198.png]: https://img-blog.csdnimg.cn/7221dfce3a9741758214cd250913d198.png
[fbd9f005bc434c6194c5e57df8ebe7ae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/746d7a177e0c46369d6ec47d5eb5dc17.png
[7c1f82abc6e64bafad623fb77ecfae70.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/5893ca013cb9472bbb07f9c69bd29021.png