主题：[讨论]取石头问题
_超.C
[专家分：10] 发布于 2011-05-18 11:56:00
地上有三堆石头，第i堆里面a[i]颗石头，甲乙两人轮流从任意一堆石头中取出来任意多颗，当然取出来的颗数不能超过这堆石头的剩余量，现在告诉你这三堆石头每堆的颗数，如果场上三堆石头都剩余0颗的话，没石头可取的那个人输。
现在要你根据给出每堆石头的数量确定谁赢（假设总是甲现取，且甲乙两人都采取对自己有利的取法）
回复列表 （共25个回复）
沙发
漫步归来 [专家分：0] 发布于 2011-05-18 14:47:00
呵呵~~有意思的~
板凳
fragileeye [专家分：1990] 发布于 2011-05-18 18:11:00
这题有相应算法的。。
3 楼
sarrow [专家分：35660] 发布于 2011-05-18 20:27:00
用动态规划——逆推。
思路没什么困难的，就是写程序会比较纠结。
以前做过一个类似的，区别只是判断胜负的标准——我做的那个是最后取完的那个人输。
> 这题有相应算法的。。
就是不知道有没有可以推导的公式。
再多写一点思路吧：
将问题对象用一个三元组『x,y,z』来表示——并且这个三元组的xyz没有顺序的关系。就是
说，『x,y,z』和『y,z,x』、……，『z,x,y』等价。
初态：『0,0,0』，显然是“甲”输——他已经无石头可取。如果看作函数，结果0和1分别
表示“甲”输和赢。
那么，上面可记为：f(0,0,0) = 0
于是有：
f(0,0,1) = 1
为什么呢？
因为状态『0,0,1』只需要一步就能变到『0,0,0』，所以，这种状态下，“甲”必赢。
以此类推，问题可解。
总之，编写程序的话，注意弄一个数据结构保存状态，就行了。
4 楼
fragileeye [专家分：1990] 发布于 2011-05-18 23:01:00
感谢ls提供如此多的思路。翻了下书，貌似问题的关键就是书中所谓的“胜势组”--Wythoff对，博弈论的知识。不懂的飘过。。
不过lz的题目要求是不够的，原意可能是这样的：可以从某一堆取出若干石子，数量不限，也可以同时从两堆取石子。要求两堆取出的石子数相等，每次必须取石子，取出最后一粒石子者为胜。
“胜势组”如 (1,2) (3,5) (4, 7) (6 ,10) (8 , 13)... ---据说可以延伸为3组的情况
书上这么介绍: 当A取子后出现(1 ,2)，B方必须取子，显然无论B怎么取子，A都是胜者、、
至于程序操作的细节，得参考下书、、
5 楼
killergsm [专家分：90] 发布于 2011-05-19 10:11:00
其实只要对几种情况进行判断就可以了.对于数组中只包含1个石头的特殊情况很容易判断,这里对一般情况进行分析.其中x代表除1以外的任意数.
情况1: 0 0 x
这种情况甲是必胜的,只要将x取为1即可
情况2: 0 x x
这种情况甲必败,理由如下
若甲将x取为0,则乙面对情况1,乙必胜;
若甲将x取为1,则乙将x取为1,甲面对 0 1 1 的情况,甲必败;
若甲将x取为非1的数如y,则乙将另外的x取为y,直到甲将其中之一取为1为止,甲必败
情况3: x x x
甲必胜,因为甲可以将任一x取为0,则乙面对情况二,乙必败
6 楼
killergsm [专家分：90] 发布于 2011-05-19 21:23:00
今天参加我们学校的一个acm宣讲会,提到了这个问题,我发现上面有考虑不周全的地方,
就是出现 0 x x时两个x可能会一个大一个小的问题,这种情况是甲必胜的,
因为只要甲将大的取到跟小的一样多就出现了情况2,而乙面对情况2是必败的
7 楼
_超.C [专家分：10] 发布于 2011-05-19 22:58:00
6楼的哥们 是xidian的吧？
8 楼
_超.C [专家分：10] 发布于 2011-05-19 23:05:00
5楼的哥们，三堆石头的数目是随机的，并不一定相等。
9 楼
_超.C [专家分：10] 发布于 2011-05-19 23:09:00
希望有高人飘过并顺便解决一下
10 楼
fragileeye [专家分：1990] 发布于 2011-05-19 23:14:00
又一个xidian的。。这t靠你自己了，没有时间写代码撒。。(如果你也是xidian的，去图书馆找一本《计算机常用算法与程序设计》，上面稍微有讲，应该还有一本)
我来回复
您所在位置：