巧取偶数 求解思路
桌上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开始，具体代码如下：
#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手算错了，输出改为甲当前该抓的个数：
#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;}