机器学习和生物信息学实验室联盟

标题: 饭后消化（算法） [打印本页]

作者: YuHaiyang 时间: 2011-10-9 12:58
标题: 饭后消化（算法）
有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 时间: 2011-10-9 14:09
这些很像ACM题啊，完全模式一样，呵呵

作者: YuHaiyang 时间: 2011-10-9 14:44

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

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

作者: zouquan 时间: 2011-10-9 14:57
设两堆石头分别是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 时间: 2011-10-9 15:56

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 时间: 2011-10-9 16:52
哈哈，有意思，我没考虑到，不过我没时间想了~~

作者: tangzk 时间: 2011-10-13 14:25
尼姆博弈理论，经典取石子游戏啊。
可惜每一次学会后又忘记了，汗！~

欢迎光临机器学习和生物信息学实验室联盟 (http://123.57.240.48/)