取火柴游戏
|
源程序名 match.???（pas, c, cpp）
可执行文件名 match.exe
输入文件名 match.in
输出文件名 match.out |
【问题描述】
输入k及k个整数n1，n2，…，nk，表示有k堆火柴棒，第i堆火柴棒的根数为ni；接着便是你和计算机取火柴棒的对弈游戏。取的规则如下：每次可以从一堆中取走若干根火柴，也可以一堆全部取走，但不允许跨堆取，也不允许不取。
谁取走最后一根火柴为胜利者。
例如：k＝2，n1＝n2＝2，A代表你，P代表计算机，若决定A先取：
A：(2,2)→(1,2) {从一堆中取一根}
P：(1,2)→(1,1) {从另一堆中取一根}
A：(1,1)→(1,0)
P：(1,0)→ (0,0) {P胜利}
如果决定A后取：
P：(2,2)→(2,0)
A：(2,0)→ 0,0) {A胜利}
又如k＝3，n1=1，n2＝2，n3＝3，A决定后取：
P：(1,2,3)→(0,2,3)
A：(0,2,3)→(0,2,2)
A已将游戏归结为(2,2)的情况，不管P如何取A都必胜。
编一个程序，在给出初始状态之后，判断是先取必胜还是先取必败，如果是先取必胜，请输
出第一次该如何取。如果是先取必败，则输出“lose”。
【样例1】
match.in match.out
3 4 3 {表示第一次从第3堆取4个出来，必胜}
3 6 9 3 6 5 {第一次取后的状态}
【样例2】
match.in match.out
4 lose {先取必败}
15 22 19 10
【算法分析】
从问题的描述分析，可以将问题中的k堆火柴棒抽象为k个非负整数，而每取一次火柴棒可抽象为使其中的一个自然数变小，当所有的数都变为0时，游戏结束，最后—次取火柴棒的人为胜方。
当k较小，且k堆火柴棒也都较小时，可使用递推的方法来处理这个问题，具体做法是从终了状态(全零)反推出初始状态的值是先取必胜还是先取必败，因为某一状态的值可以从它的所有的取一次后的下一状态得到，如果某状态的所有的下一状态都为先取必败，则这一状态为先取必胜，否则为先取必败。
但当k和ni都很大时，上述方法很难行得通，为了解决这个问题，首先引进关于n个非负整数的奇偶状态的定义：如果把n个非负整数都化成二进制数，然后对n个二进制数按位相加(不进行进位)，若每一位相加的结果都为偶数，则称这n个非负整数的状态为偶状态，否则称之为奇状态。可以证明：任何一个偶状态在某一个数变小后一定成为奇状态，而对任何一个奇状态，必定可以通过将某一个数的值变小，使得改变后的状态成为偶状态。前一种情况是显然的，因为一个数变小以后其对应的二进制数至少有一位发生改变。这一位的改变就破坏了原来的偶状态。后一种情况可以通过构造的方法来证明，首先对任何一个奇状态，从高位向低位寻找到第一位按位加之和为奇数的二进制位，设这一位为第k位，则n个数的对应的二进制数中至少存在一个数，其第k位为1，将这个二进制数的第k位变成0，则所有二进制数的第k位上的数字之和就变成了偶数。然后再对这个数的比k位低的所有位作如下调整：如果所有二进制数在该位按位加之和为偶数，则不改变该位的值，否则改变该数在该位的值，若原来的值为0，则改为1，若原来的值为1，则改为0，这样就构造出了一个偶状态，并且被改变的那个数一定变小了，因为这个数被改变的所有二进制位中的最高位从1变成了0。
如n＝3时，三堆火柴棒的数量分别为3，6，9，则3＝(0011)2，6＝(0110)2，9＝(1001)2，最高位之和为1，其中9对应的二进制数的最高位为1，将其变为0，次高位之和也是1，9对应的二进制数的次高位为0，根据证明过程将其变为1，最后二位数字之和均为偶数，无需作任何改变，这样9＝(1001)2被变成了(0101)2=5，显然，3=(0011)2，6=(0110)2，5=(0101)2是一个偶状态。
有了前面的分析，一种贪心算法就出来了。程序中用n个包含16个元素的数组（线性表）来存放对每个非负整数对应的二进制数，如b[i, 0]存放第i个数的最低位，n个数的状态取决于它们对应的二进制数的各位数字之和的奇偶性，而各位数字之和的奇偶性只需用0和1来表示，0表示偶，1表示奇。最后的状态(全0)为偶状态，所以开始状态为偶状态时，先取必败，因为先取后局面变成了奇状态，后取方一定可将字取成偶状态，直至取光为止。反之则先取必胜。
【后记】
大家都知道国际象棋特级大师卡斯帕罗夫与IBM公司研制的“深蓝”超级计算机进行国际象棋人机大战的事吧!
有了以上算法后，我们也可以编写出这样一个游戏程序。让程序代表计算机与人做取火柴棒游戏，由人或计算机先取，要求你编的程序能够尽可能使计算机获胜。
/*NIM取子游戏*/
#define DUI 16/*限抽堆数*/
#define WEI 20/*把每一堆的数转换成2进制表示的位数限制*/
int main()
{
int k,/*接受输入的堆数*/
a[DUI][WEI],/*第一维表示堆号，第二维表示2进制各位*/
num_match[DUI+1],/*记录各堆的火柴数*/
temp=0,/*暂存*/
i,j,/*循环变量*/
flag=0,/*标志，为0表示先取失败，为1表示先取胜利*/
oldnum=0,/*取前火柴数*/
newnum=0,/*取后火柴数*/
getdui=0;/*先取数的堆号*/
printf("enter k:");
scanf("%d",&k);
for(i=1;i<=k;i++)
{
printf("enter %d number of match:",i);
scanf("%d",&num_match[i]);
j=0;
temp=num_match[i];
/*把火柴数转换成2进制*/
do
{
a[i][j]=temp%2;
temp/=2;
j++;
}while(temp!=0);
/*其余位为0*/
while(j<WEI)
{
a[i][j]=0;
j++;
}
}
/*对各位计算奇偶性*/
for(j=0;j<16;j++)
{
a[0][j]=0;/*记录同一位的和*/
for(i=1;i<=k;i++)
{
a[0][j]+=a[i][j];
}
if(a[0][j]%2==1)flag=1;/*表示游戏不平衡，可让a[0][j]记录各位的奇偶性，
避免后面重复计算*/
}
if(!flag)/*游戏平衡，则先取必败*/
{
printf("lose");
return 0;
}
else
{
for(j=WEI-1;j>=0;j--)/*从高位开始，找出现不平衡的位*/
{
if(a[0][j]%2==1)
{
for(i=k;!getdui&&i>=1;i--)/*当尚未选定先取的堆时，从最后一堆开始
找合适的堆，并记录；当已选定堆就不执行此处*/
{
if(a[i][j]==1)
{
getdui=i;
break;
}
}
/*改变该堆中不平衡的各位，0变1，1变0*/
if(a[getdui][j]==1)
{
a[getdui][j]=0;
}
else
{
a[getdui][j]=1;
}
}
}
}
/*计算新值*/
for(j=0;j<WEI;j++)
{
newnum+=a[getdui][j]*pow(2,j);
}
/*记录旧值*/
oldnum=num_match[getdui];
num_match[getdui]=newnum;
/*输出先取的火柴数，及其堆*/
printf("%d %d\n",oldnum-newnum,getdui);
/*输出取数后各堆的新数*/
printf("%d",num_match[1]);
for(i=2;i<=k;i++)
{
printf(" %d",num_match[i]);
}
system("pause");
return 0;
}
