Question

C语言题目,求代码

第39级台阶

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

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

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

Answer 1

思路1：递归求解

b 用来表示左脚还是右脚:

b=0， 表示这一步要跨左脚 ，（也表示跨了奇数步）
b=1，表示这一步要跨右脚，（也表示跨了偶数步）
当台阶只剩下一个时，这时 必须要跨右脚，才达到偶数步。

a 用来表示要跨的步数:

当a==2时，不管b==0还是1，都各有一种走法（这两种跨法不同），自己思考是跨左脚还是跨右脚。
我就合成一个了。

已知ans[1]=0,ans[2]=1，下面就可以递归求解了。
思路2：排列组合

答案：
51167078
附上代码：

[cpp] view plaincopy

#include<stdio.h>

int fac(int a, int b)
{
if(a==1)
{
if(b==1)return 1;
return 0;
}
if(a==2)
return 1;
return (fac(a-1,!b)+fac(a-2,!b));
}
int main()
{
printf("%d\n", fac(39,0));
//ans = 51167078 true
return 0;
}

方法二：

[cpp] view plaincopy

#include <stdio.h>

int combination(int m,int n)//c(n,m)
{
int ans=1,i;
for(i=1;i<=m;i++)
ans=ans*(n-m+i)/i;
return ans;
}
int main()
{
int i,ans=0;
int n;
scanf("%d",&n);
for(i=1;i<=n-i;i+=2)
ans+=combination(i,n-i);
printf("%d\n",ans);
return 0;
}