D**u
发帖数: 204 | 1 这是一道非常经典的Nim对策题目.
现有两堆石子, 甲乙两人的游戏规则如下: 两人依次从两堆石子中
取走若干石子, 条件是要么从一堆中拿走任意多(至少一个), 要么从
两堆中各拿走同样多(至少一个). 拿走最后一枚石子者赢得胜利.
请问如何判断何时先走(或后走)有必胜策略? 策略为何? | m**e
发帖数: 79 | 2 偶来试试
在下面这些组合时拿石子的会输
1-2 the difference is 1
3-5 the difference is 2
4-7 the difference is 3
6-10 the difference is 4
8-13 the difference is 5
9-15 the difference is 6
11-18 the difference is 7
......
以下相似，依次向上数，碰到前面没出现的数字做为个数少的一堆的数目，
选择个数多的一堆的数目使两堆个数差依次加一。
在这些情况下无论如何拿石子，不会拿成其上总数更少的组合，
而下一个人肯定可以拿成上面的必胜组合而最终获胜。
所以偶的答案是如果出现上面的组合后拿获胜，否则先拿获胜。
不过偶不知道如何算两堆个数差很大时获胜组合的具体数目，只会一个个数//blush
BTW，Nim是什么？
【在 D**u 的大作中提到】
: 这是一道非常经典的Nim对策题目.
: 现有两堆石子, 甲乙两人的游戏规则如下: 两人依次从两堆石子中
: 取走若干石子, 条件是要么从一堆中拿走任意多(至少一个), 要么从
: 两堆中各拿走同样多(至少一个). 拿走最后一枚石子者赢得胜利.
: 请问如何判断何时先走(或后走)有必胜策略? 策略为何?
| n***u
发帖数: 3 | 3 The pairs (1,2), (3,5), (4,7) etc. are losing positions.
Let us denote L1 = (1,2) - the 1st losing position
L2 = (3,5) - the 2nd losing position
... ...
and, Ln = (An, Bn) - the nth losing position
... ...
then we can find non-recursive formula for computing
sequences {An} and {Bn}.
Let G denote the golden ratio, or (1+sqrt(5))/2.
then An is given by floor(n*G) and Bn is given by
floor(n*G^2).
【在 D**u 的大作中提到】
: 这是一道非常经典的Nim对策题目.
: 现有两堆石子, 甲乙两人的游戏规则如下: 两人依次从两堆石子中
: 取走若干石子, 条件是要么从一堆中拿走任意多(至少一个), 要么从
: 两堆中各拿走同样多(至少一个). 拿走最后一枚石子者赢得胜利.
: 请问如何判断何时先走(或后走)有必胜策略? 策略为何?
|
|
