青蛙跳台阶
时间限制: 1s
类别: 递归->简单
问题描述
有n个台阶，青蛙一次只能往上跳1个或者2个，共有多少种跳法？
请使用递归编程实现，递归思路如下：
| n 的值 | 走法 | 算式 |
|---|---|---|
| 1 | 只能一次1步 | f(1) = 1 |
| 2 | （1）一次走1步 （2）直接走2步 | f(2) = 2 |
| 3 | （1）先到达f(1)的情况，再从f(1)直接跨2步 （2）先到达f(2)的情况，再从f(2)直接跨1步 | f(3) = f(2) + f(1) = 3 |
| 4 | （1）先到达f(2)的情况，再从f(2)直接跨2步 （2）先到达f(3)的情况，再从f(3)直接跨1步 | f(4) = f(3) + f(2) = 5 |
| ... | ... | ... |
| n = x | （1）先到达f(x-2)的情况，再从f(x-2)直接跨2步 （2）先到达f(x-1)的情况，再从f(x-1)直接跨1步 | f(x) = f(x - 2) + f( - 1) |
输入说明
输入一个正整数n
输出说明
输出一个整数，表示跳法的种数。
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
long long di_gui(int n)
{
if (n == 1)return 1;
if (n == 2)return 2;
return di_gui(n - 1) + di_gui(n - 2);
}
int main()
{
int n;
cin >> n;
cout << di_gui(n) << endl;
}也是连续发了好几道基础的递归题目
给大家总结一下 递归的要点
1.递归边界 我们知道递归是从复杂向简单 那我们就得知道简单是多少
2. 递归关系 有的题是上一个的n倍 如阶乘 fibonacci 则是 前两项的和
找到这两个东西 你就可以尝试写递归了
加油