一个选数游戏
不知这里有没有发过？两人轮流从给定的n个正整数中选数，要求是不能选已选过的数的因子，谁首先无数可选就算输。
容易证明，如果这些数中有1，则先手有必胜策略。
但如果没有1，好像就有难度了。比如对于从2到n的连续整数，有没有什么好的算法能判定胜负？已有的算法确定到多大的n了？ 从小往大选？ 想了几天，没想出什么好的解法，只能暴力搜索。写了个穷举的python程序来判断一个局面是胜局还是败局。对于从2到n的连续整数的初始局面，目前用我的笔记本验证到了n=39。结果是n=3，7，28，34，35时为败局，其余都是胜局。再大的n就困难了，计算量指数增长。 你的计算量可能是O(2^n)，我优化到了O(2^(n/2))，算到了65，没有新发现，后面全是赢：
'n 胜负 尼姆值
02win1
03 lose0
04win3
05win2
06win1
07 lose0
08win1
09win1
10win2
11win3
12win3
13win2
14win1
15win2
16win8
17win9
18win2
19win3
20win5
21win7
22win4
23win5
24win3
25win2
26win1
27win6
28 lose0
29win1
30win8
31win9
32win 10
33win3
34 lose0
35 lose0
36win 13
37win 12
38win9
39win9
40win 13
41win 12
42win8
43win9
44win7
45win 16
46win9
47win8
48win 15
49win 12
50win9
51win9
52win 11
53win 10
54win 13
55win2
56win 19
57win 19
58win 17
59win 16
60win 21
61win 20
62win 16
63win1
64win 12
65win1
--------------------------------
Process exited after 11.52 seconds with return value
请按任意键继续. . .
我感觉这个优化没啥用，计算量还是指数级增长的 推荐用nauty库可以将每个图标准化 KeyTo9_Fans 发表于 2024-5-28 10:54
你的计算量可能是O(2^n)，我优化到了O(2^(n/2))，算到了65，没有新发现，后面全是赢：
我感觉这个优化没啥 ...
厉害！敢问您都做了哪些优化？
另一个问题是，为啥败局数量这么少？有没有可能败局数量是有限的？ 当连通块个数为1时，我计算连通块的尼姆数
如果尼姆数为0，表明这是先手必败局面，如果尼姆数非0，表明这是先手必胜局面，胜法就是取走一个数字，使得剩下局面的尼姆数为0
当连通块个数大于1时，我分别计算每个连通块的尼姆数，然后求这些数值的异或和
如果异或和为0，表明这是先手必败局面，不论我方怎么取，都会使得异或和非0，对方每次走到异或和为0的局面即可获胜
我开了一个从 到 尼姆数 的映射表，每次遇到一个新局面，先查询这个局面是否在表里
如果在，直接从表中读出这个局面的 尼姆数，如果不在，则递归计算这个局面的尼姆数，然后存到映射表里
我使用的整数变量只有64个二进制位，这就是我为什么只计算到65的原因
再多一个数，局面数就超过64个二进制位了，需要改用128个二进制位的整数变量，才能继续算 改用128比特的整数来存储局面，继续计算，耗时40个小时，计算到了n=120，就把我电脑的内存耗光了，没法再多算一个n了：
计算结果如下表所示：
n 胜负 尼姆值 内存消耗(KB)
2 win 1 0.1
3 lose 0 0.2
4 win 3 0.4
5 win 2 0.5
6 win 1 0.9
7 lose 0 1
8 win 1 1.4
9 win 1 1.7
10 win 2 2.3
11 win 3 2.4
12 win 3 3.4
13 win 2 3.5
14 win 1 4.5
15 win 2 5.7
16 win 8 7.1
17 win 9 7.2
18 win 2 9.4
19 win 3 9.5
20 win 5 12.3
21 win 7 14.3
22 win 4 16.9
23 win 5 17
24 win 3 22.5
25 win 2 24.8
26 win 1 29.8
27 win 6 35.1
28 lose 0 44.2
29 win 1 44.3
30 win 8 59.2
31 win 9 59.3
32 win 10 72.8
33 win 3 81.2
34 lose 0 94.2
35 lose 0 108.8
36 win 13 135.7
37 win 12 135.8
38 win 9 161.6
39 win 9 186.2
40 win 13 232.2
41 win 12 232.3
42 win 8 301.1
43 win 9 301.2
44 win 7 375.7
45 win 16 455.7
46 win 9 526.3
47 win 8 526.4
48 win 15 666.5
49 win 12 709.3
50 win 9 893.5
51 win 9 1006.5
52 win 11 1290.6
53 win 10 1290.7
54 win 13 1709.7
55 win 2 1932.2
56 win 19 2390
57 win 19 2595
58 win 17 2921.6
59 win 16 2921.7
60 win 21 3676.4
61 win 20 3676.5
62 win 16 4329.5
63 win 1 5199.5
64 win 12 6249.9
65 win 1 6852.4
66 lose 0 8503.8
67 win 1 8503.9
68 win 21 10531.9
69 win 23 11410.5
70 win 11 15136.5
71 win 10 15136.6
72 win 2 19119.1
73 win 3 19119.2
74 lose 0 21973.8
75 win 19 26582.6
76 win 1 35078.5
77 win 25 38759.4
78 win 10 52828
79 win 11 52828.1
80 win 4 67955.6
81 win 20 78118.2
82 win 24 86476.8
83 win 25 86476.9
84 lose 0 108104.1
85 win 7 117381.9
86 win 4 134098.9
87 win 4 145333.1
88 win 10 176436.2
89 win 11 176436.3
90 win 31 217252.5
91 win 2 233998.8
92 win 18 292007.3
93 win 24 309056.7
94 win 28 351706.5
95 win 26 392502.9
96 win 9 484447.6
97 win 8 484447.7
98 win 3 608204.8
99 win 28 716643.7
100 win 4 891533.9
101 win 5 891534
102 win 5 1163701.9
103 win 4 1163702
104 win 13 1451144.5
105 win 1 1729338.2
106 win 2 1954464.8
107 win 3 1954464.9
108 win 25 2423816.9
109 win 24 2423817
110 win 33 3100514.5
111 win 27 3335844.3
112 win 7 4090798.4
113 win 6 4090798.5
114 win 6 5433328.4
115 win 9 5899338.8
116 lose 0 7520879.9
117 win 17 9007900.9
118 win 18 10080182.7
119 win 29 10977835.5
120 win 38
最新发现：n=66、74、84、116为败局
这个数列【3 7 28 34 35 66 74 84 116】目前还没有被OEIS收录，很可能是楼主首创的 KeyTo9_Fans 发表于 2024-5-28 22:29
改用128比特的整数来存储局面，继续计算，耗时40个小时，计算到了n=120，就把我电脑的内存耗光了，没法再多 ...
【3 7 28 34 35 66 74 84 116】目前还没有被OEIS收录
这个数列显然与素数分布有关，不可能搞出一个通项公式来，也不存在一个数论算法。
页:
[1]