有任意种水果，每种水果个数也是任意的，两人轮流从中取出水果，规则如下： 1）每一次应取走至少一个水果；每一次只能取走一种水果的一个或者全部 2）如果谁取到最后一个水果就胜给定水果种类N和每种水果的个数M1，M2，…Mn，算出谁取胜，编程实现之。
题目的隐含条件是两个人足够聪明，聪明到为了取胜尽可能利用规则。
以上是题目的全部内容，我在考场上简单分析了下决定用递归，但是没想明白。
我的思路和当时的代码
问题转换为谁拿倒数第二种水果的最后一个的问题，继而想到了递归
//返回0表示第一个人赢，返回1表示第二个人赢
//问题归结为，谁拿倒数第二种最后一个苹果谁输
//fruitnum水果种类，a[]对应每种水果个数
int whowins(int fruitnum,int a[])
{
if(fruitnum==1)
return 0;
else
{
考虑水果个数的奇偶性等问题。
}
} 没想太明白这题，希望懂的不吝赐教
简要分析一下，可能逻辑上有错漏。
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赢。
现在，问题应该很清楚了。
不要在这样找笔试题了，一次就这么几个，还没过瘾就没有了，去安装个《笔试宝典》收录了网上90%的笔试题http://bishi.jisupeixun.com
用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会更清晰一些）
网上搜了下，参考这个结论，个人认为这个结论不正确，下午面试完有时间再推理推理，有错误欢迎指正。这个结论提供了分析问题的思路，我先分析到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)中第二种情况;