取牙签智力游戏

hujunhua

8#的问题，如何编个程序来计算一下在四堆的情况下，应该留给对手什么样的局面？

Lwins_G

hujunhua 发表于 2014-1-21 11:20
8#的问题，如何编个程序来计算一下在四堆的情况下，应该留给对手什么样的局面？

用c++粗略地写了一个复杂度为`O(N^6)`的程序（`N`为预编译可调整参数）。

功能是每次输入四个数`x,y,z,w \leq N`，输出`(x,y,z,w)`对应的状态先手胜或负。

另外，我还发现了一些有趣的东西，就先不说出来了。用来验证这些有趣的东西的代码并没有删去。

1. #include <iostream>
   
2. #include <cstdio>
   
3. #include <memory.h>
   
4. 
   
5. #define N 30
   
6. 
   
7. using namespace std;
   
8. 
   
9. bool f[N + 1][N + 1][N + 1][N + 1];
   
10. 
    
11. bool check(int x, int y, int z, int w)
    
12. {
    
13.     int a[4], b[40], t, q;
    
14.     a[0] = x; a[1] = y; a[2] = z; a[3] = w;
    
15.     memset(b, 0, sizeof(b));
    
16.     for (int i = 0; i < 4; i++)
    
17.     {
    
18.         t = 1; q = 0;
    
19.         while (a[i])
    
20.         {
    
21.             if (a[i] & t)
    
22.             {
    
23.                 b[q]++;
    
24.                 a[i] -= t;
    
25.             }
    
26.             t *= 2;
    
27.             q++;
    
28.         }
    
29.     }
    
30.     for (int i = 0; i < 40; i++) if (b[i] % 3 != 0) return 0;
    
31.     return 1;
    
32. }
    
33. 
    
34. int main()
    
35. {
    
36.     bool flag;
    
37.     for (int a = 0; a <= N; a++)
    
38.         for (int b = 0; b <= N; b++)
    
39.             for (int c = 0; c <= N; c++)
    
40.                 for (int d = 0; d <= N; d++)
    
41.                 {
    
42.                     flag = 0;
    
43.                     for (int i = 0; i < a; i++) if (!f[i][b][c][d]) flag = 1;
    
44.                     for (int i = 0; i < b; i++) if (!f[a][i][c][d]) flag = 1;
    
45.                     for (int i = 0; i < c; i++) if (!f[a][b][i][d]) flag = 1;
    
46.                     for (int i = 0; i < d; i++) if (!f[a][b][c][i]) flag = 1;
    
47.                     for (int i = 0; i < a; i++)
    
48.                         for (int j = 0; j < b; j++) if (!f[i][j][c][d]) flag = 1;
    
49.                     for (int i = 0; i < a; i++)
    
50.                         for (int j = 0; j < c; j++) if (!f[i][b][j][d]) flag = 1;
    
51.                     for (int i = 0; i < a; i++)
    
52.                         for (int j = 0; j < d; j++) if (!f[i][b][c][j]) flag = 1;
    
53.                     for (int i = 0; i < b; i++)
    
54.                         for (int j = 0; j < c; j++) if (!f[a][i][j][d]) flag = 1;
    
55.                     for (int i = 0; i < b; i++)
    
56.                         for (int j = 0; j < d; j++) if (!f[a][i][c][j]) flag = 1;
    
57.                     for (int i = 0; i < c; i++)
    
58.                         for (int j = 0; j < d; j++) if (!f[a][b][i][j]) flag = 1;
    
59.                     f[a][b][c][d] = flag;
    
60.                 }
    
61.    
    
62.     /*
    
63.     for (int a = 0; a <= N; a++)
    
64.         for (int b = 0; b <= N; b++)
    
65.             for (int c = 0; c <= N; c++)
    
66.                 for (int d = 0; d <= N; d++)
    
67.                     if (f[a][b][c][d] ^ !check(a, b, c, d)) cout << "ERROR " << a << " " << b << " " << c << " " << d << endl;
    
68.     */
    
69.    
    
70.     cout << "Preprocessing completed.\n";
    
71.    
    
72.     while (1)
    
73.     {
    
74.         int x, y, z, w;
    
75.         cin >> x >> y >> z >> w;
    
76.         if (f[x][y][z][w]) cout << "WIN\n"; else cout << "LOSE\n";
    
77.     }
    
78. }

复制代码

hujunhua

不要这种检验程序，要的是生成程序，比如限制每堆数量小于100. 我手工计算，应该留给对手的局面是：
{1,2,3,4}, {1,5,6,7}, {1,8,9,10}, {1,11,12,13}, ..., {1,3a-1,3a,3a+1}, ..., {1,95,96,97}, {1,98,99,100};
{2,5,8,9}, {2,6,10,11), {2,7,12,13}, {2,14,17,18}, {2,15,19,20}, {2,16,21,22}, ..., {2,5+9a+b,8+9a+b,9+9a+b}(b=0,1,2), ..., {2,95,98,99};
{3,5,10,11}, {3,6,8,10},{3,7,14,15}, {3,9,12,16}, {3,13,17,20}, {3,18,21,23}, {3,19,22,24},.....

应该可以编一种递归程序。

Lwins_G

hujunhua 发表于 2014-1-21 17:54
不要这种检验程序，要的是生成程序，比如限制每堆数量小于100. 我手工计算，应该留给对手的局面是：
{1,2, ...

我修改了一下，另外还上传了一个编译后的可执行文件，希望能满足你的要求。（需要`N \leq 50`）

1. #include <iostream>
   
2. #include <cstdio>
   
3. #include <conio.h>
   
4. 
   
5. #define NN 50
   
6. 
   
7. using namespace std;
   
8. 
   
9. bool f[NN + 1][NN + 1][NN + 1][NN + 1];
   
10. 
    
11. int main()
    
12. {
    
13.     int N;
    
14.     bool flag;
    
15.     cout << "Input N (not greater than " << NN << ") = ";
    
16.     cin >> N;
    
17.     for (int a = 0; a <= N; a++)
    
18.         for (int b = 0; b <= N; b++)
    
19.             for (int c = 0; c <= N; c++)
    
20.                 for (int d = 0; d <= N; d++)
    
21.                 {
    
22.                     flag = 0;
    
23.                     for (int i = 0; i < a; i++) if (!f[i][b][c][d]) flag = 1;
    
24.                     for (int i = 0; i < b; i++) if (!f[a][i][c][d]) flag = 1;
    
25.                     for (int i = 0; i < c; i++) if (!f[a][b][i][d]) flag = 1;
    
26.                     for (int i = 0; i < d; i++) if (!f[a][b][c][i]) flag = 1;
    
27.                     for (int i = 0; i < a; i++)
    
28.                         for (int j = 0; j < b; j++) if (!f[i][j][c][d]) flag = 1;
    
29.                     for (int i = 0; i < a; i++)
    
30.                         for (int j = 0; j < c; j++) if (!f[i][b][j][d]) flag = 1;
    
31.                     for (int i = 0; i < a; i++)
    
32.                         for (int j = 0; j < d; j++) if (!f[i][b][c][j]) flag = 1;
    
33.                     for (int i = 0; i < b; i++)
    
34.                         for (int j = 0; j < c; j++) if (!f[a][i][j][d]) flag = 1;
    
35.                     for (int i = 0; i < b; i++)
    
36.                         for (int j = 0; j < d; j++) if (!f[a][i][c][j]) flag = 1;
    
37.                     for (int i = 0; i < c; i++)
    
38.                         for (int j = 0; j < d; j++) if (!f[a][b][i][j]) flag = 1;
    
39.                     f[a][b][c][d] = flag;
    
40.                 }
    
41.     cout << "Preprocessing completed. I'll output the result to "result.txt".\n";
    
42.     FILE *fout;
    
43.     fout = fopen("result.txt", "w");
    
44.     fprintf(fout, "The LOSE states are:\n");
    
45.     for (int a = 0; a <= N; a++)
    
46.         for (int b = a; b <= N; b++)
    
47.             for (int c = b; c <= N; c++)
    
48.                 for (int d = c; d <= N; d++)
    
49.                     if (!f[a][b][c][d])
    
50.                         fprintf(fout, "(%d,%d,%d,%d)\n", a, b, c, d);
    
51.     fclose(fout);
    
52.     cout << "Completed. Press anykey to continue...\n";
    
53.     getch();
    
54. }

复制代码

Lwins_G

hujunhua 发表于 2014-1-21 17:54
不要这种检验程序，要的是生成程序，比如限制每堆数量小于100. 我手工计算，应该留给对手的局面是：
{1,2, ...

对你的{1,2,3,4}略有疑问，因为它不出现在我的程序打印出来的结果中。我们来试试，我先。如果你感兴趣的话可以直接点评在这个贴子上。
{1,2,3,4}->{1,2,3,3}

mathe

1. #include <iostream>
   
2. #include <cstdio>
   
3. using namespace std;
   
4. #define NN 99
   
5. int dmap[NN+1][NN+1];
   
6. #define CREATE_DATA(a,b) ((a)*(NN+1)+(b))
   
7. void init_dmap()
   
8. {
   
9.     int i;
   
10.     for(i=1;i<=NN;i++){
    
11.        dmap[0][i]=CREATE_DATA(i,i);
    
12.        dmap[i][i]=CREATE_DATA(0,i);
    
13.     }
    
14. }
    
15. 
    
16. int get_eq_cd(int a, int b, int& c, int& d)
    
17. {
    
18.     int r=dmap[a][b];
    
19.     if(r==0)return 0;
    
20.     c=r/(NN+1);
    
21.     d=r%(NN+1);
    
22.     return 1;
    
23. }
    
24. 
    
25. void add_eq_data(int a, int b, int c, int d)
    
26. {
    
27.     if(b>NN)return;
    
28.     dmap[a][b]=CREATE_DATA(c,d);
    
29.     if(c>NN)return;
    
30.     dmap[a][c]=CREATE_DATA(b,d);
    
31.     dmap[b][c]=CREATE_DATA(a,d);
    
32.     if(c>NN)return;
    
33.     dmap[a][d]=CREATE_DATA(b,d);
    
34.     dmap[b][d]=CREATE_DATA(a,c);
    
35.     dmap[c][d]=CREATE_DATA(a,b);
    
36.     printf("%d,%d,%d,%d\n",a,b,c,d);
    
37. }
    
38. 
    
39. 
    
40. 
    
41. int main()
    
42. {
    
43.     init_dmap();
    
44.     for (int a = 1; a <= NN; a++)
    
45.         for (int b = a; b <= NN; b++){
    
46.             int c,d;
    
47.             if(dmap[a][b]!=0)continue;
    
48.             for (c = b; c <= NN; c++){
    
49.                 for (d = c; d <= NN; d++)
    
50.                 {
    
51.                     int x,y;bool found=false;
    
52.                     if(get_eq_cd(a,c,x,y)&&x<=b&&y<=d)found=true;
    
53.                     if(!found&&get_eq_cd(a,d,x,y)&&x<=b&&y<=c)found=true;
    
54.                     if(!found&&get_eq_cd(b,c,x,y)&&x<=a&&y<=d)found=true;
    
55.                     if(!found&&get_eq_cd(b,d,x,y)&&x<=a&&y<=c)found=true;
    
56.                     if(!found&&get_eq_cd(c,d,x,y)&&x<=a&&y<=b)found=true;
    
57.                     if(!found){
    
58.                        add_eq_data(a,b,c,d);
    
59.                        break;
    
60.                     }
    
61.                 }
    
62.                 if(d<=NN)break;
    
63.             }
    
64.            
    
65.         }
    
66.        return 0;  
    
67. }
    

复制代码

mathe

想错了，我这方法好想不行。我程序中映射要改多值才行

hujunhua

取N<=30, 上面的程序输出结果为：
(1,2,3,3)
(1,4,5,5)
(1,6,7,7)
(1,8,9,9)
(1,10,11,11)
(1,12,13,13)
(1,14,15,15)
(1,16,17,17)
(1,18,19,19)
(1,20,21,21)
(1,22,23,23)
(1,24,25,25)
(1,26,27,27)
(1,28,29,29)
(2,4,6,6)
(2,5,7,7)
(2,8,10,10)
(2,9,11,11)
(2,12,14,14)
(2,13,15,15)
(2,16,18,18)
(2,17,19,19)
(2,20,22,22)
(2,21,23,23)
(2,24,26,26)
(2,25,27,27)
(2,28,30,30)
(3,4,7,7)
(3,5,6,7)
(3,8,11,11)
(3,9,10,11)
(3,12,15,15)
(3,13,14,15)
(3,16,19,19)
(3,17,18,19)
(3,20,23,23)
(3,21,22,23)
(3,24,27,27)
(3,25,26,27)
(4,8,12,12)
(4,9,13,13)
(4,10,14,14)
(4,11,15,15)
(4,16,20,20)
(4,17,21,21)
(4,18,22,22)
(4,19,23,23)
(4,24,28,28)
(4,25,29,29)
(4,26,30,30)
(5,8,13,13)
(5,9,12,13)
(5,10,15,15)
(5,11,14,15)
(5,16,21,21)
(5,17,20,21)
(5,18,23,23)
(5,19,22,23)
(5,24,29,29)
(5,25,28,29)
(6,8,14,14)
(6,9,15,15)
(6,10,12,14)
(6,11,13,15)
(6,16,22,22)
(6,17,23,23)
(6,18,20,22)
(6,19,21,23)
(6,24,30,30)
(6,26,28,30)
(7,8,15,15)
(7,9,14,15)
(7,10,13,15)
(7,11,12,15)
(7,11,13,14)
(7,16,23,23)
(7,17,22,23)
(7,18,21,23)
(7,19,20,23)
(7,19,21,22)
(7,27,29,30)
(8,16,24,24)
(8,17,25,25)
(8,18,26,26)
(8,19,27,27)
(8,20,28,28)
(8,21,29,29)
(8,22,30,30)
(9,16,25,25)
(9,17,24,25)
(9,18,27,27)
(9,19,26,27)
(9,20,29,29)
(9,21,28,29)
(10,16,26,26)
(10,17,27,27)
(10,18,24,26)
(10,19,25,27)
(10,20,30,30)
(10,22,28,30)
(11,16,27,27)
(11,17,26,27)
(11,18,25,27)
(11,19,24,27)
(11,19,25,26)
(11,23,29,30)
(12,16,28,28)
(12,17,29,29)
(12,18,30,30)
(12,20,24,28)
(12,21,25,29)
(12,22,26,30)
(13,16,29,29)
(13,17,28,29)
(13,20,25,29)
(13,21,24,29)
(13,21,25,28)
(13,23,27,30)
(14,16,30,30)
(14,18,28,30)
(14,20,26,30)
(14,22,24,30)
(14,22,26,28)
(14,23,27,29)
(15,19,29,30)
(15,21,27,30)
(15,22,27,29)
(15,23,25,30)
(15,23,26,29)
(15,23,27,28)

hujunhua

{1,2a,2a+1,2a+1}
{2,4a+b,4a+b+2,4a+b+2} (b=0,1)
{3,4a,4a+3,4a+3},{3,4a+1,4a+2,4a+3}
{4,8a+b,8a+b+4,8a+b+4}(b=0,1,2,3)
{5,8a+b,8a+b+5,8a+b+5},{5,8a+b+1,8a+b+4,8a+b+5}(b=0,2)
{6,8a+b,8a+b+6,8a+b+6},{6,8a+b+2,8a+b+4,8a+b+6}(b=0,1)

当最小数为\( 2^n \)时，猜想为：\( 2^n*\{1,2,3,3\}+\left( 2^{n+1}k+a \right)*\{0,1,1,1\},\left( k\geq0,a=0,1,2,\cdots,2^n-1 \right) \)
看到周期仍然与\( 2^n \)有关，还是化成二进数么？

mathe

的确结果同二进制相关，不同的二进制位可以分开处理，结果非常简单。hujunhua出的这个题目很棒呀。而且每次允许取三堆或四堆等结论类似。