8#的问题，如何编个程序来计算一下在四堆的情况下，应该留给对手什么样的局面？
hujunhua 发表于 2014-1-21 11:20
8#的问题，如何编个程序来计算一下在四堆的情况下，应该留给对手什么样的局面？
用c++粗略地写了一个复杂度为`O(N^6)`的程序（`N`为预编译可调整参数）。
功能是每次输入四个数`x,y,z,w \leq N`，输出`(x,y,z,w)`对应的状态先手胜或负。
另外，我还发现了一些有趣的东西，就先不说出来了。用来验证这些有趣的东西的代码并没有删去。
#include <iostream>
#include <cstdio>
#include <memory.h>
#define N 30
using namespace std;
bool f;
bool check(int x, int y, int z, int w)
{
int a, b, t, q;
a = x; a = y; a = z; a = w;
memset(b, 0, sizeof(b));
for (int i = 0; i < 4; i++)
{
t = 1; q = 0;
while (a)
{
if (a & t)
{
b++;
a -= t;
}
t *= 2;
q++;
}
}
for (int i = 0; i < 40; i++) if (b % 3 != 0) return 0;
return 1;
}
int main()
{
bool flag;
for (int a = 0; a <= N; a++)
for (int b = 0; b <= N; b++)
for (int c = 0; c <= N; c++)
for (int d = 0; d <= N; d++)
{
flag = 0;
for (int i = 0; i < a; i++) if (!f) flag = 1;
for (int i = 0; i < b; i++) if (!f) flag = 1;
for (int i = 0; i < c; i++) if (!f) flag = 1;
for (int i = 0; i < d; i++) if (!f) flag = 1;
for (int i = 0; i < a; i++)
for (int j = 0; j < b; j++) if (!f) flag = 1;
for (int i = 0; i < a; i++)
for (int j = 0; j < c; j++) if (!f) flag = 1;
for (int i = 0; i < a; i++)
for (int j = 0; j < d; j++) if (!f) flag = 1;
for (int i = 0; i < b; i++)
for (int j = 0; j < c; j++) if (!f) flag = 1;
for (int i = 0; i < b; i++)
for (int j = 0; j < d; j++) if (!f) flag = 1;
for (int i = 0; i < c; i++)
for (int j = 0; j < d; j++) if (!f) flag = 1;
f = flag;
}
/*
for (int a = 0; a <= N; a++)
for (int b = 0; b <= N; b++)
for (int c = 0; c <= N; c++)
for (int d = 0; d <= N; d++)
if (f ^ !check(a, b, c, d)) cout << "ERROR " << a << " " << b << " " << c << " " << d << endl;
*/
cout << "Preprocessing completed.\n";
while (1)
{
int x, y, z, w;
cin >> x >> y >> z >> w;
if (f) cout << "WIN\n"; else cout << "LOSE\n";
}
}
不要这种检验程序，要的是生成程序，比如限制每堆数量小于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},.....
应该可以编一种递归程序。
hujunhua 发表于 2014-1-21 17:54
不要这种检验程序，要的是生成程序，比如限制每堆数量小于100. 我手工计算，应该留给对手的局面是：
{1,2, ...
我修改了一下，另外还上传了一个编译后的可执行文件，希望能满足你的要求。（需要`N \leq 50`）
#include <iostream>
#include <cstdio>
#include <conio.h>
#define NN 50
using namespace std;
bool f;
int main()
{
int N;
bool flag;
cout << "Input N (not greater than " << NN << ") = ";
cin >> N;
for (int a = 0; a <= N; a++)
for (int b = 0; b <= N; b++)
for (int c = 0; c <= N; c++)
for (int d = 0; d <= N; d++)
{
flag = 0;
for (int i = 0; i < a; i++) if (!f) flag = 1;
for (int i = 0; i < b; i++) if (!f) flag = 1;
for (int i = 0; i < c; i++) if (!f) flag = 1;
for (int i = 0; i < d; i++) if (!f) flag = 1;
for (int i = 0; i < a; i++)
for (int j = 0; j < b; j++) if (!f) flag = 1;
for (int i = 0; i < a; i++)
for (int j = 0; j < c; j++) if (!f) flag = 1;
for (int i = 0; i < a; i++)
for (int j = 0; j < d; j++) if (!f) flag = 1;
for (int i = 0; i < b; i++)
for (int j = 0; j < c; j++) if (!f) flag = 1;
for (int i = 0; i < b; i++)
for (int j = 0; j < d; j++) if (!f) flag = 1;
for (int i = 0; i < c; i++)
for (int j = 0; j < d; j++) if (!f) flag = 1;
f = flag;
}
cout << "Preprocessing completed. I'll output the result to \"result.txt\".\n";
FILE *fout;
fout = fopen("result.txt", "w");
fprintf(fout, "The LOSE states are:\n");
for (int a = 0; a <= N; a++)
for (int b = a; b <= N; b++)
for (int c = b; c <= N; c++)
for (int d = c; d <= N; d++)
if (!f)
fprintf(fout, "(%d,%d,%d,%d)\n", a, b, c, d);
fclose(fout);
cout << "Completed. Press anykey to continue...\n";
getch();
}
hujunhua 发表于 2014-1-21 17:54
不要这种检验程序，要的是生成程序，比如限制每堆数量小于100. 我手工计算，应该留给对手的局面是：
{1,2, ...
对你的{1,2,3,4}略有疑问，因为它不出现在我的程序打印出来的结果中。我们来试试，我先。如果你感兴趣的话可以直接点评在这个贴子上。
{1,2,3,4}->{1,2,3,3}
#include <iostream>
#include <cstdio>
using namespace std;
#define NN 99
int dmap;
#define CREATE_DATA(a,b) ((a)*(NN+1)+(b))
void init_dmap()
{
int i;
for(i=1;i<=NN;i++){
dmap=CREATE_DATA(i,i);
dmap=CREATE_DATA(0,i);
}
}
int get_eq_cd(int a, int b, int& c, int& d)
{
int r=dmap;
if(r==0)return 0;
c=r/(NN+1);
d=r%(NN+1);
return 1;
}
void add_eq_data(int a, int b, int c, int d)
{
if(b>NN)return;
dmap=CREATE_DATA(c,d);
if(c>NN)return;
dmap=CREATE_DATA(b,d);
dmap=CREATE_DATA(a,d);
if(c>NN)return;
dmap=CREATE_DATA(b,d);
dmap=CREATE_DATA(a,c);
dmap=CREATE_DATA(a,b);
printf("%d,%d,%d,%d\n",a,b,c,d);
}
int main()
{
init_dmap();
for (int a = 1; a <= NN; a++)
for (int b = a; b <= NN; b++){
int c,d;
if(dmap!=0)continue;
for (c = b; c <= NN; c++){
for (d = c; d <= NN; d++)
{
int x,y;bool found=false;
if(get_eq_cd(a,c,x,y)&&x<=b&&y<=d)found=true;
if(!found&&get_eq_cd(a,d,x,y)&&x<=b&&y<=c)found=true;
if(!found&&get_eq_cd(b,c,x,y)&&x<=a&&y<=d)found=true;
if(!found&&get_eq_cd(b,d,x,y)&&x<=a&&y<=c)found=true;
if(!found&&get_eq_cd(c,d,x,y)&&x<=a&&y<=b)found=true;
if(!found){
add_eq_data(a,b,c,d);
break;
}
}
if(d<=NN)break;
}
}
return 0;
}
想错了，我这方法好想不行。我程序中映射要改多值才行
取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)
{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 \)有关，还是化成二进数么？
的确结果同二进制相关，不同的二进制位可以分开处理，结果非常简单。hujunhua出的这个题目很棒呀。而且每次允许取三堆或四堆等结论类似。