回 帖 发 新 帖 刷新版面

主题:[讨论]取石头问题

地上有三堆石头,第i堆里面a[i]颗石头,甲乙两人轮流从任意一堆石头中取出来任意多颗,当然取出来的颗数不能超过这堆石头的剩余量,现在告诉你这三堆石头每堆的颗数,如果场上三堆石头都剩余0颗的话,没石头可取的那个人输。 
 现在要你根据给出每堆石头的数量确定谁赢(假设总是甲现取,且甲乙两人都采取对自己有利的取法)

回复列表 (共25个回复)

11 楼


....难道你也是?

12 楼

...5楼6楼不都是我,唉~无话可说了
话说你有认真看回答吗?x一不一样还不是一样,6楼有补充

13 楼


12楼的哥们,你也没有认真思考,6楼的说的是两堆得情况。从两堆到三堆真的一样吗?

14 楼

确实是没考虑清楚,第三种情况很复杂,我整理了一下大概是这样,不知道对不对:
其实只要对几种情况进行判断就可以了.对于数组中只包含1个石头的特殊情况很容易判断,这里对一般情况进行分析.其中x代表除1以外的任意数.
情况1: 0      0      x
这种情况甲是必胜的,只要将x取为1即可
情况2: 0      x1      x2     (x1>x2)
这种情况甲必胜,理由如下
若甲将x1取为x2,则变成  0     x2     x2
此时若乙将x2取为0,则乙面对情况1,乙必胜;
若乙将x2取为1,则甲将另一x2取为1,乙面对 0      1      1 的情况,乙必败;
若乙将x2取为非1的数如y,则甲将另外的x2取为y,直到乙将其中之一取为1为止,乙必败
如果开始x1=x2,则甲必败
情况3: x1      x2      x3  
若其中有两项相等则是甲必胜,假如x2 = x3,甲可以将x1直接取0导致乙面对 0     x     x的局面必败;
若三项都不等,则谁先将其中两项取到相等或将其中一项取到0或1谁就输;
所以谁先面对2    3   4的情况谁就输了,甲可以将x1取为2,则乙只能将x2取为y,此时假设x2,x3中没有3或4,
此时甲将3取为y+1或y-1,知道乙取到3或4时,甲将令一组取为4或3,形成 2    3    4,则甲胜;
当然,如果开始三堆中包含3或4的特殊情况,如:
2    3    4      乙胜
x1    x2    3/4      甲胜(甲将3/4取为2)
x1    5    6      乙胜
2    x2    x3    乙胜
2    3/4    x3    甲胜

x1    x2    x3    甲胜  x!=2 3 4
0     x1    x2    甲胜  若x1=x2则乙胜
0     0     x     甲胜  x!=1

15 楼

题目是谁取到最后一块石头谁赢

16 楼

这个题目挺有意思的,可以考虑数学归纳法来做。

17 楼

这个题目挺有意思的,可以考虑数学归纳法来做。

18 楼

听说要用到 异或  二进制  博弈论

19 楼

其实题目是这样的:
共三堆,但只需要保证场上有两堆就能决定输赢。假设有N堆,那也可以先清场到两堆。

20 楼

“胜势组”如 (1,2) (3,5) (4, 7) (6 ,10) (8 , 13)... ---据说可以延伸为3组的情况

三组情况下,部分“胜势组”:
[0,0,1];
[0,2,2];
[0,3,3];
[0,4,4];
[1,1,1];
[1,2,3];
[1,4,5];
[2,4,6];

就是说,在上述情况下,先手必赢!

我来回复

您尚未登录,请登录后再回复。点此登录或注册