题目描述
小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级!
站在台阶前,他突然又想着一个问题:
如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,也就是说一共要走偶数步。那么,上完39级台阶,有多少种不同的上法呢?
请你利用计算机的优势,帮助小明寻找答案。
要求提交的是一个整数。
注意:不要提交解答过程,或其它的辅助说明文字。
答案:51167078
样例
```
//说实话吧,真是说数学题,花了好多时间,比赛肯定想不到
//我的思路:
//1.用 阶梯数 - 步数 得到跨阶梯数为 2的次数,再就易得到 1的个数
//2.运用 组合 得到该步数的几种上法
//3.最后相加得到结果
#include<stdio.h> //组合
long long fac(long long a)
{
for(int i=a-1; i>=1; i--)
{
a = a * i;
}
return a;
}
int main()
{
long add = 0, tot = 0;
int bu = 20;//20 到 38 步
int a;//跨2次数
int b;//跨1次数
int q,w;
int max, min;
for(bu=20; bu<=38; bu++)
{
if(bu%2 != 0)
{
++bu;
}
a = 39 - bu;
b = bu - a;
max = a>b ? a:b;
min = a<b ? a:b;
q = fac(max);
w = fac(min)*fac(max - min);
add = q / w;
tot = tot + add;
}
printf("%lld", tot);
return 0;
}
//我的天,崩溃了,天哪,这求阶乘long long只能求到20的,38求不到啊!
//思路没问题呀????
//先把错的交下,有时间研究!
正解来了!!哎 还要努力继续
#include<stdio.h>
int ans = 0;
int f(int n, int step)//n为剩余的阶梯数,step为迈出的步数
{
if(n < 0)return 0;
if(n == 0 && step % 2 == 0)ans++;
f(n-1, step+1);
f(n-2, step+1);
}
int main()
{
f(39, 0);
printf("%d", ans);
return 0;
}