将军鬼上身啦！
打败万恶的ghost以后，将军准备回寝室告诉大伙儿这个消息，没想到杯具又发生了… 你知道有种鬼叫“路鬼”吗？让人莫名其妙的迷路，将军就被这种鬼上身了。将军本来要上楼的，但是因为鬼上身，他要不就上一层楼，要不就下一层楼，这个是随机的，他不能控制自己啦！ 假设将军住在第M楼，刚开始将军在K楼，因为体力原因，将军只能上或者下N次楼，假设东6宿舍共有100层。现在问当体力消耗完的时候，将军刚好回到寝室那一层有多少种走法。 例如：将军住在5楼，将军能上或者下5次楼，现在在1楼， 那么将军将回不到寝室啦，为什么？我也不知道。  Input
有多组测试数据，每组测试数据共一行，为M,N,K（0 < N < 21,0 < M,K < 101）的值，中间以空格分开,分别代表将军住在第几层，能移动几次和刚开始在第几层； Output
对应每一组测试数据，输出体力消耗完时将军刚好回到寝室那一层的走法总数
Sample Input
44 5 41
5 5 1
Sample Output
5
0
不晓得哪个地方错了啊，纠结啊，wrong了很多次，求指导
#include<stdio.h>
void f(double c,double n)//用排列组合计算有多少种方法
{ double i=0,s1=1,s2=1;
c=(n-c)/2;
for(i=n;i>(n-c);i--)
 s1=i*s1;
for(i=1;i<=c;i++)
s2=s2*i;
printf("%.lf\n",s1/s2);

}
void main()
{ void f(double c,double n);
    double flour,flour1;
 double n,c,m,m2;
 int m1;
while(scanf("%lf %lf %lf",&flour,&n,&flour1)!=EOF)
{ if(flour>0&&flour<101&&n>0&&n<21&&flour1>0&&flour1<101)
{

c=m=m2=m1=0;
if(flour>flour1) c=flour-flour1;
else c=flour1-flour;
m=(n-c)/2;
m1=m;
m2=m1;
if(m2!=m)
printf("%.lf\n",0);
else
f(c,n);

}
}
}
我的思路是采用排列组合即

数据量比较大，应该用大数运算吧

学习！！

楼主和小曹的分析中忽略了一个隐含条件——这座楼有100层。

这意味着当他在100层时不可能继续向上走，只能向下。

同样，当他在1层时不可能继续向下走，只能向上（没有地下室）。

因为这个限制条件，使得从组合数学的角度分析这个问题变得很困难，这相当于给杨辉三角加了两条边界，不能无限地向左右扩展。

换一个思路，从动态规划的角度来分析，这个问题将变得清晰简单。

设f(i,j)为将军从初始楼层经过j次上下楼到达第i层的走法总数，那么

f(i,j) = f(i-1, j-1) + f(i + 1, j-1)

初始条件为f(k,0) = 1, f(i,0) = 0 (i != k)

因为楼的高度是一个常数，所以时间复杂度为O(n)。

由上面结构式可以确定f(i, j)的数值小于 2^j，当j取最大值20时，结果小于2^20，这并没有超出32位整型的表达范围，所以不需要大数运算。

如果上下都是完全随机 从数学意义上来讲将军不是一直原地踏步吗 小白看不懂这么长的程序啊

哦，是哦，确实没考虑到，杨大哥的做法应该是正确的

从解题的角度讲，动规处理算法简单、代码容易编写。但从研究的角度讲，组合数学分析更有意思，也许更能揭示问题的本质，理论上能构建一个O(1)的算法（不考虑组合运算本身的复杂度）。

既然我们并不是参加比赛时做这题，不妨从各个角度都观察一下这题，挺有意思的。

在西南大学的OJ上发现了这题（题号324），顺手提交了一下，AC。这里把代码发上来供大家交流

#include<stdio.h>

int f(int m, int n, int k)
{
    int a[102] = {0}, b[102] = {0}, *pa = a, *pb = b, *pt, i, j;
    for(a[m] = 1, i = 0; i < n; i++, pt = pa, pa = pb, pb = pt)
    for(j = 1; j <= 100; j++)
        pb[j] = pa[j - 1] + pa[j + 1];
    return pa[k];
}

int main()
{
    int m, n, k;
    while(scanf("%d%d%d", &m, &n, &k) != EOF) printf("%d\n", f(m, n, k));
    return 0;
}

我的代码还有优化的空间。

实际计算时，一次计算的范围只是上一次计算范围向两边扩展1（其余的地方都是0，想想杨辉三角），利用这一点可以比我上面的代码最多减少一半的计算量。

实现起来比上面代码略为复杂一点，但也算不上难，有兴趣的可以试一下。

虽然新手现在一时看不懂大神的代码，但觉得大神的代码挺有意思的，计算也没花多少时间，
比起用递归算，快多了.
不过小弟还是不晓得用排列组合错在哪儿
看来小弟还要多多努力啊

#include<stdio.h>
void f(int m,int n,int k)
{
    int a[102] = {0}, b[102] = {0}, *pa = a, *pb = b, *pt, i, j;
    for(a[m] = 1, i = 1; i <= n; i++, pt = pa, pa = pb, pb = pt)
        for(j = (m-i>=1?m-i:1); j <= (m+i<=100?m+i:100); j++)
            pb[j] = pa[j - 1] + pa[j + 1];
    printf("%d\n",pa[k]);
}
void main()
{
    int m, n, k;
    scanf("%d%d%d", &m, &n, &k);
    f(m, n, k);
}

杨哥厉害，我按照你的方法优化了一下，输入50 20 36时总共计算了440次，输出1140