主题:请帮我看看用啥算法
zoe558880
[专家分:190] 发布于 2006-09-21 16:19:00
取石子游戏
有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目,如果轮到你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。
请帮我看看用啥算法,或解题思路
回复列表 (共12个回复)
11 楼
willzhanglala [专家分:1350] 发布于 2006-10-05 16:47:00
应该是小于且最接近黄金分割比0.618。或者大于且最近于黄金分割比1.618
1,R[M,N]是指如下的范围,(M,1:N) U (1:M,N) U (M-x,N-x) x从0变化到M-x=1或者N-x=1;
定义,如果在R[M,N]范围内,M/N是小于且最接近于0.618的,那么定义M/N是合适的。
2 如果M/N是合适的,那么M-a/N,M/N-a,(M-a)/(N-a),三者肯定都不是合适的。
3,如果M/N不是合适的,那么肯定可以找到M-a/N, M/N-a,(M-a)/(N-a),三者之一是合适的。
a是任意的数。
因为1/2 是合适,并且,1/2是必败的(我要拿的时候,出现1,2我无论怎么拿都必败),
根据第2,第3条。每次总是会找到一个合适的数对,所以最后总是到(1,2)。所以,就找到了这种方法。
但是,第2和第3条怎么证明呢?
12 楼
willzhanglala [专家分:1350] 发布于 2006-10-05 16:55:00
如果是编程可以画一个表格
_0__1__2__3__4__5__________
0| R X X X X X X X
1| X X r x x x x
2| X r X x x x x
3| X x x X x
4| X x x x X x
5| X x x x X
不断搜索和标记X和R,
第一次0,0标记为R,然后将横向,纵向,斜向都标记为X
第二次,搜索(1,1)范围没有发现,空的,搜索(2,2)范围发现(1,2),(2,1)是空的,标记为r,同样横向、纵向、斜向标记x
这里用大小写,区分第一次和第二次,实际是一种标记。
不断类推,第三次就是(3,5)和(5,3)。。。。
直到(M,N)
你只要保证,每次都能取到R上面。
我来回复