一、汉诺塔
汉诺塔又称河内塔,起源于印度,传说大反天创造世界时做了三根金刚石柱,其中一根柱子上落着六十四片黄金圆盘。大反天命令陀螺门将圆盘按大小顺序重新摆放到另一根柱子上,规定每次只能移动一块,并且大圆盘不能放到小圆。
#include<stdio.h> int count; void move(char a, char b, char c, int n) { if (n == 1) { ++count; printf("第%d次移动:将现在%c上的第一个圆盘移到%c\n",count,a,c); } else if (n > 1) { move(a, c, b, n - 1);//通过c柱子将a柱子上n-1个圆盘移到b ++count; printf("第%d次移动:将现在%c上的第一个圆盘移到%c\n",count, a, c); move(b, a, c, n - 1);//看下文绿色字体解释 } } int main() { int n; scanf("%d", &n); move('a','b','c', n); return 0; }
现在我们看下图进行解析 经过这样移动便可将n-1个圆盘移动到b上,这个过程通过代码实现便是上面的:
move(a, c, b, n - 1);
然后将a上最后一个圆盘移到。然后得到下图:
这时我们发现a是空的,b是有2个圆盘,c上有一个最大的圆盘因为其不影响任何其他圆盘放在c上所以我们可以假设c没有圆盘,如果我们把a当作b,b当作a是不是就相当于刚开始n为2个圆盘,故此我们在调用一次函数即递归,代码实现便是move(b, a, c, n - 1);至此函数不断递归下去直到
n-1为1时函数结束!!!这便是递归解决汉诺塔问题了!!!
二、青蛙跳台
青蛙跳台阶问题是一个经典的数学问题,其内容为:一只青蛙一次可以跳上一级台阶或两级台阶,问青蛙从第n级台阶跳上第n+1级台阶,总共有多少种跳法。
下面看一下代码实现:
#include<stdio.h> int dancestep(int n) { if (n == 1) { return 1;//当只有一层台阶时有一种跳法 } if (n == 2) { return 2;//当只有2层台阶时有两种跳法 } if (n > 2) //n大于二时进行递归运算 { return dancestep(n - 1) + dancestep(n - 2); } } int main() { int n = 0; scanf("%d", &n); int num = dancestep(n); printf("%d\n", num); return 0; }
接下来我们进行分析:
假设青蛙从第n级台阶跳上第n+1级台阶的跳法数为f(n),那么当它只跳一级时,就可以从第n-1级台阶跳上第n级台阶,此时跳法数为f(n-1);当它一次跳两级时,就可以从第n-2级台阶跳上第n级台阶,此时跳法数为f(n-2)。
因此,我们可以得到递推公式:f(n)=f(n-1)+f(n-2)。
根据这个递推公式,我们可以依次计算出从第1级台阶到第n级台阶的所有跳法数。例如,当n=3时,有f(3)=f(2)+f(1)=2+1=3种跳法。
需要注意的是,青蛙跳台阶问题还有其他的变种,例如每次只能跳一级或者每次只能跳两级,但是其本质都是相同的,都可以使用递归的方法来解决。
注:递归虽然代码看着简便但n如果稍微大一点时电脑的计算次数的计算量却非常大
至于为什么看下图:
我们假设n=40由此我们看出当函数需要进行的计算量(n-1)^2,故此我们其实也可以用普通循环的方法来解决青蛙跳台阶的问题。下面展示代码:
#include<stdio.h> int main() { int a=1, b=2,i,n,sum; scanf("%d", &n); if (n >= 3) { for (i = 1; i <= n - 2; i++) { sum = a + b; a = b; b = sum; } } else { sum = n; } printf("%d", sum); return 0; }
这样计算的代码就不会在n较大时使函数的计算量成指数增长了!!!
好了各位今天的博客就结束了!!!