题目
有任意种水果, 每种水果个数也是任意的, 两人轮流从中取出水果, 规则如下:
1) 每一次应取走至少一个水果; 每一次只能取走一种水果的一个或者全部. 2) 如果谁取到最后一个水果就胜.给定水果种类 N 和每种水果的个数 M1, M2, …, Mn, 算出谁取胜.
二、解题
看到这个题目的时候，我整个人懵逼了，啥，到底是叫我做什么？一脸懵逼，然后再看题目，又重新看题目，才发现，题目有个隐含的条件，就是 这两个人足够聪明，充分利用了规则。 可是单单凭借这一点，还是不知道该从何下手，其实这题是 必胜策略题，可以通过用递推的方式找一下规律解决该题。
在递推之前，我们先来看看题目中一共给出了什么条件：
1.N 种不同的水果 2.每种水果的个数分别为：M1, M2, …, Mn， 3.有两个人，轮流取水果，每一次应取走至少一个水果; 每一次只能取走一种水果的一个或者全部 4.谁取到最后一个水果就胜那好，根据上面的分析， 我们先假设两个人分别为 A 和 B ，A 先取水果，水果的总个数为 M ,即 M = M1 + M2 + M3 + … + Mn，
(1)N = 1（只有一种水果）
A 先拿，因为知道水果的种类，所以 A 不需要考虑水果有多少个，他只要第一次拿的时候，拿完这一种水果就可以获胜了。
结论：N = 1 ，A 必胜
(2)N = 2 (有两种水果)
此时两个人都不敢直接拿走一种水果, 因为那样会送对方进入(1)的必胜局中, 自己必败.所以 A 和 B 都只能一个一个的拿， 这样谁拿走最后一个就由 M（水果的总个数） 的奇偶性决定。也就是说 ，M 是奇数，A 必胜，M 是偶数，B 必胜
当然我在想这个例子的时候，不小心进入了一个误区，假如第一种水果 3 个，第二种水果 2 个，水果总数为奇数，满足条件，假如 A 先拿第一种水果，B 再拿一个第一种水果，A 再拿一个，然后 B 拿全部第二种，B 赢。可是 A 是足够聪明的，A 拿了第一种水果，B 跟着拿，此时 A 肯定不会接着拿第一种水果的，因为这样自己必败，所以他肯定会选择拿第二种水果，这样就能必胜了。所以还是 N = 2 的时候，水果的总数为奇数，先拿必胜，如果水果的总数为偶数，先拿必败
结论：N = 2 ，M 是奇数, A 必胜; 否则 A 必败
(3)N = 3 (有三种水果)
当水果种类大于 2 种时，不太好确定到底谁获胜，需要根据各种水果数量的奇偶数来判断，因此先按水按数量的奇偶分类，有 4 种可能：
- 3 种水果的个数分别都是奇数个
- 3 种水果的个数分别都是偶数个
- 其中 2 种水果的个数是奇数个，其中 1 种水果的个数是偶数个
- 其中 2 种水果的个数是偶数个，其中 1 种水果的个数是奇数个
无论上面是哪种情况，A 都可以立即让 B 进入与 (2) 相反的局面（必败的局面）,比如：
- 3 种水果的个数分别都是奇数个: A 随便拿掉一种水果，剩余的水果总数为偶数（奇数 + 奇数 = 偶数），剩余两种水果，进入了（2）的局面，水果总数为偶数，先拿必败，所以 B 必败，A必胜
- 3 种水果的个数分别都是偶数个: 跟上面是一样的，A 随便拿掉一种水果，剩余的水果总数为偶数（偶数 + 偶数 = 偶数），剩余两种水果，进入了（2）的局面，水果总数为偶数，先拿必败，所以 B 必败，A必胜
- 其中 2 种水果的个数是奇数个，其中 1 种水果的个数是偶数个: A 拿走偶数个的水果的全部，也会进入（2）的局面且水果总数为偶数，A 必胜
- 其中 2 种水果的个数是偶数个，其中 1 种水果的个数是奇数个： A 拿走奇数个的水果的全部，也会进入（2）的局面且水果总数为偶数，A 必胜
结论：N = 3 ，A 必胜
(4)N = 4 (有四种水果)
A 先取, 他肯定不会全部取走一种, 因为会送 B 进入(3)的必胜态, A 就必败.
因此 A 只能取一个
- 若 A 取走一个，变成了三种水果，就是变成 (3) 了, 说明 4 种水果都只有一个(否则 A 足够聪明，可以避免这种情况) 即 M 为偶数 4 ， A 必败
- 若 A 取完这一个还剩 4 种水果, 那 B 同上分析也只敢取一个，依次类推, 谁最后面对变成 (3) 的情况就必败了.
也就是说 M - 4 必须是奇数，这样 A 才会让 B 进入最终的必败局面，所以胜负由 M - 4 的奇偶性决定, 也就是说胜负由 M 的奇偶性决定
结论：N = 4 ，M 是奇数, A 必胜; 否则 A 必败
通过上面的递推，我们基本可以看到规律了：
- N 为奇数，A 必胜
- N 为偶数，如果 M 为奇数，A 必胜；如果 M 为偶数，A 必败
三、编程
最后我们通过编程解决 GitHub 地址：
package com.liangdianshui;import java.util.Scanner;/** ** 有任意种水果，每种水果个数也是任意的，两人轮流从中取出水果，规则如下： * 1）每一次应取走至少一个水果；每一次只能取走一种水果的一个或者全部 * 2）如果谁取到最后一个水果就胜 * 给定水果种类N和每种水果的个数M1，M2，…Mn，算出谁取胜。 * （题目的隐含条件是两个人足够聪明，聪明到为了取胜尽可能利用规则） *
* * @author liangdianshui * */public class TakeTheFruit { private static final String EXIT = "q"; public static void main(String[] args) throws Exception { Scanner scanner = new Scanner(System.in); String input; int[] fruitNums; do { System.out.println("假设 A 和 B 两个人，A 先取水果"); System.out.println("请输入每种水果的个数（空格或回车分隔）："); System.out.println("输入 Q 或 q 退出"); if (EXIT.equalsIgnoreCase(input = scanner.nextLine())) { System.out.println("Exit"); break; } input = input.trim(); if (input.length() != 0) { fruitNums = initFruitNums(input); boolean isWin = takeTheFruitGame(fruitNums, fruitNums.length); if(isWin){ System.out.println("A 赢"); }else{ System.out.println("B 赢"); } System.out.println("--------------------------------------------"); } } while (true); } /** * 初始化每种水果的个数 * * @param input * @return */ private static int[] initFruitNums(String input) { String[] nums = input.split("\\s+"); int[] fruitNums = new int[nums.length]; int num; for (int i = 0; i < nums.length; i++) { num = Integer.parseInt(nums[i]); if (num <= 0) { throw new IllegalArgumentException("水果数量不能为 0 或负数：" + num); } fruitNums[i] = num; } return fruitNums; } /** * 递归法 * * @param fruitNums * @param numOfTypes * @return */ private static boolean takeTheFruitGame(int[] fruitNums, int numOfTypes) { //当水果种类为1的时候，必胜 if (numOfTypes == 1) { return true; } // 当水果种类为2的时候 if (numOfTypes == 2) { return sumOfTwoFruitNums(fruitNums) % 2 == 1; } // 当水果种类大于等于3的时候 int num; for (int i = 0; i < fruitNums.length; i++) { num = fruitNums[i]; if (num == 0) continue; fruitNums[i] = 0; if (!takeTheFruitGame(fruitNums, numOfTypes - 1)) { fruitNums[i] = num; return true; } if (num > 1) { fruitNums[i] = num - 1; if (!takeTheFruitGame(fruitNums, numOfTypes)) { fruitNums[i] = num; return true; } } fruitNums[i] = num; } return false; } /** ** 通过结论直接输出结果 * N 为奇数，A 必胜 * N 为偶数，如果 M 为奇数，A 必胜；如果 M 为偶数，A 必败 *
* @param fruitNums * @return */ private static boolean takeTheFruitGame2(int[] fruitNums) { if (fruitNums.length % 2 == 1) { return true; } return sumOfFruitNums(fruitNums) % 2 == 1; } private static int sumOfTwoFruitNums(int[] fruitNums) { int num1 = 0; int num2 = 0; for (int num : fruitNums) { if (num > 0) { if (num1 == 0) { num1 = num; } else { num2 = num; break; } } } return num1 + num2; } private static int sumOfFruitNums(int[] fruitNums) { int sum = 0; for (int num : fruitNums) { sum += num; } return sum; }}