函数递归之青蛙跳台阶+汉诺塔
目录
1. 函数递归
2. 青蛙跳台阶问题
1.1 题目
1.2 思路
1.3 代码
1.4 迭代方法求解
3. 汉诺塔问题
3.1 题目
3.2 思路
3.3 代码
1. 函数递归
想要了解函数递归相关知识，可以看博主的另一篇博客：
函数递归的讲解
2. 青蛙跳台阶问题
1.1 题目
计算一只青蛙从地面跳到指定高度 n 的台阶有多少种不同的跳跃方式。青蛙每次可以选择跳 1 级或者2 级台阶直到达到目标高度。
1.2 思路
我们可以自定义一个函数来求n层台阶有多少种不同的跳跃方法，这里我自定义的函数是
count(n); 。
如果n=1 有一层台阶，那么青蛙只有一种方法，如果n=2 有两层台阶，那么青蛙只有两种方法，如果n=3有三层台阶，青蛙如果第一次选择跳1个台阶，还剩下2个台阶（跳2个台阶的方法是固定的2种），如果第一次选择跳2个台阶，还剩下1个台阶（跳1个台阶的方法是固定的1种）。如下图：
由上图你会发现这个问题跟斐波那契数列问题有点相同，那我们就可以用斐波那契递归思路，来求解这道题。
1.3 代码
#include <stdio.h>
int count(int n)
{if (n == 1)return 1;if (n == 2)return 2;return count(n - 1) + count(n - 2);
}
int main()
{printf("请输入青蛙要跳到第几层台阶：\n");int n = 0;scanf("%d", &n);int a = count(n);printf("有%d种方法\n",a);return 0;
}1.4 迭代方法求解
青蛙跳台阶问题也可以用迭代的方法求解，也就是循环的方法。
代码如下：
#include <stdio.h>
int count(int n)
{int a = 1;int b = 2;int c = 1;if (n == 2){return 2;}else{while (n > 2){c = a + b;a = b;b = c;n--;}}return c;
}
int main()
{printf("请输入青蛙要跳到第几层台阶：\n");int n = 0;scanf("%d", &n);int a = count(n);printf("有%d种方法\n", a);return 0;
}3. 汉诺塔问题
3.1 题目
汉诺塔问题是一个经典的问题。汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？
简单来说就是有三根柱子A , B , C ，在A柱子上放一定数量的圆盘，遵守规则的情况下通过
柱子B，把全部圆盘移动到C上面。
规则如下：
1. 一次只能移动一个圆盘。
2. 大圆盘不能放在小圆盘上面
3.2 思路
这里我自定义了一个Print(input,a,b,c);函数 ，input是A柱子上的圆盘数，a,b,c分别是 A,B,C 三个柱子的编号。
下面是汉诺塔问题的大致流程：
如果有三根柱子 A , B , C 时，如图：
a = 'A' b = 'B' c = 'C'
Print( 1 , a , b , c ); 移动到C需要 printf("%d—>%d", a, c); 也就是(A—>C)
Print( 2 , a , b , c ); 移动到C需要 Print(1 , a , c , b ); A—>C, Print( 1 , b , a , c );
Print( 3 , a , b , c ); 移动到C需要 Print( 2 , a , c , b ); A—>C , Print( 2 , b , a , c );
通过上面分析我们会发现只要A>1，都会经过三大步，假设A上有n个柱子，
第一步:把A柱子上面的(n-1)个柱子通过（A=n-1时候的移动方法）借助 C 移动到 B 上面。
Print( n-1 , a , c , b );
第二步:把A柱子上剩余的1个柱子移动到C上面。
A—>C
第三步:把B柱子上面的(n-1)个柱子通过（A=n-1时候的移动方法）借助 A 移动到 C 上面。
Print( n-1 , b , a , c );
通过这三大步就能完成A上圆盘移动到B上去。
当n=1 ，只需要打印 A—>C。
3.3 代码
#include <stdio.h>
void Print(int n,char a,char b,char c)
{if (n == 1){printf("%c->%c\n", a, c);}else{Print(n - 1, a, c, b);printf("%c->%c\n", a, c);Print(n - 1, b, a, c);}
}
int main()
{printf("请输入第一根柱子有几个圆片:\n");int input = 0;char a = 'a';char b = 'b';char c = 'c';scanf("%d", &input);Print(input,a,b,c);return 0;
}