| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 586 人关注过本帖
标题:解答疑惑,求解释。
只看楼主 加入收藏
既生瑜何生亮
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2012-2-7
结帖率:100%
收藏
已结贴  问题点数:10 回复次数:5 
解答疑惑,求解释。
取石子游戏
Time Limit: 1000MS Memory limit: 65536K
题目描述
给定a、b两堆石子,甲乙两人做取石子游戏。游戏规则是:每次可以从其中一堆取走任意数目的石子,且每次只能在其中一堆中取;最后没有石子可取的人判为输。现在已知甲先取石子,问他在先取石子的情况下能否获胜(假设甲乙两位选手足够聪明)。
 

输入
第一行是一个正整数t,下面t行每行有两个整数a,b(0<=a,b<=10^9),分别表示两堆石子的数目
输出
对于每一行输入,若甲能取胜,则输出"Yes",否则输出"No"。(不包括引号部分)
示例输入
2
107 109
10000007 1
示例输出
Yes
Yes
链接地址:http://acm.sdut.
#include<stdio.h>
void main()
{
    int i,m,n,t;
    scanf("%d",&t);
    for(i=1;i<=t;i++)
    {
        scanf("%d%d",&m,&n);
        if(m==n)
            printf("No\n");
        else
            printf("Yes\n");
    }
}
为什么上面这段程序就能AC呢?小弟愚昧,百思不得其解,求高手指点一二。
搜索更多相关主题的帖子: 游戏 Memory 正整数 
2012-02-10 15:07
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:10 
这是涉及博弈论及数论的知识。这两门学科在计算机科学中应用非常广泛,大家应该掌握一些其中的基础知识。
这个取石子游戏是尼姆博弈的一个子集(尼姆博弈讨论的是三堆物品的情况),及(0, a, b)的情况。当a = b时是一个奇异局势,面对这一局势者必败。
(0, 0)必败;
(1, 1)必败;
(n, n)先取者无论从哪堆中取走k个(k <= n),后取者都可从另一堆中也取走k个,使之后的局势仍保持 a = b。先取必败。
而当a != b时(设a < b),面对这一局势者都可以从多的一堆中取走b - a的物品使之变为奇异局势,必胜。

重剑无锋,大巧不工
2012-02-10 15:49
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:0 
回复 2楼 beyondyf
表示看不懂。。。

                                         
===========深入<----------------->浅出============
2012-02-10 16:13
既生瑜何生亮
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2012-2-7
收藏
得分:0 
回复 2楼 beyondyf
懂得真多。佩服佩服。
2012-02-10 16:29
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
回复 laoyang103

所谓局势就是当前石子的状态,即每堆有几个。
所谓奇异局势就是当参与者面对它就必输的局势。

(a, b)表示有两堆,第一堆有a个,第二堆有b个。因为堆没有顺序,可以设a <= b。

(0, 0)是每堆都没有石头的状态。没有可拿的,按照游戏规则面对这一状态的人铁定输了。
(0, 1),一堆已经拿完了,另一堆只有一个石子,这时甲拿走这一石子,乙将面对(0, 0)状态,乙输了。
(0, k),同上,甲只要拿走这k个石子就胜了。因为他们都足够聪明,不会故意败给对方。
以上讨论完了只有一堆的情况。下面讨论有两堆的情况
(1, 1),因为一次只能从一堆中拿。这里题目的描述有点问题,所谓的任意数目不包括0(即不拿)。所以不管甲拿走哪个石子,乙都可以拿走另一个取胜。
(a, b), 0 < a,b这分两种情况,即a == b和 a != b,就是我上一贴讨论的核心内容,通过以上的分析应该可以理解了吧,我就不赘述了。

重剑无锋,大巧不工
2012-02-10 16:41
有容就大
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:东土大唐
等 级:版主
威 望:74
帖 子:9048
专家分:14309
注 册:2011-11-11
收藏
得分:0 
面对相等的两堆石头,先取的那个人必输。
如果不等,先取的那个从多的那一堆取走比少的那一堆多出的几个石头,变成相等的两堆。然后后取的那个面对相等的两堆,他又是先取,必输。

梅尚程荀
马谭杨奚







                                                       
2012-02-10 16:48
快速回复:解答疑惑,求解释。
数据加载中...
 
   



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

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