新浪今晚的C++笔试题

Question

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

巴扎黑 · Answer

用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會更清晰一些）

PHP中文网 · Answer

網路搜了下，參考這個結論，個人認為這個結論不正確，下午面試完有時間再推理推理，有錯誤歡迎指正。這個結論提供了分析問題的思路，我先分析到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)中第二種情況;

PHP中文网 · Answer

簡單分析一下，可能邏輯上有錯漏。
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

不要在這樣找筆試題了，一次就這麼幾個，還沒過癮就沒有了，去安裝個《筆試寶典》收錄了網上90%的筆試題http://bishi.jisupeixun.com