问题描述
有任意种水果，每种水果个数也是任意的，两人轮流从中取出水果，规则如下： 1）每一次应取走至少一个水果；每一次只能取走一种水果的一个或者全部 2）如果谁取到最后一个水果就胜给定水果种类N和每种水果的个数M1，M2，…Mn，算出谁取胜，编程实现之。题目的隐含条件是两个人足够聪明，聪明到为了取胜尽可能利用规则。
以上是题目的全部内容，我在考场上简单分析了下决定用递归，但是没想明白。我的思路和当时的代码问题转换为谁拿倒数第二种水果的最后一个的问题，继而想到了递归
//返回0表示第一个人赢，返回1表示第二个人赢//问题归结为，谁拿倒数第二种最后一个苹果谁输//fruitnum水果种类，a[]对应每种水果个数int whowins(int fruitnum,int a[]){ if(fruitnum==1)return 0; else { 考虑水果个数的奇偶性等问题。 }}
没想太明白这题，希望懂的不吝赐教
问题解答
回答1：用Java写了一个：https://github.com/terry83299387/MyTest/blob/master/WouldIWinTheGame.java
简单说说我的思路：
只有一种水果时，我方获胜
当只有两种水果时，双方都只能一个一个拿，这时候谁拿最后一个取决于水果总数是奇数还是偶数。奇数就是我方胜，偶数则对方获胜
当水果种类大于2种时，不太好确定到底谁获胜，因此要尝试多种可能：
3.1 先一次取完一种水果，然后递归判断拿走水果之后，对方是否无法获胜，如果对方无法获胜，那么这就是可行的方案3.2 否则，再尝试把这种水果只拿掉一个，同样判断拿掉之后对方是否无法获胜，如果是，那么这种方案可行3.3 如果两种方案都不可行，则换一种水果继续尝试3.4 所有水果都尝试完了，还是无法获胜，则宣告失败
注意：这种递归方式可以保证参与游戏的双方都是足够聪明的，因为当玩家A拿掉一个或一种水果之后，轮到玩家B时他也会尽量尝试每种可能让自己获胜，只有所有可能都无法获胜时才会宣告失败。
经过再次认真思考，发现这题可以非常简单地计算：
如果水果种类为奇数个，我方肯定能获胜
当水果种类为偶数个时，如果水果总个数为奇数则我方获胜，否则对方获胜
抽了点时间证明了一下上面的结论：m=1 必胜
m=2 因为任何人都不敢率先拿完一种水果，所以双方都只能一个一个地拿。所以总数为奇数胜
m=3 必胜
把水果按数量的奇偶分类，只有4种可能：1) 3种都是奇数个2) 3种都是偶数个3) 2种奇数个1种偶数个4) 2种偶数个1种奇数个无论是哪种情况，我们都可以立即让对方进入与2相反的局面（必败的局面）：a) 情况1、2，随便拿掉一种水果即可b) 情况3、4，拿掉单独的那种，留下同为奇数或同为偶数的2种所以，m=3时，我方必胜
m=4 谁都不敢率先拿完一种水果，所以双方都只能一个一个地拿，也就是说，“总数-4”必须是奇数，这样才会让对方进入最终的必败局面，所以总数也必然是奇数个
假设k>=3且k为奇数，且m=k和m=k+1时有上面的结论成立。
5.1 当m=k+2时（此时m为奇数），把水果按数量的奇偶分类，只有3种情况：1) 都为奇数或都为偶数。此时只需随便拿掉1种，就会让对方剩下的水果总数量为偶数个2) 奇数种奇数的水果、偶数种偶数的水果。此时只要拿掉一种数量为奇数的水果即可3) 偶数种奇数的水果、奇数种偶数的水果。此时只要拿掉一种数量为偶数的水果即可所以，当m为>3的奇数时，上述结论成立。（实际上情况1)为情况2)和3)的特例）5.2 当m=k+3时（此时m为偶数）由于m=k+2时是必胜的，所以这种情况下谁都不敢率先拿掉一种水果所以双方都只能一个一个地拿也就是说，“总数-m”必须是奇数，这样才能让对方进入这种局面。由于m是偶数，所以总数也必然是奇数。
至此，用归纳法证明了上面的结论是成立的。（实际上3和4两种情况可以不要，直接由1、2来归纳出最终的结论。但加上3和4会更清晰一些）
回答2：网上搜了下，参考这个结论，个人认为这个结论不正确，下午面试完有时间再推理推理，有错误欢迎指正。这个结论提供了分析问题的思路，我先分析到3种水果，从目前的分析来看用递归肯定是必然的，因为三种水果问题转换为求两种水果问题；两种水果问题转换为求一种水果问题，动态规划?假设两个人分别为 A（先取） 和 B（后取）, A 先取水果. 记水果总个数为 M (即 M1 + M2 + ... + Mn). 开始分情况讨论:(1) 有 1 种水果A 必胜(2) 有 2 种水果此时两个人都不敢全部拿走一种水果, 因为那样会送对方进入(1)的必胜态, 自己必败.所以两个人都只能一个一个拿, 这样谁拿走最后一个就由 M 的奇偶性决定.若 M 是奇数（肯定一种奇数，一种偶数）, A 必胜;（先取者胜）若 M 是偶数（两种都是偶数，两种都是奇数）如果两种都是偶数则A胜利，如果两种都是奇数B胜利。
**关于这一点，你可能会说我说的是错误的，举例说明：假如第一种水果3个，第二种水果2个，水果总数为奇数，满足条件，假如A先拿第一种水果，B再拿一个，A再拿一个，然后B拿全部第二种，B赢。如果你这么想，可能A还不够聪明，如果A足够聪明为何不拿那个偶数个的水果，这样A就赢了。**
(3) 有 3 种水果A先取, 他有足够的主动权, 让结果朝自己有利的方向走.如果 M 是奇数, 说明至少有一种水果有奇数个, 全部取走这一种水果后, 因此,水果总数还有偶数个，等同于有两种水果，总个数偶数个，就转变为（2）中第二种情况。如果 M 是偶数, 由于 N 为 3, 因此至少有一种水果有偶数个, 全部取走这一种水果后, 因此,因此,水果总数还有偶数个，等同于有两种水果，总个数偶数个同样转换为（2)中第二种情况;
回答3：简要分析一下，可能逻辑上有错漏。1，至少取一个。2，每一次只能取一种水果的一个或者全部
假如1：只有一种水果既N=1，显然是P1（person 1st）赢。一次拿完
假如2：N=2，就转化为M1，M2每次只能其中一个（-1）。
比如M1=M2=1，P1输；M1=1，M2=2，P1赢。 M1=M2=2,P1输；M1=2，M2=3，P1赢。 发现没。M1M2差值为奇数时，P1赢，否则P1输。
假如3：N>2，P1要保证留下来的两种水果差值为偶数。就是保证留下来的水果有都是奇数或都是偶数。
N=3，P1赢（随便取完一种水果都可以保证都是奇数或偶数，这一轮谁先手谁赢） N=4，这一轮谁都不敢先取完一种水果，因为N=3谁先手谁赢。 奇数比偶数多(总数为奇数)，P1赢。小于或等于偶数（总数为偶数），先手输 N=5，N是奇数，P1赢。
现在，问题应该很清楚了。
回答4：不要在这样找笔试题了，一次就这么几个，还没过瘾就没有了，去安装个《笔试宝典》收录了网上90%的笔试题http://bishi.jisupeixun.com
