2013年 C/C++ B组第三题

问题描述：

小明刚刚看完电影《第39级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!站在台阶前，他突然又想着一个问题： 如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步 那么，上完39级台阶，有多少种不同的上法呢？

一般这种上台阶的问题，涉及到问题的重复就会想用递归去解决，代码分析如下：

#include<iostream>
using namespace std;

int ans = 0;  //用于计数

void f(int i , int step) //i表示剩余的台阶，step表示已走的步数 
{
	if(i < 0)       //当剩余台阶数小于零，不符合题意，肯定就要返回了
		return; 
	if(i == 0 && step % 2 == 0)   //当楼梯走完了并且步数是偶数
		ans++; 
	f(i - 1 , step + 1);     //递归下去，第一种是只走一步
	f(i - 2 , step + 1);     //第二种是走两步
}

int main ()
{
	 
	f(39 , 0);  //调用递归函数
	cout << ans << endl;
        return 0;
}