问题描述:

小明刚刚看完电影《第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;
} 
 
 


立志成为一名攻城狮