回 帖 发 新 帖 刷新版面

主题:请帮我看看用啥算法

取石子游戏

有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目,如果轮到你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。


请帮我看看用啥算法,或解题思路

回复列表 (共12个回复)

11 楼

应该是小于且最接近黄金分割比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 楼

如果是编程可以画一个表格
   _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上面。

我来回复

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