主题:[讨论]取石头问题
_超.C
[专家分:10] 发布于 2011-05-18 11:56:00
地上有三堆石头,第i堆里面a[i]颗石头,甲乙两人轮流从任意一堆石头中取出来任意多颗,当然取出来的颗数不能超过这堆石头的剩余量,现在告诉你这三堆石头每堆的颗数,如果场上三堆石头都剩余0颗的话,没石头可取的那个人输。
现在要你根据给出每堆石头的数量确定谁赢(假设总是甲现取,且甲乙两人都采取对自己有利的取法)
回复列表 (共25个回复)
11 楼
killergsm [专家分:90] 发布于 2011-05-19 23:24:00
....难道你也是?
12 楼
killergsm [专家分:90] 发布于 2011-05-19 23:26:00
...5楼6楼不都是我,唉~无话可说了
话说你有认真看回答吗?x一不一样还不是一样,6楼有补充
13 楼
_超.C [专家分:10] 发布于 2011-05-19 23:47:00
12楼的哥们,你也没有认真思考,6楼的说的是两堆得情况。从两堆到三堆真的一样吗?
14 楼
killergsm [专家分:90] 发布于 2011-05-20 11:23:00
确实是没考虑清楚,第三种情况很复杂,我整理了一下大概是这样,不知道对不对:
其实只要对几种情况进行判断就可以了.对于数组中只包含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 楼
_超.C [专家分:10] 发布于 2011-05-20 12:04:00
题目是谁取到最后一块石头谁赢
16 楼
windy0will [专家分:2300] 发布于 2011-05-20 12:47:00
这个题目挺有意思的,可以考虑数学归纳法来做。
17 楼
windy0will [专家分:2300] 发布于 2011-05-20 12:47:00
这个题目挺有意思的,可以考虑数学归纳法来做。
18 楼
_超.C [专家分:10] 发布于 2011-05-20 22:20:00
听说要用到 异或 二进制 博弈论
19 楼
cgl_lgs [专家分:21040] 发布于 2011-05-21 07:19:00
其实题目是这样的:
共三堆,但只需要保证场上有两堆就能决定输赢。假设有N堆,那也可以先清场到两堆。
20 楼
sarrow [专家分:35660] 发布于 2011-05-21 08:40:00
“胜势组”如 (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];
就是说,在上述情况下,先手必赢!
我来回复