821. 跳台阶
难度:困难 |
---|
时/空限制:1s / 64MB |
总通过数:1370 |
总尝试数:1828 |
来源:语法题 |
算法标签: 函数 |
一个楼梯共有n级台阶,每次可以走一级或者两级,问从第0级台阶走到第n级台阶一共有多少种方案。
输入格式
共一行,包含一个整数n。
输出格式
共一行,包含一个整数,表示方案数。
数据范围
1≤n≤15*
输入样例:
5
输出样例:
8
思路:
假设调到第n个台阶的方法数是 f(n) 每次跳能跳1 ~ k个台阶(k > 1).
当 n > k 时
调到第n个台阶只要在第n-1,n-2,n-3.... n-k个台阶的其中之一再跳一次就可以
所以跳到第n个台阶的方法数是
$$
f(n) = f(n-1)+f(n-2)+......+f(n-k)
$$
当n = k 时
$$
f(n) = f(n-1)+f(n-2)+......+f(1)+1
$$
当 1 < n < k 时
$$
f(n) = f(n-1)+f(n-2)+......+f(1)
$$
由题意可得 看 k = 2 ,f(1) = 1,f(2) = 2
C++
#include<iostream>
#include<cstdio>
using namespace std;
int tiao(int x)
{
if(x == 1)return 1;
if(x == 2) return 2;
return tiao(x-1) + tiao(x -2);
}
int main(void)
{
int n ;
cin >> n;
cout << tiao(n) << endl;
}