划数游戏

〇〇

在如下的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先手胜

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. }
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

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. }
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<