简述
这是2012年蓝桥杯全国软件大赛预赛(C++本科组)第10题,实质是已知球的数量,规定取球方法,判断先取球的人的输赢。
推荐链接:《2012蓝桥杯软件大赛预赛题目汇总》
题目描述
今盒子里有n个小球,A、B两人轮流从盒中取球,每个人都可以看到另一个人取了多少个,也可以看到盒中还剩下多少个,并且两人都很聪明,不会做出错误的判断。
我们约定:
每个人从盒子中取出的球的数目必须是:1,3,7或者8个。
轮到某一方取球时不能弃权!
A先取球,然后双方交替取球,直到取完。
被迫拿到最后一个球的一方为负方(输方)
请编程确定出在双方都不判断失误的情况下,对于特定的初始球数,A是否能赢?
程序运行时,从标准输入获得数据,其格式如下:
先是一个整数n(n<100),表示接下来有n个整数。然后是n个整数,每个占一行(整数<10000),表示初始球数。
程序则输出n行,表示A的输赢情况(输为0,赢为1)。
例如,用户输入:
4
1
2
10
18
则程序应该输出:
0
1
1
0
注意:
请仔细调试!您的程序只有能运行出正确结果的时候才有机会得分!
在评卷时使用的输入数据与试卷中给出的实例数据可能是不同的。
请把所有函数写在同一个文件中,调试好后,存入与【考生文件夹】下对应题号的“解答.txt”中即可。
相关的工程文件不要拷入。
源代码中不能能使用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的API。
允许使用STL类库,但不能使用MFC或ATL等非ANSI c++标准的类库。例如,不能使用CString类型(属于MFC类库)。
分析
这是2012年蓝桥杯全国软件大赛预赛第10题,也就是最后一题,没涉及数据结构和算法,重点在问题的分析上。完成这个题目要理解一下几点:
- A和B都是想赢的;
- A不仅是A,而是先取的象征;
- A的某个状态是赢的,那这个状态的球数加上1、3、7、8后的状态一定是输的,因为B要取掉这个要加的球数去让A输;
- A的某个状态是输的,那这个状态的球数加上1、3、7、8后的状态不一定是赢的,因为B可以取任意数;
- 只需确定球数小于等于9的状态的A的输赢,后面的可以根据前面的依据上面几条的思路推断出;
下面程序把前10000个球的所有状态都计算出来了,其实可以把输入的最大数以前的所有状态求出即可。
源代码
# 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 = 0; i < n; i++) {
printf("%d\n", 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;
}
}
}
分享到:
相关推荐
蓝桥杯学习资料大全-题目参考代码-取球博弈
商战博弈---商务谈判.pptx
《伟大的博弈---华尔街金融帝国的崛起》.pdf
伟大的博弈--金融帝国的崛起.docx
伟大的博弈--金融帝国的崛起.doc
中国人工智能系列白皮书2017 - 机器博弈-智能驾驶-智能交通
信息不对称下的博弈--经济增长更需要公平正义.pptx
谈判博弈-2.docx
2季度大类资产配置报告:从基本面博弈转向资金面博弈-0424-华泰证券-22页.pdf
个人利益和社会公平的博弈--Arrow不可能性定理的逻辑分析.pdf
广告战--便车与博弈-管理资料.pdf
完全信息动态博弈-Xidian.pdf
利率债中期投资策略:一致预期下的博弈-0709-民生证券-55页.pdf
博弈-海盗分金模型.pdf
人机博弈。PDF中文版。。。。。。。。。。。。。。。。。。。。。。。。。
博弈-海盗分金模型借鉴.pdf
完全信息静态信息博弈-纳什均衡.ppt
固收年度策略:房地产篇,渐入寒冬,待政策博弈-0108-华鑫证券-11页.pdf
2019年2季度大类资产配置报告:从基本面博弈转向资金面博弈-华泰证券-20190424.pdf