您当前的位置: 桌上25个棋子，游戏双方轮流取子，每人每次可取1~3颗，直到取完。取到偶数方的为获胜者
以上是题目，请问有什么取子策略始终保证某一方始终为胜者吗？
------解决方案--------------------
以前看过一个类似的题目：那个是要求取到最后一个字。昨天试了试，取胜的总的策略就是：要使你拿字后剩下的必须是偶数。例如：
如果你首先拿：就拿奇数，那么桌子上剩余就是偶数。这时候看对方拿，如果他拿奇数，那么你也奇数。剩余还是偶数；如果他偶数，你也就偶数，剩余的还是偶数。一直下去，必定是第一个拿的赢。昨天为了做这题目，拿了25颗围棋字在寝室和同学抓了半天，冲这一点，lz要多给点分啊。。^__^
------解决方案--------------------
原理：状态回溯（从最简单状态递推到复杂状态）
问题描述：可以用一个三元组完整的描述当前状态，定义三元组
{剩余石子个数，甲的状态，乙的状态}。下面看看需要满足什么约束条件以及描述哪些状态。
剩余石子+甲的石子+乙的石子=25(奇数)；
当前状态，甲先抓，乙后抓 或 乙先甲后；
显然，当剩余石子是偶数时，（甲+乙）的石子应该是奇数；反之应是偶数。
由此，可定义具体的状态集合：
1） 剩余偶数个石子 {11, 00}, {10, 01}, {00, 11}, {01, 10}
说明：“偶”表示当前剩余石子数为偶数，第一个状态{11, 00}中，‘11’为甲的状态，高位‘1’表示当前该甲先抓，低位‘1’表示当前甲所拥有的石子数为奇数，‘00’为乙
的当前状态，高位‘0’表示乙后抓，低位‘0’表示乙有偶数个石子。
同理，剩余奇数个石子时，当前状态集合为
2） 剩余奇数个石子 {00, 10}, {01, 11}, {10, 00}, {11, 01}
所以，以上两个状态集合可以描述问题的所有状态
下面，考虑一种简单状态，即： 剩余石子数较少+甲必赢
若当前剩余石子数为2或3时，先抓者赢，对于甲来说，就是(如下)状态：
2 {11, 00}, {10, 01}
3 {10, 00}, {11, 01}
不难发现，若当前剩余石子数为4时，
若甲的石子数为奇数，而当前该乙抓，则甲有必赢策略。原因如下：
乙抓3个，甲抓1，甲赢；
乙抓2个，甲抓1，甲赢；
乙抓1个，甲抓3，甲赢。
若甲的石子数为奇数，而该甲抓，则甲亦必赢，因为甲可以直接抓三个。
用三元状态组描述剩余4个石子时，甲的必赢状态为：
4 {01, 10}, {11, 00}
因为一次最多抓三个，考虑当剩余5个石子时，若甲要必赢，必须保证抓完石子后的状态落在2、3、4的必赢状态中，这意味着可以从2、3、4的必赢状态反推至剩余5个石子的情况
。
状态迁移示例如下：
设当前状态是 5 {10, 00}，即 该甲抓且甲的石子数为偶数。若甲抓1个石子，则状态迁移至 4 {01, 10}，在4的必赢态中。显然 5 {10, 00} 也是甲的必赢状态，反之，5 {00,
10} 是甲的必输状态，因为这是乙的必赢状态。综上所述，其他状态以此类推。
所以，使用递推的方法，通过三个初始的必赢状态(即，当前剩余石子数为2, 3, 4时)，可以推至有更多石子时的必赢状态。
下面程序的初始状态是从6, 7, 8开始，具体代码如下：
- C/C++ code
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
const int se[4][2]= {{3,0}, {2,1}, {0,3}, {1,2}};
const int so[4][2]= {{2,0}, {3,1}, {0,2}, {1,3}};
const int *sp;
typedef struct
{
int num;
const int *spar[2];
} state;
state st0= {num:6, spar:{&se[0][0], &se[3][0]}};
state st1= {num:7, spar:{&so[0][0], &so[1][0]}};
state st2= {num:8, spar:{&se[0][0], &se[1][0]}};
int ni=3, min_index=0;// 初始状态解，最前状态解索引
state st[3]= {st0, st1, st2};// 递推的初始解
const int * st_tmp[2];// 临时存储获得解
int i, j, k, m, n, p, find=0, count=25;
for (i=9; i<=count; i++)
{
if ( (i%2)==0 )
sp=&se[0][0];
else
sp=&so[0][0];
for (p=0, m=0; p<2; p++, sp=sp+2)
{
find=0;
for (k=0; k<3; k++)
{
for (n=0; n<2; n++)
{
if ( ( (*(sp+1) ^ 2)==*(st[k].spar[n]+1) )
&& ( (*sp & 2) != (*(st[k].spar[n]) & 2) )
&& ( ((*(st[k].spar[n])+*sp+(i-st[k].num))%2)==0 ) )
{
st_tmp[m]=sp;
find=1;
m++;
}
}
}
if (find==0)
{
st_tmp[m]=(sp+4);
m=m+1;
}
}
printf("state: %d {%d %d}, {%d %d}\n", i, st_tmp[0][0], st_tmp[0][1], st_tmp[1][0], st_tmp[1][1]);
st[min_index%3].num=i;
st[min_index%3].spar[0]=st_tmp[0];
st[min_index%3].spar[1]=st_tmp[1];
min_index++;
}
return 0;
}
------解决方案--------------------
20L的输出结果错了，因为初始状态值st0手算错了，输出改为甲当前该抓的个数：
- C/C++ code
#include <stdio.h>
#include <stdlib.h>
typedef struct { // 状态描述三元组
int num;
const int * spar[2];
} state;
int main(void)
{
const int se[4][2] = { {3,0}, {2,1}, {0,3}, {1,2} }; // 偶数石子时状态集，前2个均为甲的优先状态
const int so[4][2] = { {2,0}, {3,1}, {0,2}, {1,3} }; // 奇数石子时状态集
const int *sp = NULL; // 当前可能解
state st0 = { 1, {&so[2][0], &so[1][0]} }; // 初始状态解 1、2、3
state st1 = { 2, {&se[0][0], &se[1][0]} };
state st2 = { 3, {&so[0][0], &so[1][0]} };
int min_index = 0; // 最前状态解索引
state st[3] = {st0, st1, st2}; // 初始状态解集，递推的初始解
const int * st_tmp[2]= {0}; // 临时存储获得解（两个状态）
int i, j, k, m, n, find=0, fetch[2]={0}, count=25;
for (i=4; i<=count; i++) // 从4开始，直到25
{
if ( (i%2)==0 ) // 得到奇/偶状态集合
sp=&se[0][0];
else
sp=&so[0][0];
for (j=0, m=0; j<2; j++, sp=sp+2) // 验证可能解，2个优先状态
{
find=0;
for (k=0; k<3; k++) // 3 个初始状态解集合
{
for (n=0; n<2; n++) // 每个初始解包含2个状态解
{
if ( ( find == 0 ) // 禁止同一可能解匹配两次,导致数组越界
&& ( (*(sp+1) ^ 2) == *(st[k].spar[n]+1) ) // 回溯规则，匹配可能的优先解
&& ( (*sp & 2) != (*(st[k].spar[n]) & 2) )
&& ( ((*(st[k].spar[n])+*sp+(i-st[k].num))&1) == 0 ) )
{
st_tmp[m] = sp; // 记录通过验证的解
fetch[m] = i-st[k].num; // 优先状态解的取子数
find = 1;
m++; // st_tmp 准备记录第二个状态解
}
}
}
if ( find==0 ) // 若优先解未通过验证，则取镜像解
{
st_tmp[m] = (sp+4);
fetch[m] = 0;
m++;
}
}
if ((fetch[0] && fetch[1]) | (i==count))
printf("state: %d %d(%d), %d(%d)\n", i, fetch[0], (st_tmp[0][0]&1), fetch[1], (st_tmp[1][0]&1));
else
printf("state: %d %d\n", i, fetch[0]+fetch[1]);
st[min_index].num = i; // 更新初始状态解
st[min_index].spar[0] = st_tmp[0];
st[min_index].spar[1] = st_tmp[1];
if (++min_index > 2) min_index = 0;
}
return 0;
}