饭后消化（算法）

YuHaiyang

有A，B两堆石子，分别为m，n个。有以下两种方法取石子：
（1）可以从任意一堆取出任意多的石子；
（2）可以从两堆中取出同样多的石子；
规则：每人一次，交替进行，最后一个取完所有石子的人胜出；
(例：若m=2，n=1，按照以上方法谁先取，谁必输。)
现在要求由你先开始，编程实现输赢情况
Input：
1   2
1   3
2   4
Output：（0是输，1是赢）
0
1
1

这个估计O(N)的复杂度都不够，最好能推出公式来

hsc

这些很像ACM题啊，完全模式一样，呵呵

YuHaiyang

hsc 发表于 2011-10-9 14:09
这些很像ACM题啊，完全模式一样，呵呵

应该确实是吧..在一个group里看到的

zouquan

设两堆石头分别是m和n，m>=n
if n=0, 输出1 （1把取完）
if m=n,输出1 （1把取完）
if m=2,n=1 输出0
else if m-n=1, 输出1，(1把取成m=2，n=1)
if n=1,m>2 输出1，（1把取成m=2，n=1）
if n=2,m>2 输出1，（1把取成m=1，n=2）
if n=3,m=5 输出0 ，（怎么取都把机会留给对方）
if n=3,m>5 输出1，（1把取成m=5，n=3）
if m-n=2, n>3 输出1，（1把取成m=5，n=3）
if n=4，m=7 输出0

得出规律
n   m   输出  差
1   2   0       1
3   5   0       2
4   7   0       3
5   9   0       4
当n>2时，如果m=2n-1则输出0，其余都输出1
可用数学归纳法证明，并得出解法。

别做这高中数学题，耽误时间，呵呵，有时间读读paper:)   

YuHaiyang

zouquan 发表于 2011-10-9 14:57
设两堆石头分别是m和n，m>=n
if n=0, 输出1 （1把取完）
if m=n,输出1 （1把取完）

= =!这个不算高中题吧..饭后消化玩玩
这个算法是有问题的比如5,9，输出是1，比如我从11里取6个，对方就是必输策略了，对我就是必胜了，输出该为1.这个是因为5在上一个必败策略中出现过了，是3,5,。所以下一个必败策略不能出现5

zouquan

哈哈，有意思，我没考虑到，不过我没时间想了~~

tangzk

尼姆博弈理论，经典取石子游戏啊。
可惜每一次学会后又忘记了，汗！~