| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1504 人关注过本帖
标题:将军鬼上身
只看楼主 加入收藏
编程20123165
Rank: 2
等 级:论坛游民
帖 子:11
专家分:26
注 册:2013-5-18
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:13 
将军鬼上身
将军鬼上身啦!
打败万恶的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);

}
}
}
我的思路是采用排列组合即
搜索更多相关主题的帖子: 将军 ghost 
2013-05-24 23:20
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:3 
数据量比较大,应该用大数运算吧
令:
A=ABS(M-K)
如果A>N无解,输出0
B=ABS(N-A)
如果B不是偶数则无解,输出0

如果B是偶数,说明需要N+B/2次上(或者下),B/2次下(或者上)
令X=N+B/2,Y=B/2
想象成在X+1个地方插入Y下(或者上),所以等价于
t1+t2+...tx+1=Y的解数目(ti>=0)
等价于(t1+1)+(t2+1)+...(t(1+1)+1)=Y+X+1
所以解的个数为C(X+Y,X)
2013-05-24 23:57
我叫沃恩
Rank: 12Rank: 12Rank: 12
来 自:Asia
等 级:贵宾
威 望:10
帖 子:1234
专家分:3865
注 册:2013-3-29
收藏
得分:0 
学习!!

因为我是菜鸟,所以应该被骂! 细节+坚持=成功!
2013-05-25 07:32
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:17 
楼主和小曹的分析中忽略了一个隐含条件——这座楼有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位整型的表达范围,所以不需要大数运算。

重剑无锋,大巧不工
2013-05-25 08:57
xhd504070596
Rank: 2
等 级:论坛游民
帖 子:12
专家分:11
注 册:2013-5-24
收藏
得分:0 
如果上下都是完全随机 从数学意义上来讲将军不是一直原地踏步吗 小白看不懂这么长的程序啊
2013-05-25 09:39
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:0 
哦,是哦,确实没考虑到,杨大哥的做法应该是正确的
2013-05-25 11:09
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
从解题的角度讲,动规处理算法简单、代码容易编写。但从研究的角度讲,组合数学分析更有意思,也许更能揭示问题的本质,理论上能构建一个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;
}

重剑无锋,大巧不工
2013-05-25 12:32
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
我的代码还有优化的空间。

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

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

重剑无锋,大巧不工
2013-05-25 12:40
编程20123165
Rank: 2
等 级:论坛游民
帖 子:11
专家分:26
注 册:2013-5-18
收藏
得分:0 
回复 8楼 beyondyf
虽然新手现在一时看不懂大神的代码,但觉得大神的代码挺有意思的,计算也没花多少时间,
比起用递归算,快多了.
不过小弟还是不晓得用排列组合错在哪儿
看来小弟还要多多努力啊
2013-05-25 14:16
Agdmeg
Rank: 4
来 自:四川成都
等 级:业余侠客
威 望:3
帖 子:101
专家分:201
注 册:2011-8-9
收藏
得分: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
2013-05-25 16:11
快速回复:将军鬼上身
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.031560 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved