算法题每日一练 --- 第 11 天：第 39 级台阶

一、问题描述

小明刚刚看完电影《第 39 级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是 39 级!

站在台阶前，他突然又想着一个问题：

如果我每一步只能迈上 1 个或 2 个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完 39 级台阶，那么总共有多少种不同的上法呢？

面对庞大的计算量人力计算肯定不行，请你利用计算机的优势，帮助小明寻找这个答案。

二、题目要求

考察

1.递归性、规律性2.建议用时10~25min

运行限制

• 最大运行时间：1s

• 最大运行内存: 128M

三、问题分析

题目告诉我们的已知信息是总共有 39 个台阶，每一次只能跨越一个或者两个，而且要求跨越的总步数必须是偶数。

假如将上述题目中的步数要求为偶数给去掉，那么通过普通的斐波那契数列就可以解决这个问题。

if(n==1) return 1;//只有一级台阶，输出1步if(n==2) return 2;//两级台阶，可以先走一步再走一步，或者直接走两步，所以两种else return fac(n-1)+fac(n-2);//总的规律性

加上这一个条件，我们也只需要加上一个步数判断就行了。走一步跨越 1 个台阶，调用函数，步数加一。走一步跨越 2 个台阶，调用函数，步数加一。假如台阶数已经走完了，只需要判断步数是否为偶数。

判断条件为：if(n==0&&step%2==0)

四、编码实现

#include <iostream>using namespace std;int sum=0;//定义全局变量sum void fac(int n,int step)//函数 {  if(n<0)     return;  if(n==0&&step%2==0)//如果台阶数为0，步数是偶数     sum++;//sum加加   fac(n-1,step+1);//台阶数减一，步数加一   fac(n-2,step+1);//台阶数减二，步数加一 }int main(){  int i,j,n=39;//初始化   fac(n,0);//调用函数   cout<<sum;//输出结果     return 0;}

五、输出结果

输出结果为：51167078 运行截图：