C语言——青蛙跳台阶（递归）

目录

一、题目描述：

二、解题思路：

三、代码：

---

一、题目描述：

        一只青蛙可以一次跳 1 级台阶或一次跳 2 级台阶，例如：跳上第一级台阶只有一种跳法，直接跳 1 级即可。跳上两级台阶，有两种跳法： 每次跳 1 级，跳两次； 或者一次跳 2 级。问要跳上第 n 级台阶有多少种跳法？

二、解题思路：

 

    通过分析可以发现青蛙跳台阶问题可以类似于一个斐波那契数：当青蛙要跳到第一个台阶时可以跳一个台阶；当青蛙要跳到第二个台阶时可以跳一个2级台阶或者两个1级台阶；当台阶数大于2即N个台阶时，可以从第N-1个台阶跳、也可以从第N-2个台阶跳——walk(n)=walk(n-1)+walk(n-2)。

三、代码：

#include<stdio.h>
int test(int n)
{
	if (n <= 2)
		return n;
	else
		return test(n - 1) + test(n - 2);
}

int main()
{
    printf("输入要跳的台阶数！！！\n");
	int n = 0;
	scanf("%d", &n);
	int ret = test(n);
	printf("有%d种跳法\n", ret);

	return 0;
}