新浪今晚的C++笔试题

Question

有任意种水果，每种水果个数也是任意的，两人轮流从中取出水果，规则如下：1）每一次应取走至少一个水果；每一次只能取走一种水果的一个或者全部2）如果谁取到最后一个水果就胜给定水果种类N和每种水果的个数M1，M2，…Mn，算出谁取胜，编程实现之。题目的隐含条件是两个人足够聪明，聪明到为了取胜尽可能利用规则。以上是题目的全部内容，我在考场上简单分析了下决定用递归，但是没想明白。我的思路和当时的代码问题转换为谁拿倒数第二种水果的最后一个的问题，继而想到了递归//返回0表示第一个人赢，返回1表示第二个人赢//问题归结为，谁拿倒数第二种最后一个苹果谁输//fruitnum水果种类，a[]对应每种水果个数intwhowins(intfruitnum,inta[]){if(fruitnum==1)return0;else{考虑水果个数的奇偶性等问题。}}没想太明白这题，希望懂的不吝赐教

Answer 1

网上搜了下，参考这个结论，个人认为这个结论不正确，下午面试完有时间再推理推理，有错误欢迎指正。这个结论提供了分析问题的思路，我先分析到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)中第二种情况;