/**
* 题目描述：
小明刚刚看完电影《第39级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!
站在台阶前，他突然又想着一个问题：
如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？
输出格式：
输出一个整数
解题思路：
不用管是左脚还是右脚迈，只要走的步数是偶数即可。递归的思想。
*
*/
public class Main2 {
public static void main(String[] args) {
long time = System.currentTimeMillis();
f(
39,
0);
System.out.println(count);
System.out.println(System.currentTimeMillis()-time);
}
static int count=
0;
static void f(
int stair,
int step){
if(stair<
0)
return;
if(stair==
0){
if(step%
2==
0){
count++;
return;
}
}
f(stair-
1,step+
1);
f(stair-
2,step+
1);
}
}
