魔方吧·中文魔方俱乐部

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

---

作者: lulijie    时间: 2009-10-10 00:44:41     标题: 取数游戏

这个游戏跟隔空棋类似，只不过一种是一维的，一种是二维的。
－－－－－－－－－－－－－－－
从1到n共n个数，甲乙两人轮流取数，规则如下：
1  每人每次取1个数。取过的数不能再取。
2  每人取的数不能和前面两人取过的数相邻。
3  谁最后无数可取就算输。
－－－－－－－－－－－－－－－
问：先取方胜，还是后取方胜，有没有规律？
这个游戏相对简单些。

---

作者: noski    时间: 2009-10-10 10:30:44

首先，有个对称性取数策略：
结论A. 如果轮到某一方下子时，剩下奇数个数字，那么该方就可以通过下在正中间，然后对称下子的方法取胜。
由结论A可推出：n为奇数时，先取方必胜。

而当n为偶数时，先取方有三种策略：
策略1. 取最边上的数字，这样还剩下n-2个数字可取；
策略2. 取边上第二个数字，这样还剩下n-3个数字可取；
策略3. 取中间的某个数字，这样将数字序列分成两段，一段为奇数一段为偶数。
由结论A可知，此时先取方采用策略2则必输，因此，先取方只可选用策略1和策略3。

假设双方只采用策略1，就成了一个递归的过程，数字序列长度不断减2，最后谁拿到最后两个谁赢，因此：
n = 4k 时，先取方输；
n = 4k+2 时，先取方赢。
但是，足够聪明的双方不会只采用策略1。

而考虑策略3，先取方如何把这个数字序列截成两段，才能使自己赢呢？
继续。。

---

作者: phileas    时间: 2009-10-10 12:28:58

一维的容易很多，不过仍然不存在一个漂亮的公式。

取数会把原来连续的一段数字分成两段，相当于两个子游戏。所以仍然可以用处理nim类问题的一般方法。求得前100项为：

0,1,1,2,0,3,1,1,0,3,3,2,2,4,0,5,2,2,3,3,0,1,1,3,0,2,1,1,0,4,5,2,7,4,0,1,1,2,0,3,
1,1,0,3,3,2,2,4,4,5,5,2,3,3,0,1,1,3,0,2,1,1,0,4,5,3,7,4,8,1,1,2,0,3,1,1,0,3,3,2,
2,4,4,5,5,9,3,3,0,1,1,3,0,2,1,1,0,4,5,3,

程序如下：

import java.util.BitSet;

public class X
{
    public static void main(String[] args)
    {
        int[] nim = new int[100];
        nim[0] = 0;
        nim[1] = 1;
        nim[2] = 1;

        for (int i = 3; i < nim.length; i++)
        {
            calculate(i, nim);
        }

        for (int i = 0; i < nim.length; i++)
        {
            System.out.print(nim + ",");
        }
    }

    private static void calculate(int i, int[] nim)
    {
        BitSet handleSet = new BitSet();

        handleSet.set(nim[i-2]);
        handleSet.set(nim[i-3]);
        int n = i-3;
        for (int index = 0; index <= n/2; index++)
        {
            handleSet.set(nim[index] ^ nim[n-index]);
        }

        nim = handleSet.nextClearBit(0);
    }

}

---

作者: lulijie    时间: 2009-10-10 20:19:33

楼上，你的那100项，每项代表什么意思？
最好把结果表示成先手胜，还是先手败，便于交流。可统一用0表示先手败，1表示先手胜。
比如结果：   1，1，1，0，.......
   表示    n＝1、2、3、4 、......  ，分别为先手胜、胜、胜、败、......

---

作者: phileas    时间: 2009-10-10 20:42:11

单纯要知道先手胜还是后手胜的话：0表示先手败，非0表示先手胜。

这些数值本身的作用是用来递推的。2楼也已经说了，一次取数，可以把原来的游戏变成
1. 子游戏n-2
2. 子游戏n-3
3. 子游戏1和子游戏n-4；子游戏2和子游戏n-5。。。

所以，递归定义nim(n)如下：
1. nim(0)=0
2. 当nim(0),...,nim(k)都已经定义，定义集合G(k+1) = {nim(k-1), nim(k-2), nim(1) 异或 nim(k-3), nim(2) 异或 nim(k-4),...}
3. 定义nim(k+1) = min {x | x >= 0 且 x不属于G(k+1)}

然后这个取数游戏就变成那个经典的取石子游戏了，仍然是用两进制解决。

编程计算上述函数是容易的，但是不存在一个很漂亮的公式来描述这个函数。

有了这个函数，可以很容易解决多堆数字的情况，比如，三堆数字分别有2个，3个，5个，这种情况是先行必败，因为1异或2异或3 = 0

[ 本帖最后由 phileas 于 2009-10-10 21:17 编辑 ]

---

作者: lulijie    时间: 2009-10-10 23:08:39

我算出的n=18，是先手败。

---

作者: phileas    时间: 2009-10-10 23:43:11

18，先手拿成12,3，后手如何应对？

---

作者: lulijie    时间: 2009-10-10 23:48:07

我算出的20以内（包括多堆数字，数字的总和在20以内）必败局面如下：
1,1
------------------------
1,2
------------------------
4
2,2
1,1,1,1
------------------------
1,1,1,2
------------------------
3,3
1,1,4
1,1,2,2
1,1,1,1,1,1
------------------------
1,6
1,2,4
1,2,2,2
1,1,1,1,1,2
------------------------
8
1,7
2,6
4,4
2,2,4
1,1,3,3
2,2,2,2
1,1,1,1,4
1,1,1,1,2,2
1,1,1,1,1,1,1,1
------------------------
2,7
1,3,5
1,1,1,6
1,2,3,3
1,1,1,2,4
1,1,1,2,2,2
1,1,1,1,1,1,1,2
------------------------
5,5
1,1,8
2,3,5
3,3,4
1,1,1,7
1,1,2,6
1,1,4,4
2,2,3,3
1,1,2,2,4
1,1,1,1,3,3
1,1,2,2,2,2
1,1,1,1,1,1,4
1,1,1,1,1,1,2,2
1,1,1,1,1,1,1,1,1,1
------------------------
1,2,8
1,4,6
1,1,2,7
1,2,2,6
1,2,4,4
1,1,1,3,5
1,2,2,2,4
1,1,1,1,1,6
1,1,1,2,3,3
1,2,2,2,2,2
1,1,1,1,1,2,4
1,1,1,1,1,2,2,2
1,1,1,1,1,1,1,1,1,2
------------------------
3,9
4,8
6,6
1,4,7
2,2,8
2,4,6
4,4,4
1,1,5,5
1,2,2,7
2,2,2,6
2,2,4,4
3,3,3,3
1,1,1,1,8
1,1,2,3,5
1,1,3,3,4
2,2,2,2,4
1,1,1,1,1,7
1,1,1,1,2,6
1,1,1,1,4,4
1,1,2,2,3,3
2,2,2,2,2,2
1,1,1,1,2,2,4
1,1,1,1,1,1,3,3
1,1,1,1,2,2,2,2
1,1,1,1,1,1,1,1,4
1,1,1,1,1,1,1,1,2,2
1,1,1,1,1,1,1,1,1,1,1,1
------------------------
1,12
3,10
6,7
2,4,7
1,2,5,5
1,3,3,6
1,3,4,5
2,2,2,7
1,1,1,2,8
1,1,1,4,6
1,2,2,3,5
1,2,3,3,4
1,1,1,1,2,7
1,1,1,2,2,6
1,1,1,2,4,4
1,2,2,2,3,3
1,1,1,1,1,3,5
1,1,1,2,2,2,4
1,1,1,1,1,1,1,6
1,1,1,1,1,2,3,3
1,1,1,2,2,2,2,2
1,1,1,1,1,1,1,2,4
1,1,1,1,1,1,1,2,2,2
1,1,1,1,1,1,1,1,1,1,1,2
------------------------
14
2,12
7,7
3,3,8
3,5,6
4,5,5
1,1,3,9
1,1,4,8
1,1,6,6
1,3,3,7
2,2,5,5
2,3,3,6
2,3,4,5
3,3,4,4
1,1,1,4,7
1,1,2,2,8
1,1,2,4,6
1,1,4,4,4
2,2,2,3,5
2,2,3,3,4
1,1,1,1,5,5
1,1,1,2,2,7
1,1,2,2,2,6
1,1,2,2,4,4
1,1,3,3,3,3
2,2,2,2,3,3
1,1,1,1,1,1,8
1,1,1,1,2,3,5
1,1,1,1,3,3,4
1,1,2,2,2,2,4
1,1,1,1,1,1,1,7
1,1,1,1,1,1,2,6
1,1,1,1,1,1,4,4
1,1,1,1,2,2,3,3
1,1,2,2,2,2,2,2
1,1,1,1,1,1,2,2,4
1,1,1,1,1,1,1,1,3,3
1,1,1,1,1,1,2,2,2,2
1,1,1,1,1,1,1,1,1,1,4
1,1,1,1,1,1,1,1,1,1,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,1
------------------------
1,3,11
1,5,9
1,6,8
3,5,7
1,1,1,12
1,1,3,10
1,1,6,7
1,2,3,9
1,2,4,8
1,2,6,6
1,4,4,6
2,3,3,7
1,1,2,4,7
1,2,2,2,8
1,2,2,4,6
1,2,4,4,4
1,3,3,3,5
1,1,1,2,5,5
1,1,1,3,3,6
1,1,1,3,4,5
1,1,2,2,2,7
1,2,2,2,2,6
1,2,2,2,4,4
1,2,3,3,3,3
1,1,1,1,1,2,8
1,1,1,1,1,4,6
1,1,1,2,2,3,5
1,1,1,2,3,3,4
1,2,2,2,2,2,4
1,1,1,1,1,1,2,7
1,1,1,1,1,2,2,6
1,1,1,1,1,2,4,4
1,1,1,2,2,2,3,3
1,2,2,2,2,2,2,2
1,1,1,1,1,1,1,3,5
1,1,1,1,1,2,2,2,4
1,1,1,1,1,1,1,1,1,6
1,1,1,1,1,1,1,2,3,3
1,1,1,1,1,2,2,2,2,2
1,1,1,1,1,1,1,1,1,2,4
1,1,1,1,1,1,1,1,1,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,2
------------------------
5,11
8,8
1,1,14
1,4,11
1,7,8
2,3,11
2,5,9
2,6,8
3,4,9
4,4,8
4,6,6
1,1,2,12
1,1,7,7
1,2,3,10
1,2,6,7
1,4,4,7
2,2,3,9
2,2,4,8
2,2,6,6
2,4,4,6
3,3,5,5
4,4,4,4
1,1,3,3,8
1,1,3,5,6
1,1,4,5,5
1,2,2,4,7
2,2,2,2,8
2,2,2,4,6
2,2,4,4,4
2,3,3,3,5
3,3,3,3,4
1,1,1,1,3,9
1,1,1,1,4,8
1,1,1,1,6,6
1,1,1,3,3,7
1,1,2,2,5,5
1,1,2,3,3,6
1,1,2,3,4,5
1,1,3,3,4,4
1,2,2,2,2,7
2,2,2,2,2,6
2,2,2,2,4,4
2,2,3,3,3,3
1,1,1,1,1,4,7
1,1,1,1,2,2,8
1,1,1,1,2,4,6
1,1,1,1,4,4,4
1,1,2,2,2,3,5
1,1,2,2,3,3,4
2,2,2,2,2,2,4
1,1,1,1,1,1,5,5
1,1,1,1,1,2,2,7
1,1,1,1,2,2,2,6
1,1,1,1,2,2,4,4
1,1,1,1,3,3,3,3
1,1,2,2,2,2,3,3
2,2,2,2,2,2,2,2
1,1,1,1,1,1,1,1,8
1,1,1,1,1,1,2,3,5
1,1,1,1,1,1,3,3,4
1,1,1,1,2,2,2,2,4
1,1,1,1,1,1,1,1,1,7
1,1,1,1,1,1,1,1,2,6
1,1,1,1,1,1,1,1,4,4
1,1,1,1,1,1,2,2,3,3
1,1,1,1,2,2,2,2,2,2
1,1,1,1,1,1,1,1,2,2,4
1,1,1,1,1,1,1,1,1,1,3,3
1,1,1,1,1,1,1,1,2,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,4
1,1,1,1,1,1,1,1,1,1,1,1,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
------------------------
1,16
1,2,14
1,4,12
2,4,11
2,7,8
3,4,10
4,6,7
1,2,2,12
1,2,7,7
1,3,5,8
1,5,5,6
2,2,3,10
2,2,6,7
2,4,4,7
1,1,1,3,11
1,1,1,5,9
1,1,1,6,8
1,1,3,5,7
1,2,3,3,8
1,2,3,5,6
1,2,4,5,5
1,3,3,4,6
1,3,4,4,5
2,2,2,4,7
1,1,1,1,1,12
1,1,1,1,3,10
1,1,1,1,6,7
1,1,1,2,3,9
1,1,1,2,4,8
1,1,1,2,6,6
1,1,1,4,4,6
1,1,2,3,3,7
1,2,2,2,5,5
1,2,2,3,3,6
1,2,2,3,4,5
1,2,3,3,4,4
2,2,2,2,2,7
1,1,1,1,2,4,7
1,1,1,2,2,2,8
1,1,1,2,2,4,6
1,1,1,2,4,4,4
1,1,1,3,3,3,5
1,2,2,2,2,3,5
1,2,2,2,3,3,4
1,1,1,1,1,2,5,5
1,1,1,1,1,3,3,6
1,1,1,1,1,3,4,5
1,1,1,1,2,2,2,7
1,1,1,2,2,2,2,6
1,1,1,2,2,2,4,4
1,1,1,2,3,3,3,3
1,2,2,2,2,2,3,3
1,1,1,1,1,1,1,2,8
1,1,1,1,1,1,1,4,6
1,1,1,1,1,2,2,3,5
1,1,1,1,1,2,3,3,4
1,1,1,2,2,2,2,2,4
1,1,1,1,1,1,1,1,2,7
1,1,1,1,1,1,1,2,2,6
1,1,1,1,1,1,1,2,4,4
1,1,1,1,1,2,2,2,3,3
1,1,1,2,2,2,2,2,2,2
1,1,1,1,1,1,1,1,1,3,5
1,1,1,1,1,1,1,2,2,2,4
1,1,1,1,1,1,1,1,1,1,1,6
1,1,1,1,1,1,1,1,1,2,3,3
1,1,1,1,1,1,1,2,2,2,2,2
1,1,1,1,1,1,1,1,1,1,1,2,4
1,1,1,1,1,1,1,1,1,1,1,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2
------------------------
18
2,16
4,14
6,12
2,2,14
2,4,12
3,3,12
4,7,7
5,5,8
1,1,5,11
1,1,8,8
1,5,5,7
2,2,2,12
2,2,7,7
2,3,5,8
2,5,5,6
3,3,3,9
3,3,4,8
3,3,6,6
3,4,5,6
4,4,5,5
1,1,1,1,14
1,1,1,4,11
1,1,1,7,8
1,1,2,3,11
1,1,2,5,9
1,1,2,6,8
1,1,3,4,9
1,1,4,4,8
1,1,4,6,6
1,2,3,5,7
1,3,3,4,7
2,2,3,3,8
2,2,3,5,6
2,2,4,5,5
2,3,3,4,6
2,3,4,4,5
3,3,4,4,4
1,1,1,1,2,12
1,1,1,1,7,7
1,1,1,2,3,10
1,1,1,2,6,7
1,1,1,4,4,7
1,1,2,2,3,9
1,1,2,2,4,8
1,1,2,2,6,6
1,1,2,4,4,6
1,1,3,3,5,5
1,1,4,4,4,4
1,2,2,3,3,7
2,2,2,2,5,5
2,2,2,3,3,6
2,2,2,3,4,5
2,2,3,3,4,4
3,3,3,3,3,3
1,1,1,1,3,3,8
1,1,1,1,3,5,6
1,1,1,1,4,5,5
1,1,1,2,2,4,7
1,1,2,2,2,2,8
1,1,2,2,2,4,6
1,1,2,2,4,4,4
1,1,2,3,3,3,5
1,1,3,3,3,3,4
2,2,2,2,2,3,5
2,2,2,2,3,3,4
1,1,1,1,1,1,3,9
1,1,1,1,1,1,4,8
1,1,1,1,1,1,6,6
1,1,1,1,1,3,3,7
1,1,1,1,2,2,5,5
1,1,1,1,2,3,3,6
1,1,1,1,2,3,4,5
1,1,1,1,3,3,4,4
1,1,1,2,2,2,2,7
1,1,2,2,2,2,2,6
1,1,2,2,2,2,4,4
1,1,2,2,3,3,3,3
2,2,2,2,2,2,3,3
1,1,1,1,1,1,1,4,7
1,1,1,1,1,1,2,2,8
1,1,1,1,1,1,2,4,6
1,1,1,1,1,1,4,4,4
1,1,1,1,2,2,2,3,5
1,1,1,1,2,2,3,3,4
1,1,2,2,2,2,2,2,4
1,1,1,1,1,1,1,1,5,5
1,1,1,1,1,1,1,2,2,7
1,1,1,1,1,1,2,2,2,6
1,1,1,1,1,1,2,2,4,4
1,1,1,1,1,1,3,3,3,3
1,1,1,1,2,2,2,2,3,3
1,1,2,2,2,2,2,2,2,2
1,1,1,1,1,1,1,1,1,1,8
1,1,1,1,1,1,1,1,2,3,5
1,1,1,1,1,1,1,1,3,3,4
1,1,1,1,1,1,2,2,2,2,4
1,1,1,1,1,1,1,1,1,1,1,7
1,1,1,1,1,1,1,1,1,1,2,6
1,1,1,1,1,1,1,1,1,1,4,4
1,1,1,1,1,1,1,1,2,2,3,3
1,1,1,1,1,1,2,2,2,2,2,2
1,1,1,1,1,1,1,1,1,1,2,2,4
1,1,1,1,1,1,1,1,1,1,1,1,3,3
1,1,1,1,1,1,1,1,1,1,2,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,1,4
1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1

---

作者: lulijie    时间: 2009-10-10 23:49:59

7,12
1,3,15
1,5,13
1,9,9
1,1,1,16
1,2,5,11
1,2,8,8
1,3,6,9
1,4,5,9
1,4,6,8
1,6,6,6
2,5,5,7
3,3,3,10
3,3,6,7
3,4,5,7
1,1,1,2,14
1,1,1,4,12
1,1,2,4,11
1,1,2,7,8
1,1,3,4,10
1,1,4,6,7
1,2,2,3,11
1,2,2,5,9
1,2,2,6,8
1,2,3,4,9
1,2,4,4,8
1,2,4,6,6
1,3,5,5,5
1,4,4,4,6
2,2,3,5,7
2,3,3,4,7
1,1,1,2,2,12
1,1,1,2,7,7
1,1,1,3,5,8
1,1,1,5,5,6
1,1,2,2,3,10
1,1,2,2,6,7
1,1,2,4,4,7
1,2,2,2,3,9
1,2,2,2,4,8
1,2,2,2,6,6
1,2,2,4,4,6
1,2,3,3,5,5
1,2,4,4,4,4
1,3,3,3,3,6
1,3,3,3,4,5
2,2,2,3,3,7
1,1,1,1,1,3,11
1,1,1,1,1,5,9
1,1,1,1,1,6,8
1,1,1,1,3,5,7
1,1,1,2,3,3,8
1,1,1,2,3,5,6
1,1,1,2,4,5,5
1,1,1,3,3,4,6
1,1,1,3,4,4,5
1,1,2,2,2,4,7
1,2,2,2,2,2,8
1,2,2,2,2,4,6
1,2,2,2,4,4,4
1,2,2,3,3,3,5
1,2,3,3,3,3,4
1,1,1,1,1,1,1,12
1,1,1,1,1,1,3,10
1,1,1,1,1,1,6,7
1,1,1,1,1,2,3,9
1,1,1,1,1,2,4,8
1,1,1,1,1,2,6,6
1,1,1,1,1,4,4,6
1,1,1,1,2,3,3,7
1,1,1,2,2,2,5,5
1,1,1,2,2,3,3,6
1,1,1,2,2,3,4,5
1,1,1,2,3,3,4,4
1,1,2,2,2,2,2,7
1,2,2,2,2,2,2,6
1,2,2,2,2,2,4,4
1,2,2,2,3,3,3,3
1,1,1,1,1,1,2,4,7
1,1,1,1,1,2,2,2,8
1,1,1,1,1,2,2,4,6
1,1,1,1,1,2,4,4,4
1,1,1,1,1,3,3,3,5
1,1,1,2,2,2,2,3,5
1,1,1,2,2,2,3,3,4
1,2,2,2,2,2,2,2,4
1,1,1,1,1,1,1,2,5,5
1,1,1,1,1,1,1,3,3,6
1,1,1,1,1,1,1,3,4,5
1,1,1,1,1,1,2,2,2,7
1,1,1,1,1,2,2,2,2,6
1,1,1,1,1,2,2,2,4,4
1,1,1,1,1,2,3,3,3,3
1,1,1,2,2,2,2,2,3,3
1,2,2,2,2,2,2,2,2,2
1,1,1,1,1,1,1,1,1,2,8
1,1,1,1,1,1,1,1,1,4,6
1,1,1,1,1,1,1,2,2,3,5
1,1,1,1,1,1,1,2,3,3,4
1,1,1,1,1,2,2,2,2,2,4
1,1,1,1,1,1,1,1,1,1,2,7
1,1,1,1,1,1,1,1,1,2,2,6
1,1,1,1,1,1,1,1,1,2,4,4
1,1,1,1,1,1,1,2,2,2,3,3
1,1,1,1,1,2,2,2,2,2,2,2
1,1,1,1,1,1,1,1,1,1,1,3,5
1,1,1,1,1,1,1,1,1,2,2,2,4
1,1,1,1,1,1,1,1,1,1,1,1,1,6
1,1,1,1,1,1,1,1,1,1,1,2,3,3
1,1,1,1,1,1,1,1,1,2,2,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,2,4
1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2
------------------------
5,15
1,1,18
1,9,10
2,3,15
2,5,13
2,9,9
3,6,11
3,8,9
4,8,8
6,6,8
1,1,2,16
1,1,4,14
1,1,6,12
1,3,6,10
1,3,7,9
1,4,4,11
1,4,7,8
1,6,6,7
2,2,5,11
2,2,8,8
2,3,6,9
2,4,5,9
2,4,6,8
2,6,6,6
3,3,7,7
3,4,4,9
4,4,4,8
4,4,6,6
5,5,5,5
1,1,2,2,14
1,1,2,4,12
1,1,3,3,12
1,1,4,7,7
1,1,5,5,8
1,2,2,4,11
1,2,2,7,8
1,2,3,4,10
1,2,4,6,7
1,4,4,4,7
2,2,2,3,11
2,2,2,5,9
2,2,2,6,8
2,2,3,4,9
2,2,4,4,8
2,2,4,6,6
2,3,5,5,5
2,4,4,4,6
3,3,3,3,8
3,3,3,5,6
3,3,4,5,5
4,4,4,4,4
1,1,1,1,5,11
1,1,1,1,8,8
1,1,1,5,5,7
1,1,2,2,2,12
1,1,2,2,7,7
1,1,2,3,5,8
1,1,2,5,5,6
1,1,3,3,3,9
1,1,3,3,4,8
1,1,3,3,6,6
1,1,3,4,5,6
1,1,4,4,5,5
1,2,2,2,3,10
1,2,2,2,6,7
1,2,2,4,4,7
1,3,3,3,3,7
2,2,2,2,3,9
2,2,2,2,4,8
2,2,2,2,6,6
2,2,2,4,4,6
2,2,3,3,5,5
2,2,4,4,4,4
2,3,3,3,3,6
2,3,3,3,4,5
3,3,3,3,4,4
1,1,1,1,1,1,14
1,1,1,1,1,4,11
1,1,1,1,1,7,8
1,1,1,1,2,3,11
1,1,1,1,2,5,9
1,1,1,1,2,6,8
1,1,1,1,3,4,9
1,1,1,1,4,4,8
1,1,1,1,4,6,6
1,1,1,2,3,5,7
1,1,1,3,3,4,7
1,1,2,2,3,3,8
1,1,2,2,3,5,6
1,1,2,2,4,5,5
1,1,2,3,3,4,6
1,1,2,3,4,4,5
1,1,3,3,4,4,4
1,2,2,2,2,4,7
2,2,2,2,2,2,8
2,2,2,2,2,4,6
2,2,2,2,4,4,4
2,2,2,3,3,3,5
2,2,3,3,3,3,4
1,1,1,1,1,1,2,12
1,1,1,1,1,1,7,7
1,1,1,1,1,2,3,10
1,1,1,1,1,2,6,7
1,1,1,1,1,4,4,7
1,1,1,1,2,2,3,9
1,1,1,1,2,2,4,8
1,1,1,1,2,2,6,6
1,1,1,1,2,4,4,6
1,1,1,1,3,3,5,5
1,1,1,1,4,4,4,4
1,1,1,2,2,3,3,7
1,1,2,2,2,2,5,5
1,1,2,2,2,3,3,6
1,1,2,2,2,3,4,5
1,1,2,2,3,3,4,4
1,1,3,3,3,3,3,3
1,2,2,2,2,2,2,7
2,2,2,2,2,2,2,6
2,2,2,2,2,2,4,4
2,2,2,2,3,3,3,3
1,1,1,1,1,1,3,3,8
1,1,1,1,1,1,3,5,6
1,1,1,1,1,1,4,5,5
1,1,1,1,1,2,2,4,7
1,1,1,1,2,2,2,2,8
1,1,1,1,2,2,2,4,6
1,1,1,1,2,2,4,4,4
1,1,1,1,2,3,3,3,5
1,1,1,1,3,3,3,3,4
1,1,2,2,2,2,2,3,5
1,1,2,2,2,2,3,3,4
2,2,2,2,2,2,2,2,4
1,1,1,1,1,1,1,1,3,9
1,1,1,1,1,1,1,1,4,8
1,1,1,1,1,1,1,1,6,6
1,1,1,1,1,1,1,3,3,7
1,1,1,1,1,1,2,2,5,5
1,1,1,1,1,1,2,3,3,6
1,1,1,1,1,1,2,3,4,5
1,1,1,1,1,1,3,3,4,4
1,1,1,1,1,2,2,2,2,7
1,1,1,1,2,2,2,2,2,6
1,1,1,1,2,2,2,2,4,4
1,1,1,1,2,2,3,3,3,3
1,1,2,2,2,2,2,2,3,3
2,2,2,2,2,2,2,2,2,2
1,1,1,1,1,1,1,1,1,4,7
1,1,1,1,1,1,1,1,2,2,8
1,1,1,1,1,1,1,1,2,4,6
1,1,1,1,1,1,1,1,4,4,4
1,1,1,1,1,1,2,2,2,3,5
1,1,1,1,1,1,2,2,3,3,4
1,1,1,1,2,2,2,2,2,2,4
1,1,1,1,1,1,1,1,1,1,5,5
1,1,1,1,1,1,1,1,1,2,2,7
1,1,1,1,1,1,1,1,2,2,2,6
1,1,1,1,1,1,1,1,2,2,4,4
1,1,1,1,1,1,1,1,3,3,3,3
1,1,1,1,1,1,2,2,2,2,3,3
1,1,1,1,2,2,2,2,2,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,8
1,1,1,1,1,1,1,1,1,1,2,3,5
1,1,1,1,1,1,1,1,1,1,3,3,4
1,1,1,1,1,1,1,1,2,2,2,2,4
1,1,1,1,1,1,1,1,1,1,1,1,1,7
1,1,1,1,1,1,1,1,1,1,1,1,2,6
1,1,1,1,1,1,1,1,1,1,1,1,4,4
1,1,1,1,1,1,1,1,1,1,2,2,3,3
1,1,1,1,1,1,1,1,2,2,2,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,2,2,4
1,1,1,1,1,1,1,1,1,1,1,1,1,1,3,3
1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,4
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1

---

作者: lulijie    时间: 2009-10-10 23:52:21

回7楼：
   后手应成  3 ,10

---

作者: noski    时间: 2009-10-11 00:03:42

我想，对于先手将数字序列分成两段这种情况，还需要进一步进行抽象。
先手记为A，后手记为B，下面将站在A的角度看如何取胜：

定义：
先手制胜权  X(n) 操作序列形如[ABABA]，对于连续的n个数，如果先手A能确保必胜，则称该n具有先手制胜权。
先手保留权  Y(n) 操作序列形如[BABAB]，对于连续的n个数，如果让B先下时，A能有策略确保最后一子仍被B取得，那么称该n具有先手保留权。

比如：
先手制胜权：
对于所有的奇数，X(n)=1；
对于偶数，
X(2)=1
X(4)=0
X(6)=1
X(8)=0
……
这个X(n)就是lulijie要找的答案。

先手保留权：
Y(1)=1
Y(2)=1
Y(3)=0
Y(4)=1
Y(5)=0
Y(6)=1
Y(7)=1
Y(8)=1
……
比如n=1或6，先手方既有先手制胜权，又有先手保留权。那么就可以推出n=10的情况，让先手方取的数把序列分隔成长度为1和6的两段，于是先手方必胜，X(10)=1。

对于任一个n的情况，先手方A下在中间，把n分隔成i和j两个序列，如果存在i和j，使得X(i)、Y(i)、X(j)、Y(j)同时为1，那么X(n)=1。
好像可以递推，大家可以验证一下。。

---

作者: lulijie    时间: 2009-10-11 00:44:51

noski的方法：
可以以小的先手制胜权+先手保留权 →  大的先手制胜权。
那么先手保留权又要预先计算，也要有一个先手保留权 的递推公式，否则递推无法进行下去。

---

作者: lulijie    时间: 2009-10-11 01:08:32

某种局面 A，先手方取：            A可以是若干堆数字(不限1堆)，它所有堆数字的和为Sa
         若某种取法后形成的局面(B)是必败局面，那么A局面就是必胜局面，记作f(A)=1,
         若他无论何种取法都无法形成必败局面，那么A局面就是必败局面，记作f(A)=0。
-------------------------------------------------------------------------------------------------------------------
        由于A取后形成的局面的所有堆数字的和必然比Sa小，所以可以有递推公式：
         f(0)=0
        Sa从1逐渐增大，推导出所有必败局面。
-----------------------------------------------------------------
        Sa=1
             f(1) ,取后可以形成f(0)，所以是必胜局面
        Sa=2
             f(2), 取后可以形成f(0)，所以是必胜局面
             f(1,1),无论何种取法都无法形成必败局面,所以f(1,1)=0
        Sa=3
             f(3),取后可以形成f(0)，所以是必胜局面
             f(1,2),无论何种取法都无法形成必败局面,所以f(1,2)=0
             f(1,1,1),取后可以形成f(1,1)，所以是必胜局面
       Sa=4
             f(4),无论何种取法都无法形成必败局面,所以f(4)=0
             f(1,3),取后可以形成f(1,1)，所以是必胜局面
             f(2,2),无论何种取法都无法形成必败局面,所以f(2,2)=0
             f(1,1,2),取后可以形成f(1,1)，所以是必胜局面
             f(1,1,1,1),无论何种取法都无法形成必败局面,所以f(1,1,1,1)=0
         ..........

---

作者: phileas    时间: 2009-10-11 09:43:33

原帖由 lulijie 于 2009-10-10 23:52 发表
回7楼：
   后手应成  3 ,10

回10楼：先手应2,3,5。

---

作者: phileas    时间: 2009-10-11 10:01:12

通过状态转换来计算当然是可以的，但是这样计算量比较大，实际上就是穷举。

对于一般的两人博弈游戏，每步只有有限多种选择，有限步后必然结束，结束后必然能判定输赢（即不存在和棋）。那么根据博弈论的基本定理，任一个初始状态，必然有一个人存在必胜策略。

如果加上限制条件：对于任何状态，两人可供选择的下法是相同的；那么所有这样的游戏都可以等价于一个经典的nim取石子游戏。本游戏正是如此。

这个定理的价值在于，母游戏的nim值等于所有子游戏的nim值的异或。这样，虽然仍然需要编程计算，但计算量比较小。

对于二维的隔空棋，也是可以运用这个定理的。但是由于二维情况下无法很容易的把母游戏转化成多个子游戏，所以即使使用该定理，计算量仍然很大，作用不明显。

---

作者: phileas    时间: 2009-10-11 10:10:36

我把前20项的nim值重新贴一下，有兴趣的朋友可以用8楼的列表验证一下，是否先手必败的充要条件是nim值的异或=0。

nim(1)=1,nim(2)=1,nim(3)=2,nim(4)=0,nim(5)=3,
nim(6)=1,nim(7)=1,nim(8)=0,nim)9)=3,nim(10)=3,
nim(11)=2,nim(12)=2,nim(13)=4,nim(14)=0,nim(15)=5,
nim(16)=2,nim(17)=2,nim(18)=3,nim(19)=3,nim(20)=0,
==============================================
随便验证两个：
2,7：nim(2)异或nim(7) = 1异或1 = 0
1,3,5：nim(1)异或nim(3)异或nim(7) = 1异或2异或3 = 0

---

作者: lulijie    时间: 2009-10-11 12:52:10

3,10    和   2,3,5   可以一步转化，不可能都是必败局面，看来我的程序还是有问题

---

作者: lulijie    时间: 2009-10-11 13:20:08

找到错误所在，Sa>=12 的结果修正如下：
4,8
6,6
1,4,7
2,2,8
2,4,6
4,4,4
1,1,5,5
1,2,2,7
2,2,2,6
2,2,4,4
3,3,3,3
1,1,1,1,8
1,1,2,3,5
1,1,3,3,4
2,2,2,2,4
1,1,1,1,1,7
1,1,1,1,2,6
1,1,1,1,4,4
1,1,2,2,3,3
2,2,2,2,2,2
1,1,1,1,2,2,4
1,1,1,1,1,1,3,3
1,1,1,1,2,2,2,2
1,1,1,1,1,1,1,1,4
1,1,1,1,1,1,1,1,2,2
1,1,1,1,1,1,1,1,1,1,1,1
------------------------
6,7
1,3,9
2,4,7
1,2,5,5
1,3,3,6
1,3,4,5
2,2,2,7
1,1,1,2,8
1,1,1,4,6
1,2,2,3,5
1,2,3,3,4
1,1,1,1,2,7
1,1,1,2,2,6
1,1,1,2,4,4
1,2,2,2,3,3
1,1,1,1,1,3,5
1,1,1,2,2,2,4
1,1,1,1,1,1,1,6
1,1,1,1,1,2,3,3
1,1,1,2,2,2,2,2
1,1,1,1,1,1,1,2,4
1,1,1,1,1,1,1,2,2,2
1,1,1,1,1,1,1,1,1,1,1,2
------------------------
14
3,11
5,9
7,7
1,3,10
2,3,9
3,3,8
3,5,6
4,5,5
1,1,4,8
1,1,6,6
1,3,3,7
2,2,5,5
2,3,3,6
2,3,4,5
3,3,4,4
1,1,1,4,7
1,1,2,2,8
1,1,2,4,6
1,1,4,4,4
2,2,2,3,5
2,2,3,3,4
1,1,1,1,5,5
1,1,1,2,2,7
1,1,2,2,2,6
1,1,2,2,4,4
1,1,3,3,3,3
2,2,2,2,3,3
1,1,1,1,1,1,8
1,1,1,1,2,3,5
1,1,1,1,3,3,4
1,1,2,2,2,2,4
1,1,1,1,1,1,1,7
1,1,1,1,1,1,2,6
1,1,1,1,1,1,4,4
1,1,1,1,2,2,3,3
1,1,2,2,2,2,2,2
1,1,1,1,1,1,2,2,4
1,1,1,1,1,1,1,1,3,3
1,1,1,1,1,1,2,2,2,2
1,1,1,1,1,1,1,1,1,1,4
1,1,1,1,1,1,1,1,1,1,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,1
------------------------
3,12
5,10
1,6,8
2,3,10
3,5,7
1,1,6,7
1,2,4,8
1,2,6,6
1,4,4,6
2,3,3,7
1,1,1,3,9
1,1,2,4,7
1,2,2,2,8
1,2,2,4,6
1,2,4,4,4
1,3,3,3,5
1,1,1,2,5,5
1,1,1,3,3,6
1,1,1,3,4,5
1,1,2,2,2,7
1,2,2,2,2,6
1,2,2,2,4,4
1,2,3,3,3,3
1,1,1,1,1,2,8
1,1,1,1,1,4,6
1,1,1,2,2,3,5
1,1,1,2,3,3,4
1,2,2,2,2,2,4
1,1,1,1,1,1,2,7
1,1,1,1,1,2,2,6
1,1,1,1,1,2,4,4
1,1,1,2,2,2,3,3
1,2,2,2,2,2,2,2
1,1,1,1,1,1,1,3,5
1,1,1,1,1,2,2,2,4
1,1,1,1,1,1,1,1,1,6
1,1,1,1,1,1,1,2,3,3
1,1,1,1,1,2,2,2,2,2
1,1,1,1,1,1,1,1,1,2,4
1,1,1,1,1,1,1,1,1,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,2
------------------------
8,8
1,1,14
1,7,8
2,6,8
4,4,8
4,6,6
1,1,3,11
1,1,5,9
1,1,7,7
1,2,6,7
1,4,4,7
2,2,4,8
2,2,6,6
2,4,4,6
3,3,5,5
4,4,4,4
1,1,1,3,10
1,1,2,3,9
1,1,3,3,8
1,1,3,5,6
1,1,4,5,5
1,2,2,4,7
2,2,2,2,8
2,2,2,4,6
2,2,4,4,4
2,3,3,3,5
3,3,3,3,4
1,1,1,1,4,8
1,1,1,1,6,6
1,1,1,3,3,7
1,1,2,2,5,5
1,1,2,3,3,6
1,1,2,3,4,5
1,1,3,3,4,4
1,2,2,2,2,7
2,2,2,2,2,6
2,2,2,2,4,4
2,2,3,3,3,3
1,1,1,1,1,4,7
1,1,1,1,2,2,8
1,1,1,1,2,4,6
1,1,1,1,4,4,4
1,1,2,2,2,3,5
1,1,2,2,3,3,4
2,2,2,2,2,2,4
1,1,1,1,1,1,5,5
1,1,1,1,1,2,2,7
1,1,1,1,2,2,2,6
1,1,1,1,2,2,4,4
1,1,1,1,3,3,3,3
1,1,2,2,2,2,3,3
2,2,2,2,2,2,2,2
1,1,1,1,1,1,1,1,8
1,1,1,1,1,1,2,3,5
1,1,1,1,1,1,3,3,4
1,1,1,1,2,2,2,2,4
1,1,1,1,1,1,1,1,1,7
1,1,1,1,1,1,1,1,2,6
1,1,1,1,1,1,1,1,4,4
1,1,1,1,1,1,2,2,3,3
1,1,1,1,2,2,2,2,2,2
1,1,1,1,1,1,1,1,2,2,4
1,1,1,1,1,1,1,1,1,1,3,3
1,1,1,1,1,1,1,1,2,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,4
1,1,1,1,1,1,1,1,1,1,1,1,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
------------------------
1,2,14
1,5,11
2,7,8
4,6,7
1,1,3,12
1,1,5,10
1,2,3,11
1,2,5,9
1,2,7,7
1,3,4,9
1,3,5,8
1,5,5,6
2,2,6,7
2,4,4,7
1,1,1,6,8
1,1,2,3,10
1,1,3,5,7
1,2,2,3,9
1,2,3,3,8
1,2,3,5,6
1,2,4,5,5
1,3,3,4,6
1,3,4,4,5
2,2,2,4,7
1,1,1,1,6,7
1,1,1,2,4,8
1,1,1,2,6,6
1,1,1,4,4,6
1,1,2,3,3,7
1,2,2,2,5,5
1,2,2,3,3,6
1,2,2,3,4,5
1,2,3,3,4,4
2,2,2,2,2,7
1,1,1,1,1,3,9
1,1,1,1,2,4,7
1,1,1,2,2,2,8
1,1,1,2,2,4,6
1,1,1,2,4,4,4
1,1,1,3,3,3,5
1,2,2,2,2,3,5
1,2,2,2,3,3,4
1,1,1,1,1,2,5,5
1,1,1,1,1,3,3,6
1,1,1,1,1,3,4,5
1,1,1,1,2,2,2,7
1,1,1,2,2,2,2,6
1,1,1,2,2,2,4,4
1,1,1,2,3,3,3,3
1,2,2,2,2,2,3,3
1,1,1,1,1,1,1,2,8
1,1,1,1,1,1,1,4,6
1,1,1,1,1,2,2,3,5
1,1,1,1,1,2,3,3,4
1,1,1,2,2,2,2,2,4
1,1,1,1,1,1,1,1,2,7
1,1,1,1,1,1,1,2,2,6
1,1,1,1,1,1,1,2,4,4
1,1,1,1,1,2,2,2,3,3
1,1,1,2,2,2,2,2,2,2
1,1,1,1,1,1,1,1,1,3,5
1,1,1,1,1,1,1,2,2,2,4
1,1,1,1,1,1,1,1,1,1,1,6
1,1,1,1,1,1,1,1,1,2,3,3
1,1,1,1,1,1,1,2,2,2,2,2
1,1,1,1,1,1,1,1,1,1,1,2,4
1,1,1,1,1,1,1,1,1,1,1,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2
------------------------
4,8
6,6
1,4,7
2,2,8
2,4,6
4,4,4
1,1,5,5
1,2,2,7
2,2,2,6
2,2,4,4
3,3,3,3
1,1,1,1,8
1,1,2,3,5
1,1,3,3,4
2,2,2,2,4
1,1,1,1,1,7
1,1,1,1,2,6
1,1,1,1,4,4
1,1,2,2,3,3
2,2,2,2,2,2
1,1,1,1,2,2,4
1,1,1,1,1,1,3,3
1,1,1,1,2,2,2,2
1,1,1,1,1,1,1,1,4
1,1,1,1,1,1,1,1,2,2
1,1,1,1,1,1,1,1,1,1,1,1
------------------------
6,7
1,3,9
2,4,7
1,2,5,5
1,3,3,6
1,3,4,5
2,2,2,7
1,1,1,2,8
1,1,1,4,6
1,2,2,3,5
1,2,3,3,4
1,1,1,1,2,7
1,1,1,2,2,6
1,1,1,2,4,4
1,2,2,2,3,3
1,1,1,1,1,3,5
1,1,1,2,2,2,4
1,1,1,1,1,1,1,6
1,1,1,1,1,2,3,3
1,1,1,2,2,2,2,2
1,1,1,1,1,1,1,2,4
1,1,1,1,1,1,1,2,2,2
1,1,1,1,1,1,1,1,1,1,1,2
------------------------
14
3,11
5,9
7,7
1,3,10
2,3,9
3,3,8
3,5,6
4,5,5
1,1,4,8
1,1,6,6
1,3,3,7
2,2,5,5
2,3,3,6
2,3,4,5
3,3,4,4
1,1,1,4,7
1,1,2,2,8
1,1,2,4,6
1,1,4,4,4
2,2,2,3,5
2,2,3,3,4
1,1,1,1,5,5
1,1,1,2,2,7
1,1,2,2,2,6
1,1,2,2,4,4
1,1,3,3,3,3
2,2,2,2,3,3
1,1,1,1,1,1,8
1,1,1,1,2,3,5
1,1,1,1,3,3,4
1,1,2,2,2,2,4
1,1,1,1,1,1,1,7
1,1,1,1,1,1,2,6
1,1,1,1,1,1,4,4
1,1,1,1,2,2,3,3
1,1,2,2,2,2,2,2
1,1,1,1,1,1,2,2,4
1,1,1,1,1,1,1,1,3,3
1,1,1,1,1,1,2,2,2,2
1,1,1,1,1,1,1,1,1,1,4
1,1,1,1,1,1,1,1,1,1,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,1
------------------------
3,12
5,10
1,6,8
2,3,10
3,5,7
1,1,6,7
1,2,4,8
1,2,6,6
1,4,4,6
2,3,3,7
1,1,1,3,9
1,1,2,4,7
1,2,2,2,8
1,2,2,4,6
1,2,4,4,4
1,3,3,3,5
1,1,1,2,5,5
1,1,1,3,3,6
1,1,1,3,4,5
1,1,2,2,2,7
1,2,2,2,2,6
1,2,2,2,4,4
1,2,3,3,3,3
1,1,1,1,1,2,8
1,1,1,1,1,4,6
1,1,1,2,2,3,5
1,1,1,2,3,3,4
1,2,2,2,2,2,4
1,1,1,1,1,1,2,7
1,1,1,1,1,2,2,6
1,1,1,1,1,2,4,4
1,1,1,2,2,2,3,3
1,2,2,2,2,2,2,2
1,1,1,1,1,1,1,3,5
1,1,1,1,1,2,2,2,4
1,1,1,1,1,1,1,1,1,6
1,1,1,1,1,1,1,2,3,3
1,1,1,1,1,2,2,2,2,2
1,1,1,1,1,1,1,1,1,2,4
1,1,1,1,1,1,1,1,1,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,2
------------------------
8,8
1,1,14
1,7,8
2,6,8
4,4,8
4,6,6
1,1,3,11
1,1,5,9
1,1,7,7
1,2,6,7
1,4,4,7
2,2,4,8
2,2,6,6
2,4,4,6
3,3,5,5
4,4,4,4
1,1,1,3,10
1,1,2,3,9
1,1,3,3,8
1,1,3,5,6
1,1,4,5,5
1,2,2,4,7
2,2,2,2,8
2,2,2,4,6
2,2,4,4,4
2,3,3,3,5
3,3,3,3,4
1,1,1,1,4,8
1,1,1,1,6,6
1,1,1,3,3,7
1,1,2,2,5,5
1,1,2,3,3,6
1,1,2,3,4,5
1,1,3,3,4,4
1,2,2,2,2,7
2,2,2,2,2,6
2,2,2,2,4,4
2,2,3,3,3,3
1,1,1,1,1,4,7
1,1,1,1,2,2,8
1,1,1,1,2,4,6
1,1,1,1,4,4,4
1,1,2,2,2,3,5
1,1,2,2,3,3,4
2,2,2,2,2,2,4
1,1,1,1,1,1,5,5
1,1,1,1,1,2,2,7
1,1,1,1,2,2,2,6
1,1,1,1,2,2,4,4
1,1,1,1,3,3,3,3
1,1,2,2,2,2,3,3
2,2,2,2,2,2,2,2
1,1,1,1,1,1,1,1,8
1,1,1,1,1,1,2,3,5
1,1,1,1,1,1,3,3,4
1,1,1,1,2,2,2,2,4
1,1,1,1,1,1,1,1,1,7
1,1,1,1,1,1,1,1,2,6
1,1,1,1,1,1,1,1,4,4
1,1,1,1,1,1,2,2,3,3
1,1,1,1,2,2,2,2,2,2
1,1,1,1,1,1,1,1,2,2,4
1,1,1,1,1,1,1,1,1,1,3,3
1,1,1,1,1,1,1,1,2,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,4
1,1,1,1,1,1,1,1,1,1,1,1,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
------------------------
1,2,14
1,5,11
2,7,8
4,6,7
1,1,3,12
1,1,5,10
1,2,3,11
1,2,5,9
1,2,7,7
1,3,4,9
1,3,5,8
1,5,5,6
2,2,6,7
2,4,4,7
1,1,1,6,8
1,1,2,3,10
1,1,3,5,7
1,2,2,3,9
1,2,3,3,8
1,2,3,5,6
1,2,4,5,5
1,3,3,4,6
1,3,4,4,5
2,2,2,4,7
1,1,1,1,6,7
1,1,1,2,4,8
1,1,1,2,6,6
1,1,1,4,4,6
1,1,2,3,3,7
1,2,2,2,5,5
1,2,2,3,3,6
1,2,2,3,4,5
1,2,3,3,4,4
2,2,2,2,2,7
1,1,1,1,1,3,9
1,1,1,1,2,4,7
1,1,1,2,2,2,8
1,1,1,2,2,4,6
1,1,1,2,4,4,4
1,1,1,3,3,3,5
1,2,2,2,2,3,5
1,2,2,2,3,3,4
1,1,1,1,1,2,5,5
1,1,1,1,1,3,3,6
1,1,1,1,1,3,4,5
1,1,1,1,2,2,2,7
1,1,1,2,2,2,2,6
1,1,1,2,2,2,4,4
1,1,1,2,3,3,3,3
1,2,2,2,2,2,3,3
1,1,1,1,1,1,1,2,8
1,1,1,1,1,1,1,4,6
1,1,1,1,1,2,2,3,5
1,1,1,1,1,2,3,3,4
1,1,1,2,2,2,2,2,4
1,1,1,1,1,1,1,1,2,7
1,1,1,1,1,1,1,2,2,6
1,1,1,1,1,1,1,2,4,4
1,1,1,1,1,2,2,2,3,3
1,1,1,2,2,2,2,2,2,2
1,1,1,1,1,1,1,1,1,3,5
1,1,1,1,1,1,1,2,2,2,4
1,1,1,1,1,1,1,1,1,1,1,6
1,1,1,1,1,1,1,1,1,2,3,3
1,1,1,1,1,1,1,2,2,2,2,2
1,1,1,1,1,1,1,1,1,1,1,2,4
1,1,1,1,1,1,1,1,1,1,1,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2
------------------------
4,14
9,9
1,5,12
2,2,14
2,5,11
3,4,11
3,6,9
4,5,9
4,7,7
5,5,8
1,1,8,8
1,2,3,12
1,2,5,10
1,3,4,10
1,5,5,7
2,2,3,11
2,2,5,9
2,2,7,7
2,3,4,9
2,3,5,8
2,5,5,6
3,3,4,8
3,3,6,6
3,4,5,6
4,4,5,5
1,1,1,1,14
1,1,1,7,8
1,1,2,6,8
1,1,4,4,8
1,1,4,6,6
1,2,2,3,10
1,2,3,5,7
1,3,3,4,7
2,2,2,3,9
2,2,3,3,8
2,2,3,5,6
2,2,4,5,5
2,3,3,4,6
2,3,4,4,5
3,3,4,4,4
1,1,1,1,3,11
1,1,1,1,5,9
1,1,1,1,7,7
1,1,1,2,6,7
1,1,1,4,4,7
1,1,2,2,4,8
1,1,2,2,6,6
1,1,2,4,4,6
1,1,3,3,5,5
1,1,4,4,4,4
1,2,2,3,3,7
2,2,2,2,5,5
2,2,2,3,3,6
2,2,2,3,4,5
2,2,3,3,4,4
3,3,3,3,3,3
1,1,1,1,1,3,10
1,1,1,1,2,3,9
1,1,1,1,3,3,8
1,1,1,1,3,5,6
1,1,1,1,4,5,5
1,1,1,2,2,4,7
1,1,2,2,2,2,8
1,1,2,2,2,4,6
1,1,2,2,4,4,4
1,1,2,3,3,3,5
1,1,3,3,3,3,4
2,2,2,2,2,3,5
2,2,2,2,3,3,4
1,1,1,1,1,1,4,8
1,1,1,1,1,1,6,6
1,1,1,1,1,3,3,7
1,1,1,1,2,2,5,5
1,1,1,1,2,3,3,6
1,1,1,1,2,3,4,5
1,1,1,1,3,3,4,4
1,1,1,2,2,2,2,7
1,1,2,2,2,2,2,6
1,1,2,2,2,2,4,4
1,1,2,2,3,3,3,3
2,2,2,2,2,2,3,3
1,1,1,1,1,1,1,4,7
1,1,1,1,1,1,2,2,8
1,1,1,1,1,1,2,4,6
1,1,1,1,1,1,4,4,4
1,1,1,1,2,2,2,3,5
1,1,1,1,2,2,3,3,4
1,1,2,2,2,2,2,2,4
1,1,1,1,1,1,1,1,5,5
1,1,1,1,1,1,1,2,2,7
1,1,1,1,1,1,2,2,2,6
1,1,1,1,1,1,2,2,4,4
1,1,1,1,1,1,3,3,3,3
1,1,1,1,2,2,2,2,3,3
1,1,2,2,2,2,2,2,2,2
1,1,1,1,1,1,1,1,1,1,8
1,1,1,1,1,1,1,1,2,3,5
1,1,1,1,1,1,1,1,3,3,4
1,1,1,1,1,1,2,2,2,2,4
1,1,1,1,1,1,1,1,1,1,1,7
1,1,1,1,1,1,1,1,1,1,2,6
1,1,1,1,1,1,1,1,1,1,4,4
1,1,1,1,1,1,1,1,2,2,3,3
1,1,1,1,1,1,2,2,2,2,2,2
1,1,1,1,1,1,1,1,1,1,2,2,4
1,1,1,1,1,1,1,1,1,1,1,1,3,3
1,1,1,1,1,1,1,1,1,1,2,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,1,4
1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1

---

作者: lulijie    时间: 2009-10-11 13:23:23

3,16
9,10
2,5,12
3,4,12
3,6,10
3,7,9
4,5,10
1,2,8,8
1,4,6,8
1,6,6,6
2,2,3,12
2,2,5,10
2,3,4,10
2,5,5,7
3,3,6,7
3,4,5,7
1,1,1,2,14
1,1,1,5,11
1,1,2,7,8
1,1,4,6,7
1,2,2,6,8
1,2,4,4,8
1,2,4,6,6
1,3,3,3,9
1,3,5,5,5
1,4,4,4,6
2,2,2,3,10
2,2,3,5,7
2,3,3,4,7
1,1,1,1,3,12
1,1,1,1,5,10
1,1,1,2,3,11
1,1,1,2,5,9
1,1,1,2,7,7
1,1,1,3,4,9
1,1,1,3,5,8
1,1,1,5,5,6
1,1,2,2,6,7
1,1,2,4,4,7
1,2,2,2,4,8
1,2,2,2,6,6
1,2,2,4,4,6
1,2,3,3,5,5
1,2,4,4,4,4
1,3,3,3,3,6
1,3,3,3,4,5
2,2,2,3,3,7
1,1,1,1,1,6,8
1,1,1,1,2,3,10
1,1,1,1,3,5,7
1,1,1,2,2,3,9
1,1,1,2,3,3,8
1,1,1,2,3,5,6
1,1,1,2,4,5,5
1,1,1,3,3,4,6
1,1,1,3,4,4,5
1,1,2,2,2,4,7
1,2,2,2,2,2,8
1,2,2,2,2,4,6
1,2,2,2,4,4,4
1,2,2,3,3,3,5
1,2,3,3,3,3,4
1,1,1,1,1,1,6,7
1,1,1,1,1,2,4,8
1,1,1,1,1,2,6,6
1,1,1,1,1,4,4,6
1,1,1,1,2,3,3,7
1,1,1,2,2,2,5,5
1,1,1,2,2,3,3,6
1,1,1,2,2,3,4,5
1,1,1,2,3,3,4,4
1,1,2,2,2,2,2,7
1,2,2,2,2,2,2,6
1,2,2,2,2,2,4,4
1,2,2,2,3,3,3,3
1,1,1,1,1,1,1,3,9
1,1,1,1,1,1,2,4,7
1,1,1,1,1,2,2,2,8
1,1,1,1,1,2,2,4,6
1,1,1,1,1,2,4,4,4
1,1,1,1,1,3,3,3,5
1,1,1,2,2,2,2,3,5
1,1,1,2,2,2,3,3,4
1,2,2,2,2,2,2,2,4
1,1,1,1,1,1,1,2,5,5
1,1,1,1,1,1,1,3,3,6
1,1,1,1,1,1,1,3,4,5
1,1,1,1,1,1,2,2,2,7
1,1,1,1,1,2,2,2,2,6
1,1,1,1,1,2,2,2,4,4
1,1,1,1,1,2,3,3,3,3
1,1,1,2,2,2,2,2,3,3
1,2,2,2,2,2,2,2,2,2
1,1,1,1,1,1,1,1,1,2,8
1,1,1,1,1,1,1,1,1,4,6
1,1,1,1,1,1,1,2,2,3,5
1,1,1,1,1,1,1,2,3,3,4
1,1,1,1,1,2,2,2,2,2,4
1,1,1,1,1,1,1,1,1,1,2,7
1,1,1,1,1,1,1,1,1,2,2,6
1,1,1,1,1,1,1,1,1,2,4,4
1,1,1,1,1,1,1,2,2,2,3,3
1,1,1,1,1,2,2,2,2,2,2,2
1,1,1,1,1,1,1,1,1,1,1,3,5
1,1,1,1,1,1,1,1,1,2,2,2,4
1,1,1,1,1,1,1,1,1,1,1,1,1,6
1,1,1,1,1,1,1,1,1,1,1,2,3,3
1,1,1,1,1,1,1,1,1,2,2,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,2,4
1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2
------------------------
20
3,17
10,10
3,3,14
3,7,10
4,8,8
6,6,8
1,1,4,14
1,1,9,9
1,4,7,8
1,6,6,7
2,2,8,8
2,4,6,8
2,6,6,6
3,3,3,11
3,3,5,9
3,3,7,7
4,4,4,8
4,4,6,6
5,5,5,5
1,1,1,5,12
1,1,2,2,14
1,1,2,5,11
1,1,3,4,11
1,1,3,6,9
1,1,4,5,9
1,1,4,7,7
1,1,5,5,8
1,2,2,7,8
1,2,4,6,7
1,3,3,3,10
1,4,4,4,7
2,2,2,6,8
2,2,4,4,8
2,2,4,6,6
2,3,3,3,9
2,3,5,5,5
2,4,4,4,6
3,3,3,3,8
3,3,3,5,6
3,3,4,5,5
4,4,4,4,4
1,1,1,1,8,8
1,1,1,2,3,12
1,1,1,2,5,10
1,1,1,3,4,10
1,1,1,5,5,7
1,1,2,2,3,11
1,1,2,2,5,9
1,1,2,2,7,7
1,1,2,3,4,9
1,1,2,3,5,8
1,1,2,5,5,6
1,1,3,3,4,8
1,1,3,3,6,6
1,1,3,4,5,6
1,1,4,4,5,5
1,2,2,2,6,7
1,2,2,4,4,7
1,3,3,3,3,7
2,2,2,2,4,8
2,2,2,2,6,6
2,2,2,4,4,6
2,2,3,3,5,5
2,2,4,4,4,4
2,3,3,3,3,6
2,3,3,3,4,5
3,3,3,3,4,4
1,1,1,1,1,1,14
1,1,1,1,1,7,8
1,1,1,1,2,6,8
1,1,1,1,4,4,8
1,1,1,1,4,6,6
1,1,1,2,2,3,10
1,1,1,2,3,5,7
1,1,1,3,3,4,7
1,1,2,2,2,3,9
1,1,2,2,3,3,8
1,1,2,2,3,5,6
1,1,2,2,4,5,5
1,1,2,3,3,4,6
1,1,2,3,4,4,5
1,1,3,3,4,4,4
1,2,2,2,2,4,7
2,2,2,2,2,2,8
2,2,2,2,2,4,6
2,2,2,2,4,4,4
2,2,2,3,3,3,5
2,2,3,3,3,3,4
1,1,1,1,1,1,3,11
1,1,1,1,1,1,5,9
1,1,1,1,1,1,7,7
1,1,1,1,1,2,6,7
1,1,1,1,1,4,4,7
1,1,1,1,2,2,4,8
1,1,1,1,2,2,6,6
1,1,1,1,2,4,4,6
1,1,1,1,3,3,5,5
1,1,1,1,4,4,4,4
1,1,1,2,2,3,3,7
1,1,2,2,2,2,5,5
1,1,2,2,2,3,3,6
1,1,2,2,2,3,4,5
1,1,2,2,3,3,4,4
1,1,3,3,3,3,3,3
1,2,2,2,2,2,2,7
2,2,2,2,2,2,2,6
2,2,2,2,2,2,4,4
2,2,2,2,3,3,3,3
1,1,1,1,1,1,1,3,10
1,1,1,1,1,1,2,3,9
1,1,1,1,1,1,3,3,8
1,1,1,1,1,1,3,5,6
1,1,1,1,1,1,4,5,5
1,1,1,1,1,2,2,4,7
1,1,1,1,2,2,2,2,8
1,1,1,1,2,2,2,4,6
1,1,1,1,2,2,4,4,4
1,1,1,1,2,3,3,3,5
1,1,1,1,3,3,3,3,4
1,1,2,2,2,2,2,3,5
1,1,2,2,2,2,3,3,4
2,2,2,2,2,2,2,2,4
1,1,1,1,1,1,1,1,4,8
1,1,1,1,1,1,1,1,6,6
1,1,1,1,1,1,1,3,3,7
1,1,1,1,1,1,2,2,5,5
1,1,1,1,1,1,2,3,3,6
1,1,1,1,1,1,2,3,4,5
1,1,1,1,1,1,3,3,4,4
1,1,1,1,1,2,2,2,2,7
1,1,1,1,2,2,2,2,2,6
1,1,1,1,2,2,2,2,4,4
1,1,1,1,2,2,3,3,3,3
1,1,2,2,2,2,2,2,3,3
2,2,2,2,2,2,2,2,2,2
1,1,1,1,1,1,1,1,1,4,7
1,1,1,1,1,1,1,1,2,2,8
1,1,1,1,1,1,1,1,2,4,6
1,1,1,1,1,1,1,1,4,4,4
1,1,1,1,1,1,2,2,2,3,5
1,1,1,1,1,1,2,2,3,3,4
1,1,1,1,2,2,2,2,2,2,4
1,1,1,1,1,1,1,1,1,1,5,5
1,1,1,1,1,1,1,1,1,2,2,7
1,1,1,1,1,1,1,1,2,2,2,6
1,1,1,1,1,1,1,1,2,2,4,4
1,1,1,1,1,1,1,1,3,3,3,3
1,1,1,1,1,1,2,2,2,2,3,3
1,1,1,1,2,2,2,2,2,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,8
1,1,1,1,1,1,1,1,1,1,2,3,5
1,1,1,1,1,1,1,1,1,1,3,3,4
1,1,1,1,1,1,1,1,2,2,2,2,4
1,1,1,1,1,1,1,1,1,1,1,1,1,7
1,1,1,1,1,1,1,1,1,1,1,1,2,6
1,1,1,1,1,1,1,1,1,1,1,1,4,4
1,1,1,1,1,1,1,1,1,1,2,2,3,3
1,1,1,1,1,1,1,1,2,2,2,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,2,2,4
1,1,1,1,1,1,1,1,1,1,1,1,1,1,3,3
1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,4
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1

---

作者: lulijie    时间: 2009-10-11 13:29:41

phileas的方法，确实不错。
不知有没有办法也应用于二维，甚至三维中。
莫非只能用我的这种笨方法来计算。但对于二维情况，用我的方法，如何编程都是个难题。
就像我计算一维情况，稍不注意，哪里有个小疏漏，就得出不正确的结果。

---

作者: noski    时间: 2009-10-11 15:51:54     标题: 回复 12# 的帖子

其实我这个先手保留权，就是你的问题的兄弟篇——谁取了最后一个数谁输。。

另外，有个简单推断法：
如果n为奇数，X(n)=1
如果n为偶数，且X(n-2)=0，则X(n)=1
如果n为偶数，且X(n-2)=1，那么先手的策略就是把n分成一个奇数i和一个偶数j，并使X(j)=1。不过这个情况还没想通如何判断能不能赢。。

---

作者: phileas    时间: 2009-10-11 21:09:08     标题: 回复 21# 的帖子

对于拿到最后一个算输的问题，其一般解法见：
http://bbs.mf8-china.com/viewthr ... page%3D1&page=2
15楼

---

作者: flwb    时间: 2009-10-18 11:46:22

原帖由 noski 于 2009-10-10 10:30 发表
首先，有个对称性取数策略：
结论A. 如果轮到某一方下子时，剩下奇数个数字，那么该方就可以通过下在正中间，然后对称下子的方法取胜。
由结论A可推出：n为奇数时，先取方必胜。

而当n为偶数时，先取方有三种策 ...

假设N=10,现在已经数到5,还剩678910五个数,你数中间的8,我数10胜,你怎么会必胜?

明白了,你说的剩下奇数个数字,应该是指可数的数字!

[ 本帖最后由 flwb 于 2009-10-18 11:55 编辑 ]

---

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

Powered by Discuz! X2