分享程序员开发的那些事...
更新时间：2022-10-11 18:05:30
小明刚刚看完电影《第39级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!
站在台阶前，他突然又想着一个问题：
如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，那么总共有多少种不同的上法呢？
面对庞大的计算量人力计算肯定不行，请你利用计算机的优势，帮助小明寻找这个答案。
题目告诉我们的已知信息是总共有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
运行截图：