新浪今晚的C++笔试题

Question

有任意种水果，每种水果个数也是任意的，两人轮流从中取出水果，规则如下： 1）每一次应取走至少一个水果；每一次只能取走一种水果的一个或者全部 2）如果谁取到最后一个水果就胜给定水果种类N和每种水果的个数M1，M2，…Mn，算出谁取胜，编程实现之。
题目的隐含条件是两个人足够聪明，聪明到为了取胜尽可能利用规则。

以上是题目的全部内容，我在考场上简单分析了下决定用递归，但是没想明白。
我的思路和当时的代码
问题转换为谁拿倒数第二种水果的最后一个的问题，继而想到了递归

//返回0表示第一个人赢，返回1表示第二个人赢
//问题归结为，谁拿倒数第二种最后一个苹果谁输
//fruitnum水果种类，a[]对应每种水果个数
int whowins(int fruitnum,int a[])
{
    if(fruitnum==1)
        return 0;
    else
       {
       考虑水果个数的奇偶性等问题。
       }
} 

没想太明白这题，希望懂的不吝赐教

Answer 1

用Java写了一个：https://github.com/terry83299387/MyTest/blob/master/WouldIWinTheGame.java

简单说说我的思路：

1. 只有一种水果时，我方获胜

2. 当只有两种水果时，双方都只能一个一个拿，这时候谁拿最后一个取决于水果总数是奇数还是偶数。奇数就是我方胜，偶数则对方获胜

3. 当水果种类大于2种时，不太好确定到底谁获胜，因此要尝试多种可能：

3.1 先一次取完一种水果，然后递归判断拿走水果之后，对方是否无法获胜，如果对方无法获胜，那么这就是可行的方案
3.2 否则，再尝试把这种水果只拿掉一个，同样判断拿掉之后对方是否无法获胜，如果是，那么这种方案可行
3.3 如果两种方案都不可行，则换一种水果继续尝试
3.4 所有水果都尝试完了，还是无法获胜，则宣告失败

注意：这种递归方式可以保证参与游戏的双方都是足够聪明的，因为当玩家A拿掉一个或一种水果之后，轮到玩家B时他也会尽量尝试每种可能让自己获胜，只有所有可能都无法获胜时才会宣告失败。

---

经过再次认真思考，发现这题可以非常简单地计算：

1. 如果水果种类为奇数个，我方肯定能获胜

2. 当水果种类为偶数个时，如果水果总个数为奇数则我方获胜，否则对方获胜

---

抽了点时间证明了一下上面的结论：

1. m=1 必胜

2. m=2 因为任何人都不敢率先拿完一种水果，所以双方都只能一个一个地拿。所以总数为奇数胜

3. m=3 必胜

   把水果按数量的奇偶分类，只有4种可能：
   1) 3种都是奇数个
   2) 3种都是偶数个
   3) 2种奇数个1种偶数个
   4) 2种偶数个1种奇数个
   无论是哪种情况，我们都可以立即让对方进入与2相反的局面（必败的局面）：
   a) 情况1、2，随便拿掉一种水果即可
   b) 情况3、4，拿掉单独的那种，留下同为奇数或同为偶数的2种
   所以，m=3时，我方必胜
   

4. m=4 谁都不敢率先拿完一种水果，所以双方都只能一个一个地拿，也就是说，“总数-4”必须是奇数，这样才会让对方进入最终的必败局面，所以总数也必然是奇数个

5. 假设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会更清晰一些）

Answer 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)中第二种情况;

Answer 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赢。

现在，问题应该很清楚了。

Answer 4

不要在这样找笔试题了，一次就这么几个，还没过瘾就没有了，去安装个《笔试宝典》收录了网上90%的笔试题http://bishi.jisupeixun.com