青蛙跳台
原理:一只青蛙跳n个台阶,青蛙可以一次性跳1个台阶,也可以跳2个台阶,问,有多少种跳法,可以跳过n个台阶。
分析:青蛙跳台本质上是递归问题,那它为什么是递归问题呢?
①假如有一个台阶,那青蛙只有一种跳法。
②假如有两个台阶,青蛙有两种跳法,1.一个一个台阶跳。2.跳两个台阶
③假如有三个台阶,青蛙有三种跳法,1.一个一个台阶跳。2.一次跳两个台阶再跳一个台阶。3.一次跳一个台阶再跳两台阶。
④假如有四个台阶,青蛙有五种跳法(这里就不再推啦,有兴趣的小伙伴可以推一推)
⑤假如有五个台阶,青蛙有九种跳法(这里就不再推啦,有兴趣的小伙伴可以推一推)
#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)这个函数就行。
原理:有三个柱子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
注意:
代码实现
//这里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; }
不知不觉就到了尾声啦,作为小白的我,可能写的不是很好,不对的地方还请各位小伙伴留言给我谢谢啦。