题目描述
今盒子里有n个小球，A、B两人轮流从盒中取球，每个人都可以看到另一个人取了多少个，也可以看到盒中还剩下多少个，并且两人都很聪明，不会做出错误的判断。
我们约定：
每个人从盒子中取出的球的数目必须是：1，3，7或者8个。
轮到某一方取球时不能弃权！
A先取球，然后双方交替取球，直到取完。
被迫拿到最后一个球的一方为负方（输方）
请编程确定出在双方都不判断失误的情况下，对于特定的初始球数，A是否能赢？
程序运行时，从标准输入获得数据，其格式如下：
先是一个整数n(n<100)，表示接下来有n个整数。然后是n个整数，每个占一行（整数<10000），表示初始球数。
程序则输出n行，表示A的输赢情况（输为0，赢为1）。
例如，用户输入：
４
１
２
10
18
则程序应该输出：
0
1
1
0
注意：
请仔细调试！您的程序只有能运行出正确结果的时候才有机会得分！
在评卷时使用的输入数据与试卷中给出的实例数据可能是不同的。
请把所有函数写在同一个文件中，调试好后，存入与【考生文件夹】下对应题号的“解答.txt”中即可。
相关的工程文件不要拷入。
源代码中不能能使用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的API。
允许使用STL类库，但不能使用MFC或ATL等非ANSI c++标准的类库。例如，不能使用CString类型（属于MFC类库）。
题目分析：
开始的时候就感觉是个递归的题目，并且会用到深搜，多以就开始用深搜的方式开始写，但是写的时候迷茫了，关键就是开始的思路不是很准确，做的时候感觉如果深搜走一步的话下一步就需要敌人走了，这样的话需要我走一步敌人走一步，就复杂了，并且回溯的时候不好记录曾经走过的球数的输赢情况，就果断用了一下走两步的方式，如果我先走1步，就直接写出敌人可能的走法，如果在我抓完我的之后，如果敌人能在我拿完之后给我所留下的我只能是输了的话，就说明此路不通，在遍历拿走其他数目的球，也就是再分别拿3、7、8个球，直到找出可行的方案，注意在这个过程种会把走过的路径标记一下当前球数是否可以胜利，以解决深搜是否会造成时间浪费
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <iostream>
#include <cstdlib>
using namespace std;
int map[10000];
bool fun(int x){
if(map[x]==1) return 1;
if(map[x]==-1){
if(fun(x-2)&&fun(x-4)&&fun(x-8)&&fun(x-9)) { map[x-2]=map[x-4]=map[x-8]=map[x-9]=1; return 1;} //看对方
if(fun(x-4)&&fun(x-6)&&fun(x-10)&&fun(x-11)) { map[x-4]=map[x-6]=map[x-10]=map[x-11]=1; return 1;} //看对方
if(fun(x-8)&&fun(x-10)&&( fun(x-14)||(x-14<=0) )&&( fun(x-15)||(x-15<=0) )){//看对方
map[x-8]=map[x-10]=map[x-14]=1;
if(x-15>=1) map[x-15]=1;
return 1;
}
if(fun(x-9)&&fun(x-11)&&( fun(x-15)||(x-15<=0) )&&( fun(x-16)||(x-16<=0) )) { //看对方
map[x-9]=map[x-11]=1;
if(x-15>=1) map[x-15]=1;
if(x-15>=1) map[x-15]=1;
return 1;
}
map[x]=0;
return 0;
}
if(map[x]==0) return 0;
return 0;
}
int main(){
memset(map,-1,sizeof(map));
for(int i=1;i<=11;i++)
if(i==1||i==3||i==5||i==7) map[i]=0;
else map[i]=1;
int Case;
scanf("%d",&Case);
while(Case--){
int n;
scanf("%d",&n);
cout<<fun(n)<<' ';
}
return 0;
} 结果没想到下面的代码和思路竟然这样简单，顿时考量了一下自己的智商。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
原来这道题从小到大的顺序遍历还是很好的
分析
这是2012年蓝桥杯全国软件大赛预赛第10题，也就是最后一题，没涉及数据结构和算法，重点在问题的分析上。完成这个题目要理解一下几点：
- A和B都是想赢的；
- A不仅是A，而是先取的象征；
- A的某个状态是赢的，那这个状态的球数加上1、3、7、8后的状态一定是输的，因为B要取掉这个要加的球数去让A输；
- A的某个状态是输的，那这个状态的球数加上1、3、7、8后的状态不一定是赢的，因为B可以取任意数；
- 只需确定球数小于等于9的状态的A的输赢，后面的可以根据前面的依据上面几条的思路推断出；
网友代码：
# include <stdio.h>
# define MAX 10000
# define MAXIN 100
int result[MAX] = {0, 0, 1, 0, 1, 0, 1, 0, 1, 1};
void getresult(void);
int main(void)
{
int i;
int n;
int in[MAXIN];
getresult();
scanf("%d", &n);
for(i = 0; i < n; i++) {
scanf("%d", &in[i]);
}
for(i = 1; i < n; i++) {
printf("%d ", result[in[i]]);
}
}
void getresult(void)
{
int i;
for(i = 9; i < 10000; i++) {
result[i] = 0;
if(result[i - 1] == 0) {
result[i] = 1;
} else if(result[i - 3] == 0) {
result[i] = 1;
} else if(result[i - 7] == 0) {
result[i] = 1;
} else if(result[i - 8] == 0) {
result[i] = 1;
}
}
}不过结果是一样的，这样还给了自己一点点安慰。