新浪今晚的C++笔试题-PHP中文网问答

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

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

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

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

N=3，P1赢（随便取完一种水果都可以保证都是奇数或偶数，这一轮谁先手谁赢） N=4，这一轮谁都不敢先取完一种水果，因为N=3谁先手谁赢。奇数比偶数多(总数为奇数)，P1赢。小于或等于偶数（总数为偶数），先手输 N=5，N是奇数，P1赢。

全部回复(2)

PHP中文网2017-04-17 13:02:19 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)中第二种情况;

赞 +0

添加回复

PHP中文网2017-04-17 13:02:19 1楼

简要分析一下，可能逻辑上有错漏。
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要保证留下来的两种水果差值为偶数。就是保证留下来的水果有都是奇数或都是偶数。

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