第三届蓝桥杯【省赛试题10】取球游戏

题目描述：

今盒子里有n个小球，A、B两人轮流从盒中取球，每个人都可以看到另一个人取了多少个，也可以看到盒中还剩下多少个，并且两人都很聪明，不会做出错误的判断。

我们约定：每个人从盒子中取出的球的数目必须是：1，3，7或者8个。轮到某一方取球时不能弃权！A先取球，然后双方交替取球，直到取完。被迫拿到最后一个球的一方为负方（输方）请编程确定出在双方都不判断失误的情况下，对于特定的初始球数，A是否能赢？程序运行时，从标准输入获得数据，其格式如下：先是一个整数n(n<100)，表示接下来有n个整数。然后是n个整数，每个占一行（整数<10000），表示初始球数。程序则输出n行，表示A的输赢情况（输为0，赢为1）。例如，用户输入：４１２1018则程序应该输出：0110注意：请仔细调试！您的程序只有能运行出正确结果的时候才有机会得分！在评卷时使用的输入数据与试卷中给出的实例数据可能是不同的。请把所有函数写在同一个文件中，调试好后，存入与【考生文件夹】下对应题号的“解答.txt”中即可。相关的工程文件不要拷入。源代码中不能能使用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的API。允许使用STL类库，但不能使用MFC或ATL等非ANSI c++标准的类库。例如，不能使用CString类型（属于MFC类库）。题目思路：

有点巴什博弈的意思，题目给出条件：

1:每次可以取1，3，7，8个

2：A先取

3：谁取到最后一个谁输

4：给定一个数，判定A能否一定赢

A一定赢的情况下，B一定输。

有3种情况，

①球数是先取的人一定赢

②先取的人一定输

③先取的人取了球以后，变成第②种情况，那么先取的人一定赢。

因此，我们可以先求出前10个（大于8个即可）数的输赢情况，我们就可以递推出后面的输赢情况。

得到核心代码：

//i表示要推出的结果 p[j]表示可以取的球数 //win[i]表示i个球 先取的人是否一定赢 if(i-p[j]>0&&win[i-p[j]]==0) win[i] = 1;
题目代码：
#include<cstdio>#include<ctime>#include<cstdlib>using namespace std;int n,a;int p[4]={1,3,7,8};//1-9个球的输赢情况 int win[105] = {0,0,1,0,1,0,1,0,1,1};//递推10-100个球的输赢情况 void Win(){	for(int i=10 ;i<=100 ;i++){		for(int j=0 ;j<4 ;j++){			if(i-p[j]>0&&win[i-p[j]]==0){				win[i] = 1;			}		}	}} int main(){	scanf("%d",&n);	Win();	while(n--){		scanf("%d",&a);		PRintf("%d/n",win[a]);		}	return 0;}