取球博弈

两个人玩取球的游戏。
一共有N个球，每人轮流取球，每次可取集合{n1,n2,n3}中的任何一个数目。
如果无法继续取球，则游戏结束。
此时，持有奇数个球的一方获胜。
如果两人都是奇数，则为平局。

假设双方都采用最聪明的取法，
第一个取球的人一定能赢吗？
试编程解决这个问题。
输入格式：
第一行3个正整数n1 n2 n3，空格分开，表示每次可取的数目 (0<n1,n2,n3<100)
第二行5个正整数x1 x2 … x5，空格分开，表示5局的初始球数(0<xi<1000)

输出格式：
一行5个字符，空格分开。分别表示每局先取球的人能否获胜。
能获胜则输出+，
次之，如有办法逼平对手，输出0，
无论如何都会输，则输出-

例如，输入：
1 2 3
1 2 3 4 5
程序应该输出：
+ 0 + 0 -

再例如，输入：
1 4 5
10 11 12 13 15
程序应该输出：
0 - 0 + +

再例如，输入：
2 3 5
7 8 9 10 11
程序应该输出：
+ 0 0 0 0

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 3000ms

在完成这个题之前我们先来看另外一道题

今盒子里有 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

这是12年蓝桥杯预赛的题目，很明显原题是由这道题拓展出的，首先来分析下这个题，盒子里有n个球，A先取球
1. n为1，A输
2. n为2，A拿一个，A赢
3. n为3，A输
4. 。。。。。。
递归思路慢慢浮现出来，轮到A取球，如果盒子内没有球，则说明最后一个球是B取走，A赢；如果盒子里面的球在A取走1，3，7或者8个后B取球没赢，则说明A赢了，逐步往下递归即可。
下面附上代码

public class ProgramDesigning9 {
public static boolean pick(int n) {
if (n == 0 || n >= 1 && !pick(n - 1) || n >= 3 && !pick(n - 3) || 
                n >= 7 && !pick(n - 7) || n >= 8 && !pick(n - 8)) {
return true; 
            }
return false;
    }

public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] x = new int[n];
for (int i = 0; i < x.length; i++) {
            x[i] = input.nextInt();
        }
        input.close();
for (int i = 0; i < x.length; i++) {
            System.out.println(pick(x[i]));
        }
    }
}

不过这种解法有个问题，就是耗时，当球数目很多时，会超时。优化详见「蓝桥杯——博弈论问题」，这里我不做过多阐述了，点击查看原博客就好，核心优化思想就是加一个数组来存储中间结果。
回到原题来，用类似的思想可以作出解法（代码中写了解释就不过多说明）

public class ProgramDesigning9 {
// 每次可以取球的个数
public static int[] pick = new int[3];
// 5局的初始球数
public static int[] init = new int[5];
// 存储球数为数组索引时的取球输赢结果
public static int[] result = new int[1000];
// 输赢情况
public static char[] sign = { '-', '0', '0', '+' };

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
// 初始化n数组
for (int i = 0; i < 3; i++) {
            pick[i] = scan.nextInt();
        }

// 初始化init数组
for (int i = 0; i < 5; i++) {
            init[i] = scan.nextInt();
        }
        scan.close();

// 找出可以取球的最小值，如果初始球数小于这个值则直接平局（两人都无法取球）
int Min = Math.min(pick[0], Math.min(pick[1], pick[2]));
for (int i = 0; i < Min; i++) {
            result[i] = 2;
        }

// 从Min开始，向end数组填值
for (int i = Min; i < result.length; i++) {
int temp = 0;
for (int j = 0; j < 3; j++) {
// 判断球的数目是否小于pick[j]，小于则继续pick[j+1]
if (i - pick[j] < 0) {
continue;
                }
// 自己拿了球，对方必定赢的情况
else if (result[i - pick[j]] == 3) {
// 自己拿了奇数个球，则平局
if (pick[j] % 2 != 0)
                        temp = 1 > temp ? 1 : temp;
                }
// 自己拿了球，对方必定输的情况
else if (result[i - pick[j]] == 0) {
// 自己拿了偶数个球，自己必定输
if (pick[j] % 2 == 0)
                        temp = 3;
// 拿了奇数个球，平局
else
                        temp = 2 > temp ? 2 : temp;
                } 
// 自己拿了球后，对方和我们平局的情况
else if (result[i - pick[j]] == 2) {
// 如果自己拿的偶数个，可能平局
if (pick[j] % 2 == 0)
                        temp = 2 > temp ? 2 : temp;
// 如果自己拿的奇数个，自己必定赢
else
                        temp = 3;
                }
// 自己拿了球后，对方和我们平局
else if (result[i - pick[j]] == 1) {
if (pick[j] % 2 == 0)
                        temp = 1 > temp ? 1 : temp;
                }
            }
            result[i] = temp;
        }
for (int i = 0; i < 5; i++) {
            System.out.print(sign[result[init[i]]] + " ");
        }
    }
}

这个程序是参考网友写的，有一点不是很懂，就是为什么要设置两种平局的情况，有朋友如果有见解欢迎评论

秒客网

第七届蓝桥杯个人赛省赛（Java B组）第九题

取球博弈

相关文章