划数游戏

〇〇

在如下的4*4方格中，2人
依次划去1~4个相邻的数（可以是纵横或斜45度），比如：0102,0408,030609
但当划的路径中已经有数被划去，则不能再划.比如02已划，则不能010203
划去最后一个方格的数者判负，请问先后手谁有必胜的策略？

01 02 03 04
05 06 07 08
09 10 11 12
13 14 15 16

mathe

这个题目用计算机很简单.状态只有最多$2^16$种

gxqcn

$[(1,2,3,4),(5,6,7,8),(9,10,11,12),(13,14,15,16)]$
■ 用数学公式LaTeX重新排版

1. 01 02 03 04
   
2. 05 06 07 08
   
3. 09 10 11 12
   
4. 13 14 15 16

复制代码

■ 用code标签重新排版，可避免英文字母或数字对不齐现象

1. +----+----+----+----+
   
2. | 01 | 02 | 03 | 04 |
   
3. +----+----+----+----+
   
4. | 05 | 06 | 07 | 08 |
   
5. +----+----+----+----+
   
6. | 09 | 10 | 11 | 12 |
   
7. +----+----+----+----+
   
8. | 13 | 14 | 15 | 16 |
   
9. +----+----+----+----+

复制代码

■ 再手工加上表格线

01	02	03	04
05	06	07	08
09	10	11	12
13	14	15	16

■ 直接用表格排版（如果表格比较小，应限定table=xxx；如果将table居中，其内的所有单元格均居中）

〇〇

有几种必胜和必败的形
必胜：
倒数第3步：曲3和不相连的1，方4,不是直4的双直2,对方下步无论如何不能给出直1

必败：
倒数第3步：直2，直3，直4，对方下步总能给出直1

mathe

N*N的格子,
N=1,2,4先手败
N=3,5先手胜

1. 
   
2. #include <string.h>
   
3. #include <assert.h>
   
4. #include <stdlib.h>
   
5. #include <vector>
   
6. using namespace std;
   
7. #define N 4
   
8. #define BITS (N*N)
   
9. typedef unsigned int SET;
   
10. #define BIT(x,y)  ((x)+(y)*N)
    
11. char result[1<<BITS];
    
12. vector<SET> lines;
    
13. void init_lines()
    
14. {
    
15.     int i;
    
16.     for(i=0;i<BITS;i++){///single element
    
17.         SET s=1<<i;
    
18.         lines.push_back(s);
    
19.     }
    
20.     for(i=0;i<N;i++){
    
21.         int x=i,y=0;
    
22.         SET s=1<<BIT(x,y);
    
23.         while(++y<N){
    
24.             s|=1<<BIT(x,y);
    
25.             lines.push_back(s);
    
26.         }
    
27.     }
    
28.     for(i=0;i<N;i++){
    
29.         int x=0,y=i;
    
30.         SET s=1<<BIT(x,y);
    
31.         while(++x<N){
    
32.             s|=1<<BIT(x,y);
    
33.             lines.push_back(s);
    
34.         }
    
35.     }
    
36.     for(i=0;i<N;i++){
    
37.         int x=i,y=0;
    
38.         SET s=1<<BIT(x,y);
    
39.         while(--x>=0&&++y<N){
    
40.             s|=1<<BIT(x,y);
    
41.             lines.push_back(s);
    
42.         }
    
43.     }
    
44.     for(i=0;i<N;i++){
    
45.         int x=i,y=0;
    
46.         SET s=1<<BIT(x,y);
    
47.         while(++x<N&&++y<N){
    
48.             s|=1<<BIT(x,y);
    
49.             lines.push_back(s);
    
50.         }
    
51.     }
    
52.     for(i=1;i<N-1;i++){
    
53.         int x=i,y=N-1;
    
54.         SET s=1<<BIT(x,y);
    
55.         while(--x>=0&&--y>=0){
    
56.             s|=1<<BIT(x,y);
    
57.             lines.push_back(s);
    
58.         }
    
59.     }
    
60.     for(i=1;i<N-1;i++){
    
61.         int x=i,y=N-1;
    
62.         SET s=1<<BIT(x,y);
    
63.         while(++x<N&&--y>=0){
    
64.             s|=1<<BIT(x,y);
    
65.             lines.push_back(s);
    
66.         }
    
67.     }
    
68. }
    
69. #define FAIL (char)-1
    
70. #define SUCC (char)1
    
71. char search(SET s)
    
72. {
    
73.     int i;
    
74.     if(result[s]!=0)
    
75.         return result[s];
    
76.     for(i=0;i<lines.size();i++){
    
77.         if((s&lines[i])==lines[i]){
    
78.             char r=search(s&~lines[i]);
    
79.             if(r==FAIL)
    
80.                 break;
    
81.         }
    
82.     }
    
83.     if(i==lines.size()){
    
84.         result[s]=FAIL;
    
85.     }else{
    
86.         result[s]=SUCC;
    
87.     }
    
88.     return result[s];
    
89. }
    
90. 
    
91. int main()
    
92. {
    
93.     init_lines();
    
94.     result[0]=SUCC;
    
95.     int i;
    
96.     for(i=0;i<BITS;i++){
    
97.         result[1<<i]=FAIL;
    
98.     }
    
99.     char r=search((1<<BITS)-1);
    
100.     if(r==SUCC){
     
101.         printf("First win\n");
     
102.     }else{
     
103.         printf("First fail\n");
     
104.     }
     
105. }
     

复制代码

〇〇

阅读理解中

〇〇

没太看懂，把cpp翻译成标准C,执行结果
58 （才这么多，代表什么？）
First fail

1. 
   
2. //#include <string.h>
   
3. //#include <assert.h>
   
4. #include <stdio.h>
   
5. #include <stdlib.h>
   
6. //#include <vector>
   
7. //using namespace std;
   
8. #define N 4
   
9. #define BITS (N*N)
   
10. typedef unsigned int SET;
    
11. #define BIT(x,y)  ((x)+(y)*N)
    
12. #define lines_push_back(s) lines[p++]=s
    
13. char result[1<<BITS];
    
14. //vector<SET> lines;
    
15. SET lines[10000000L];
    
16. int lines_size=0;
    
17. void init_lines()
    
18. {
    
19.     int i;
    
20.     int p=0;
    
21.     for(i=0;i<BITS;i++){///single element
    
22.         SET s=1<<i;
    
23.         lines_push_back(s);
    
24.     }
    
25.     for(i=0;i<N;i++){
    
26.         int x=i,y=0;
    
27.         SET s=1<<BIT(x,y);
    
28.         while(++y<N){
    
29.             s|=1<<BIT(x,y);
    
30.             lines_push_back(s);
    
31.         }
    
32.     }
    
33.     for(i=0;i<N;i++){
    
34.         int x=0,y=i;
    
35.         SET s=1<<BIT(x,y);
    
36.         while(++x<N){
    
37.             s|=1<<BIT(x,y);
    
38.             lines_push_back(s);
    
39.         }
    
40.     }
    
41.     for(i=0;i<N;i++){
    
42.         int x=i,y=0;
    
43.         SET s=1<<BIT(x,y);
    
44.         while(--x>=0&&++y<N){
    
45.             s|=1<<BIT(x,y);
    
46.             lines_push_back(s);
    
47.         }
    
48.     }
    
49.     for(i=0;i<N;i++){
    
50.         int x=i,y=0;
    
51.         SET s=1<<BIT(x,y);
    
52.         while(++x<N&&++y<N){
    
53.             s|=1<<BIT(x,y);
    
54.             lines_push_back(s);
    
55.         }
    
56.     }
    
57.     for(i=1;i<N-1;i++){
    
58.         int x=i,y=N-1;
    
59.         SET s=1<<BIT(x,y);
    
60.         while(--x>=0&&--y>=0){
    
61.             s|=1<<BIT(x,y);
    
62.             lines_push_back(s);
    
63.         }
    
64.     }
    
65.     for(i=1;i<N-1;i++){
    
66.         int x=i,y=N-1;
    
67.         SET s=1<<BIT(x,y);
    
68.         while(++x<N&&--y>=0){
    
69.             s|=1<<BIT(x,y);
    
70.             lines_push_back(s);
    
71.         }
    
72.     }
    
73.     lines_size=p;
    
74.     printf("%d\n",lines_size);
    
75. }
    
76. #define FAIL (char)-1
    
77. #define SUCC (char)1
    
78. char search(SET s)
    
79. {
    
80.     int i;
    
81.     if(result[s]!=0)
    
82.         return result[s];
    
83.     for(i=0;i<lines_size;i++){
    
84.         if((s&lines[i])==lines[i]){
    
85.             char r=search(s&~lines[i]);
    
86.             if(r==FAIL)
    
87.                 break;
    
88.         }
    
89.     }
    
90.     if(i==lines_size){
    
91.         result[s]=FAIL;
    
92.     }else{
    
93.         result[s]=SUCC;
    
94.     }
    
95.     return result[s];
    
96. }
    
97. 
    
98. int main()
    
99. {
    
100.     init_lines();
     
101.     result[0]=SUCC;
     
102.     int i;
     
103.     for(i=0;i<BITS;i++){
     
104.         result[1<<i]=FAIL;
     
105.     }
     
106.     char r=search((1<<BITS)-1);
     
107.     if(r==SUCC){
     
108.         printf("First win\n");
     
109.     }else{
     
110.         printf("First fail\n");
     
111.     }
     
112. }
     

复制代码

mathe

很简单,我们用一个N*N比特的二进制数表示方格当前的状态.对于每个格子对应比特是1表示这个格子还没有被划掉,0表示被划掉.所以初始状态为((1<<BITS)-1),也就是所有格子没有被划掉.
数组result[]用来保存每个方格状态是先手胜还是后手胜.先手胜结果保存为SUCC,后手胜结果保存为FAIL.
函数search用来计算每个方格状态是先手胜还是后手胜.先查询result[]判断是否已经计算过.