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

一、问题描述

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

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

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

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

二、题目要求

考察

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

三、问题分析

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

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

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

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

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

四、编码实现

#include <iostream>usingnamespacestd;
intsum=0;//定义全局变量sum voidfac(intn,intstep)//函数 {
if(n<0) 
return;
if(n==0&&step%2==0)//如果台阶数为0，步数是偶数 sum++;//sum加加 fac(n-1,step+1);//台阶数减一，步数加一 fac(n-2,step+1);//台阶数减二，步数加一 }
intmain()
{
inti,j,n=39;//初始化 fac(n,0);//调用函数 cout<<sum;//输出结果 return0;
}

五、输出结果

输出结果为：51167078