魔方吧·中文魔方俱乐部

标题: 取石子游戏 [打印本页]

作者: Light 时间: 2010-2-15 18:57:17 标题: 取石子游戏

两个人做取石子游戏，有若干堆石子，每堆都有若干个，两个人轮流取石子，有两种取法：1.在一堆中取任意数量棋子，2.在两堆中取相等数量棋子。取最后一个棋子的人输（也就是说要留给对方最后一个棋子就赢了），如果你是先手，求出在什么情况下必胜，以及必胜方案。
请给予详细讲解，包括必胜的方案中取十字数目的算法，谢谢！

作者: Paracel_007 时间: 2010-2-15 18:59:21

全是若干啊。。。
最近有很多策略的题目啊。。。

作者: Light 时间: 2010-2-15 19:03:17

原帖由 Paracel_007 于 2010-2-15 18:59 发表全是若干啊。。。最近有很多策略的题目啊。。。

呵呵，取法中的第二点“在两堆中取相等数量棋子” ，本来我想写成“在若干堆中取相等数量棋子”的，但是后来由于记不清原题是什么，所以没敢写成若干堆，就写两堆了……不过估计如果能算出两堆就应该能算出若干堆……

作者: tm__xk 时间: 2010-2-15 19:09:54 标题: 回复 3# 的帖子

保守地说一句未必....

作者: yq0711 时间: 2010-2-15 19:25:05

感觉要分单双数讨论吧..具体的做法不是很清楚...

作者: tm__xk 时间: 2010-2-15 20:03:19

两堆的情况:
L= [0, 1], [1, 0], [2, 2], [3, 5], [4, 7], [5, 3], [6, 10], [7, 4], [8, 13], [9, 15], [10, 6],
   [11, 18], [12, 20], [13, 8], [14, 23], [15, 9], [16, 26], [17, 28], [18, 11], [19, 31], [20, 12],
   [21, 34], [22, 36], [23, 14], [24, 39], [25, 41], [26, 16], [27, 44], [28, 17], [29, 47], [30, 49],
   [31, 19], [34, 21], [36, 22], [39, 24], [41, 25], [44, 27], [47, 29], [49, 30];

哪位高手来找下规律....

附件: 1.gif (2010-2-15 20:03:19, 12.44 KB) / 下载次数 70
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=ODg5NDh8MThlMDE4MDN8MTc0NzE2MTA3OXwwfDA%3D

作者: Paracel_007 时间: 2010-2-15 20:06:53 标题: 回复 6# 的帖子

这是先手必输的情况吧？

作者: Light 时间: 2010-2-15 20:46:49

原帖由 Paracel_007 于 2010-2-15 20:06 发表这是先手必输的情况吧？

恩，对……我要的是必胜的情况……

作者: tm__xk 时间: 2010-2-15 20:52:55

L就是败局的意思....显然大家都只会考虑败局....(不会有人看绿点吧....= =||||)

作者: 忧天杞人 时间: 2010-2-15 20:53:29

第一种情况可参考;拿N堆棋子的问题>
http://wyl7830.blog.163.com/blog ... 797/edit/?mode=prev

作者: tm__xk 时间: 2010-2-15 21:02:30

再来最后一个....n=100....忘说了,刚是n=50..
L;
  [0, 1], [1, 0], [2, 2], [3, 5], [4, 7], [5, 3], [6, 10], [7, 4],
      [8, 13], [9, 15], [10, 6], [11, 18], [12, 20], [13, 8],
      [14, 23], [15, 9], [16, 26], [17, 28], [18, 11], [19, 31],
      [20, 12], [21, 34], [22, 36], [23, 14], [24, 39], [25, 41],
      [26, 16], [27, 44], [28, 17], [29, 47], [30, 49], [31, 19],
      [32, 52], [33, 54], [34, 21], [35, 57], [36, 22], [37, 60],
      [38, 62], [39, 24], [40, 65], [41, 25], [42, 68], [43, 70],
      [44, 27], [45, 73], [46, 75], [47, 29], [48, 78], [49, 30],
      [50, 81], [51, 83], [52, 32], [53, 86], [54, 33], [55, 89],
      [56, 91], [57, 35], [58, 94], [59, 96], [60, 37], [61, 99],
      [62, 38], [65, 40], [68, 42], [70, 43], [73, 45], [75, 46],
      [78, 48], [81, 50], [83, 51], [86, 53], [89, 55], [91, 56],
      [94, 58], [96, 59], [99, 61]

不玩了....
不知对各位高手有没帮助....
PS.我一眼看到了[3,5],[8,13],[21,34],[55,89]....

附件: 2.gif (2010-2-15 21:02:30, 15.78 KB) / 下载次数 33
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=ODg5NTZ8ZWZiZmYyMWN8MTc0NzE2MTA3OXwwfDA%3D

作者: tm__xk 时间: 2010-2-15 21:07:21

突然意识到那直线斜率确实是黄金数....

作者: d891320478 时间: 2010-2-15 21:17:17

这是个二进制问题，我们学编程时做过这个题，是贪心算法

作者: tm__xk 时间: 2010-2-15 22:25:33

继续不完全归纳....
除3,5,8,13,21,34,55,89外,还有:
4,7,11,18,29,47;
14,23,37,60;
17,28,45,73;
19,31,50,81等..

作者: phileas 时间: 2010-2-15 22:44:04

先行必输态：[(1+sqrt(5))n/2], [(3+sqrt(5))n/2]

作者: tm__xk 时间: 2010-2-15 23:24:41

5/3=<1,1,2>
7/4=<1,1,3>
23/14=<1,1,1,1,4>
28/17=<1,1,1,1,5>
86/53=<1,1,1,1,1,1,6>
99/61=<1,1,1,1,1,1,7>

31/19=<1,1,1,1,2,2>
44/27=<1,1,1,1,2,3>
57/35=<1,1,1,1,2,4>
70/43=<1,1,1,1,2,5>
83/51=<1,1,1,1,2,6>
96/59=<1,1,1,1,2,7>

还有
41/25=<1,1,1,1,3,2>
49/30=<1,1,1,1,2,1,2>
75/46=<1,1,1,1,2,2,2>

作者: tm__xk 时间: 2010-2-15 23:30:26 标题: 回复 15# 的帖子

哦........原来如此..
开始几项不对..

作者: tm__xk 时间: 2010-2-15 23:33:02

看来中学的东西都忘光了....原来还有Beatty定理这种东西....

作者: lulijie 时间: 2010-2-15 23:41:09

两堆的必败态：
自然数集：1，2，3，4，5，6，7，,.........................
差值集合：0，1，2，3，4，5，6..........
-------------------------------------
首先：(0,1) 差值为1
自然数集删去1，差值集合删去1
变成：
自然数集：2,3,4,5,6,7,.........................
差值集合：0，2，3，4，5，6..........
------------------------
然后从自然数集选最小的数为2，差值集合选择最小的数为0，
得到第二个必败态为(2,2)
自然数集删去2，差值集合删去0
变成：
自然数集：3，4，5，6，7，8，.......................
差值集合：2，3，4，5，6..........
--------------------------------------------------
然后从自然数集选最小的数为3，差值集合选择最小的数为2，
得到下一个必败态为(3,5)
自然数集删去3和5，差值集合删去2
变成：
自然数集：4，6，7，8.........................
差值集合：3，4，5，6..........
----------------------------------------------------
然后从自然数集选最小的数为4，差值集合选择最小的数为3，
得到下一个必败态为(4，7)
自然数集删去4和7，差值集合删去3
变成：
自然数集：6，8，9.........................
差值集合：4，5，6..........
------------------------------------------------------
然后从自然数集选最小的数为6，差值集合选择最小的数为4，
得到下一个必败态为(6，10)
自然数集删去6和10，差值集合删去4
变成：
自然数集：8，9，11，12........................
差值集合：5，6，7，8..........
-------------------------------------------------
依次类推，得出
（8，13），（9，16），（11，18）。。。。。。

[ 本帖最后由 lulijie 于 2010-2-15 23:43 编辑 ]

作者: tm__xk 时间: 2010-2-15 23:45:18

差点忘了还有N堆的情况........= =||||

作者: lulijie 时间: 2010-2-15 23:59:18

归纳一下：
二堆必败态按从小到大的顺序，记作f(n)。
那么，f(1)=(0,1)
      f(2)=(2,2)
初始集合A={3，4，5，6，7，......)
n>=3的所有的必败态f(n)，可以用以下递推公式推出：min(A)表示A集合中的最小元素。
      f(n)=( min(A)，min(A)+n-1)
      A= A 删除元素 min(A)  和  min(A)+n-1

作者: phileas 时间: 2010-2-16 08:54:50

楼上的答案有点问题：通项公式是[(1+sqrt(5))n/2], [(3+sqrt(5))n/2]，二堆先行必输态的前两个是(1,2), (3,5)

三堆没法套用二堆的做法，第一个先行必输态是(1,1,1)

作者: Paracel_007 时间: 2010-2-16 09:11:15

(1，2)是先行必胜态啊

作者: Light 时间: 2010-2-16 09:32:08 标题: 回复 13# 的帖子

能不能说的详细一点……

作者: ggglgq 时间: 2010-2-22 00:31:53

　　


提供一个与本主题相关的主题：小游戏,谁能取胜

http://bbs.mf8-china.com/viewthread.php?tid=764

　　
　　

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)