g***s
发帖数: 3811 | 1 题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
１比较容易，２难一些. |
g**e
发帖数: 6127 | 2 第一题先取的人必胜，只要每次都把一堆留下两根，剩下的都拿走。不管第二个人怎么
拿，都有必胜的办法。
第二题还没想特别清楚，感觉如果是奇数堆火柴，先拿取胜。偶数堆就是后拿取胜
，可
【在 g***s 的大作中提到】
: 题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
: 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
: 题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
: 将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
: １比较容易，２难一些.
|
g***s
发帖数: 3811 | 3 只能从"一堆"中取
【在 g**e 的大作中提到】
: 第一题先取的人必胜，只要每次都把一堆留下两根，剩下的都拿走。不管第二个人怎么
: 拿，都有必胜的办法。
: 第二题还没想特别清楚，感觉如果是奇数堆火柴，先拿取胜。偶数堆就是后拿取胜
:
: ，可
|
g**e
发帖数: 6127 | 4 不是有若干堆吗，你的意思是一堆没取完，不能动下一堆？
【在 g***s 的大作中提到】
: 只能从"一堆"中取
|
g***s
发帖数: 3811 | 5 一次从两堆里取
【在 g**e 的大作中提到】
: 不是有若干堆吗，你的意思是一堆没取完，不能动下一堆？
|
A***M
发帖数: 18 | 6 1是比较简单。异或所有堆的数目。每次从某堆取一些， 使这个异或值为0。
2也类似吧。 还在想。
，可
【在 g***s 的大作中提到】
: 题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
: 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
: 题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
: 将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
: １比较容易，２难一些.
|
g**********y
发帖数: 14569 | |
b**********r
发帖数: 91 | 8 nim number problem. (1) make all nums xor equals to 0 (2) make all nums xor
equals to 1
，可
【在 g***s 的大作中提到】
: 题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
: 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
: 题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
: 将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
: １比较容易，２难一些.
|
g**e
发帖数: 6127 | 9 各位大牛都太厉害了
【在 g**********y 的大作中提到】
: http://en.wikipedia.org/wiki/Nim
|
g**********y
发帖数: 14569 | 10 我是后知后觉 + 偷懒 + 问人 + Google，Bravethinker是博学
【在 g**e 的大作中提到】
: 各位大牛都太厉害了
|
|
|
r*******y
发帖数: 1081 | 11 consider the simple case firstly ?
，可
【在 g***s 的大作中提到】
: 题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
: 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
: 题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
: 将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
: １比较容易，２难一些.
|
g***s
发帖数: 3811 | 12 2不对。
比如 3 3 3 3
xor
【在 b**********r 的大作中提到】
: nim number problem. (1) make all nums xor equals to 0 (2) make all nums xor
: equals to 1
:
: ，可
|
g***s
发帖数: 3811 | 13 这个只给了1的解答。1是比较容易的。
【在 g**********y 的大作中提到】
: http://en.wikipedia.org/wiki/Nim
|
g**********y
发帖数: 14569 | 14 3 3 3 3想起来比较抽象，{3，2}就可以。
按XOR=1, player 1该取成{1, 2}, 但是player 2把2取走，player 1就必胜了。
【在 g***s 的大作中提到】
: 2不对。
: 比如 3 3 3 3
:
: xor
|
g***s
发帖数: 3811 | 15 我是说3 3 3 3 按这个方法不对。
3 3 3 3实际是必败的一个状态.
【在 g**********y 的大作中提到】
: 3 3 3 3想起来比较抽象，{3，2}就可以。
: 按XOR=1, player 1该取成{1, 2}, 但是player 2把2取走，player 1就必胜了。
|
g**e
发帖数: 6127 | 16 偶数堆先拿必败吧，我感觉
【在 g***s 的大作中提到】
: 我是说3 3 3 3 按这个方法不对。
: 3 3 3 3实际是必败的一个状态.
|
g***s
发帖数: 3811 | 17 不一定。例如3 1 1 1 或者1 1
【在 g**e 的大作中提到】
: 偶数堆先拿必败吧，我感觉
|
g**e
发帖数: 6127 | 18 1 1 怎么不是先拿必败？第一个人只能拿一根，第二个人就赢了
是不是我理解错了第二题意？
【在 g***s 的大作中提到】
: 不一定。例如3 1 1 1 或者1 1
|
g***s
发帖数: 3811 | 19 取到最后一根的败啊
【在 g**e 的大作中提到】
: 1 1 怎么不是先拿必败？第一个人只能拿一根，第二个人就赢了
: 是不是我理解错了第二题意？
|
g***s
发帖数: 3811 | 20 这是大学算法课的一个作业。后来发到了学校的bbs上，刚刚查了一下，居然有人放到
blog里面了。
http://blog.163.com/gditacmfeng@yeah/blog/static/13702062420100
先解决第1题
定义1：若所有火柴数异或为0，则该状态被称为利他态，用字母T表示；否则，为利己
态，用S表示。
定理1：对任何S态，存在方法，从其中取一堆中的若干根，使状态变为T态。
引理1.1 ：A(i)为非副整数，i=1..n, 记c=A(1) xor A(2) xor …… xor A(n),若c>0
,则存在A(t), A(t) xor c
证明： 把c表示成二进制，记它的二进制数的最高位为第p位，则必然存在一个A(t),它
二进制的第p位也是1。（否则，若所有的A(i)的第p位都是0，c的第p位就也为0，矛盾
！）
x=a(t) xor c 的第p位将为1 xor 1,即0；
又因为c的最高位为p，所以x高于p位的值不变。所以必有x
. 命题得证。
再来证定理1.
证明：
设共有n堆火柴，每堆的数目分别为A(i)，i=1..n，A(i)为非副整数.
记c=A(1) xor A(2) xor …… xor A(n),
因为是S态，所以 c>0;
所以存在A(t), A(t) xor c
A(t)' = A(t) xor c
c' = A(1) xor A(2) xor … xor A(t)' xor … xor A(n)
= A(1) xor A(2) xor … xor A(t) xor c xor … xor A(n)
= A(1) xor A(2) xor … xor A(t) xor … xor A(n) xor c
= c xor c = 0
所以，用把第t堆由A(t)根取成A(t)' 根（A(t)' = A(t) xor c
故命题成立。 #
定理2：T态，取任何一堆的若干根，都将成为S态。
证明：反证法：
反设存在一堆，记为第m堆，从中取了若干根，根数由A(m)变为A(m)' .
A(m)>A(m)' 状态均为T态。
记c=A(1) xor A(2) xor … xor A(m) xor… xor A(n),
记c'=A(1) xor A(2) xor … xor A(m)' xor… xor A(n),
c=0;c'=0;
所以有 0= A(1) xor A(2) xor … xor A(m) xor… xor A(n)
= A(1) xor A(2) xor … xor A(m-1) xor A(m+1) xor… xor A(n) xor A(m)
= d xor A(m)
d= A(1) xor A(2) xor … xor A(m-1) xor A(m+1) xor… xor A(n)
故 A(m)=d
同理， d xor A(m)' =0
A(m)'= d
所以，A(m)'=A(m) . 矛盾！
故反设不成立。原命题成立。 #
定理 3：S态，只要方法正确，必赢。
最终胜利即由S态转变为T态，任何一个S态，只要把它变为T态，（由定理一，可以把它
变成T态。）对方只能把T态转变为S态(定理2)。这样，所有S态向T态的转变都可以有己
方控制，对方只能被动地实现由T态转变为S态。故S态必赢。 #
定理4：T态，只要对方法正确，必败。
由定理3易得。
我们再来处理第2题。我们会发现两题会有一些相同之处，控制S->T态的人控制着主动权
。经过分析，我们有以下结论：
定义2：若一堆中仅有1根火柴，则被称为孤单堆。若大于1根，则称为充裕堆。
定义3：T态中，若充裕堆的堆数大于等于2，则称为完全利他态，用T2表示；若充裕堆的
堆数等于0，则称为部分利他态，用T0表示。
定理4：不存在充裕堆数为1的T态。
证明：
孤单堆的根数异或只会影响二进制的最后一位，但充裕堆会影响高位（非最后一位）。
一个充裕堆，高位必有一位不为0，则所有根数异或不为0。故不会是T态。
定义4：S态中，若充裕堆的堆数大于等于2，则称为完全利己态，用S2表示；若充裕堆的
堆数等于1，则称为自主利己态，用S1表示; 若充裕堆的堆数等于0，则称为部分利己态
，用S0表示。
定理4：S0态，即仅有奇数个孤单堆，必败。T0态必胜。
证明：S0态，其实就是每次只能取一根。每次第奇数根都由己取，第偶数根都由对方取
，所以最后一根必己取。败。
同理, T0态必胜#
定理5：S1态，只要方法正确，必胜。
证明：若此时孤单堆堆数为奇数，把充裕堆取完；否则，取成一根。
这样，就变成奇数个孤单堆，由对方取。
由定理4，对方必输。己必胜。 #
定理6：S2态不可转一次变为T0态。
证明：充裕堆数不可能一次由2变为0。得证。 #
定理7：S2态可一次转变为T2态。
证明：由定理1，S态可转变为T态，态可一次转变为T态
又由定理6，S2态不可转一次变为T0态，
所以转变的T态为T2态。 #
定理8：T2态，只能转变为S2态或S1态。
证明：. 由定理2，T态必然变为S态。
由于充裕堆数不可能一次由2变为0，所以此时的S态不可能为S0态。
命题得证。
定理9：S2态，只要方法正确，必胜.
证明：方法如下：
1） S2态，就把它变为T2态。（由定理7）
2） 对方只能T2转变成S2态或S1态(定理8)
若转变为S2, 转向1）
若转变为S1, 这己必胜。（定理5）
定理10：T2态必输。
证明：同9。
综上所述，必输态有： T2,S0
必胜态： S2,S1,T0.
两题比较：
第一题的全过程其实如下：
S2->T2->S2->T2-> …… ->T2->S1->T0->S0->T0->……->S0->T0(全0)
第二题的全过程其实如下：
S2->T2->S2->T2-> …… ->T2->S1->S0->T0->S0->……->S0->T0(全0)
下划线表示胜利一方的取法。
是否发现了他们的惊人相似之处。
我们不难发现(见加黑部分)，S1态可以转变为S0态（第二题做法），也可以转变为T0（
第一题做法）。哪一方控制了S1态，他即可以有办法使自己得到最后一根（转变为T0）
,也可以使对方得到最后一根（转变为S0）。
所以，抢夺S1是制胜的关键！
为此，始终把T2态让给对方，将使对方处于被动状态，他早晚将把状态变为S1.(见定
理9的证明). |
|
|
g**********y
发帖数: 14569 | 21 如果没有见过解法，面试时就解出来，也太牛了。我是慢慢想都只能解特殊情况。不知道什么时候能全解。
>0
【在 g***s 的大作中提到】
: 这是大学算法课的一个作业。后来发到了学校的bbs上，刚刚查了一下，居然有人放到
: blog里面了。
: http://blog.163.com/gditacmfeng@yeah/blog/static/13702062420100
: 先解决第1题
: 定义1：若所有火柴数异或为0，则该状态被称为利他态，用字母T表示；否则，为利己
: 态，用S表示。
: 定理1：对任何S态，存在方法，从其中取一堆中的若干根，使状态变为T态。
: 引理1.1 ：A(i)为非副整数，i=1..n, 记c=A(1) xor A(2) xor …… xor A(n),若c>0
: ,则存在A(t), A(t) xor c : 证明： 把c表示成二进制，记它的二进制数的最高位为第p位，则必然存在一个A(t),它
|
g***s
发帖数: 3811 | 22 这个做面试题太难。是一道课后选题，老师也没有答案的那种。
知道什么时候能全解。
【在 g**********y 的大作中提到】
: 如果没有见过解法，面试时就解出来，也太牛了。我是慢慢想都只能解特殊情况。不知道什么时候能全解。
:
: >0
|
d*******l
发帖数: 338 | |
s*****y
发帖数: 897 | 24 这个真是google得面试题阿
http://23.latest.careercup.appspot.com/question?id=174666
【在 g***s 的大作中提到】
: 这个做面试题太难。是一道课后选题，老师也没有答案的那种。
:
: 知道什么时候能全解。
|
F**r
发帖数: 84 | 25 game theory, simple DP, only 2 values for each state case, win or lose
，可
【在 g***s 的大作中提到】
: 题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
: 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
: 题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
: 将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
: １比较容易，２难一些.
|
g***s
发帖数: 3811 | 26 第一题做面试没问题，并不难。第二题做面试要现场做出来难。
【在 s*****y 的大作中提到】
: 这个真是google得面试题阿
: http://23.latest.careercup.appspot.com/question?id=174666
|
d**e
发帖数: 6098 | 27 看来现在的面试,数学差点都不行...
【在 g**********y 的大作中提到】
: http://en.wikipedia.org/wiki/Nim
|
b*******y
发帖数: 232 | 28 好像第二问就是留一根给对方就行了
，可
【在 g***s 的大作中提到】
: 题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
: 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
: 题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
: 将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
: １比较容易，２难一些.
|
N*2
发帖数: 95 | 29 拜托
人家明明给了1和2的答案
仔细看
【在 g***s 的大作中提到】
: 这个只给了1的解答。1是比较容易的。
|
g***s
发帖数: 3811 | 30 哦。不好意思，没看仔细。
呵呵。
【在 N*2 的大作中提到】
: 拜托
: 人家明明给了1和2的答案
: 仔细看
|
|
|
g**********y
发帖数: 14569 | 31 赞知错就改！
【在 g***s 的大作中提到】
: 哦。不好意思，没看仔细。
: 呵呵。
|
