新浪今晚的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

Written one using Java: https://github.com/terry83299387/MyTest/blob/master/WouldIWinTheGame.java

Let me briefly talk about my thoughts:

1. When there is only one kind of fruit, our side wins

2. When there are only two kinds of fruits, both parties can only take them one by one. At this time, who takes the last one depends on whether the total number of fruits is an odd number or an even number. If the number is odd, we win, if the number is even, the opponent wins

3. When there are more than 2 types of fruits, it is not easy to determine who wins, so try multiple possibilities:

3.1 First take one kind of fruit at a time, and then recursively judge whether the opponent cannot win after taking the fruit. If the opponent cannot win, then this is a feasible solution
3.2 Otherwise, try to put this Only remove one fruit, and also judge whether the opponent cannot win after taking it away. If so, then this solution is feasible
3.3 If both solutions are not feasible, change another fruit and continue trying
3.4 All fruits After trying but still unable to win, it is declared a failure

Note: This recursive method can ensure that both parties participating in the game are smart enough, because after 玩家A takes away one or a kind of fruit, he will also try his best to try every possible way when it is 玩家B’s turn. Win by yourself, and declare defeat only when all possibilities fail to win.

---

After thinking carefully again, I found that this question can be calculated very simply:

1. If there are an odd number of fruit types, we will definitely win

2. When the number of fruit types is an even number, if the total number of fruits is an odd number, our side wins, otherwise the opponent wins

---

I took some time to prove the above conclusion:

1. m=1 must win

2. m=2 Because no one dares to take the first to finish a fruit, so both parties can only take it one by one. Therefore, an odd number wins

3. m=3 must win

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

4. m=4 No one dares to finish a fruit first, so both sides can only take it one by one. In other words, the "total -4" must be an odd number, so that the other party can enter the final A losing situation, so the total number must be an odd number

5. Assume k>=3 and k is an odd number, and the above conclusion holds true when m=k and 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是偶数，所以总数也必然是奇数。
   

At this point, the above conclusion is proved to be true by induction. (Actually, the two situations 3 and 4 can be omitted, and the final conclusion can be summarized directly from 1 and 2. But adding 3 and 4 will make it clearer)

Answer 2

I searched online and found this conclusion. Personally, I think this conclusion is incorrect. I will have time to reason again after the interview in the afternoon. If there are any mistakes, please correct me. This conclusion provides an idea for analyzing the problem. I first analyzed three kinds of fruits. From the current analysis, it is definitely inevitable to use recursion, because the problem of three fruits is converted into a problem of finding two fruits; the problem of two fruits is converted into a problem of finding two fruits. A fruit problem, dynamic programming?
Suppose two people are A (take first) and B (take last), A takes the fruit first. Remember the total number of fruits is M (i.e. M1 + M2 + ... + Mn) . Start discussing by situation:
(1) There is 1 kind of fruit
A must win
(2) There are 2 kinds of fruits
At this time, neither person dares to take away all one kind of fruit, because That will send the other party into the must-win state of (1), and you will lose.
So both people can only take it one by one, so who takes the last one is determined by the parity of M.
If M is Odd numbers (definitely one odd number and one even number), A must win; (whoever gets it first wins)
If M is an even number (both are even numbers, both are odd numbers)
If both are even numbers Then A wins, if both are odd numbers, B wins.

** Regarding this point, you may say that what I said is wrong. For example:
If there are 3 fruits of the first type and 2 fruits of the second type, the total number of fruits is an odd number, and the condition is met. If A takes the first fruit first, B takes another, A takes another, then B takes all the second fruit, and B wins.
If you think so, maybe A is not smart enough. If A is smart enough, why not take the even number of fruits, so that A wins. **

(3) There are 3 kinds of fruits
A takes first, he has enough initiative to make the result go in his own favor.
If M is an odd number, it means that at least one kind of fruit has an odd number, all After taking away this kind of fruit, therefore, the total number of fruits is still an even number, which is equivalent to there being two kinds of fruits, and the total number is an even number, which changes to the second situation in (2).
If M is an even number, since N is 3, there is an even number of at least one kind of fruit. After all this kind of fruit is taken away, therefore, there is an even number of fruits in total, which is equivalent to having two kinds of fruits. An even number is also converted into the second case in (2);

Answer 3

A brief analysis, there may be logical errors.
1, take at least one. 2. You can only take one or all of one kind of fruit at a time

Suppose 1: There is only one kind of fruit and N=1, obviously P1 (person 1st) wins. Take it all in one go

If 2: N=2, it is converted to M1, and M2 can only be one of them (-1) at a time.

  比如M1=M2=1，P1输；M1=1，M2=2，P1赢。
  M1=M2=2,P1输；M1=2，M2=3，P1赢。
  发现没。M1M2差值为奇数时，P1赢，否则P1输。

If 3: N>2, P1 must ensure that the difference between the two remaining fruits is an even number. It is to ensure that the remaining fruits are all odd numbers or all even numbers.

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

Now, the problem should be clear.

Answer 4

Stop looking for written test questions like this, there are just a few at a time, and they are gone before you get the pleasure. Go install the "Written Test Collection" which contains 90% of the written test questions on the Internet http://bishi.jisupeixun.com