首頁猿問新浪今晚的C++筆試題

新浪今晚的C++筆試題

JavaScript

大話西游666 2019-04-21 20:13:56

有任意種水果，每種水果個數(shù)也是任意的，兩人輪流從中取出水果，規(guī)則如下：1）每一次應(yīng)取走至少一個水果；每一次只能取走一種水果的一個或者全部2）如果誰取到最后一個水果就勝給定水果種類N和每種水果的個數(shù)M1，M2，…Mn，算出誰取勝，編程實現(xiàn)之。題目的隱含條件是兩個人足夠聰明，聰明到為了取勝盡可能利用規(guī)則。以上是題目的全部內(nèi)容，我在考場上簡單分析了下決定用遞歸，但是沒想明白。我的思路和當(dāng)時的代碼問題轉(zhuǎn)換為誰拿倒數(shù)第二種水果的最后一個的問題，繼而想到了遞歸//返回0表示第一個人贏，返回1表示第二個人贏//問題歸結(jié)為，誰拿倒數(shù)第二種最后一個蘋果誰輸//fruitnum水果種類，a[]對應(yīng)每種水果個數(shù)intwhowins(intfruitnum,inta[]){if(fruitnum==1)return0;else{考慮水果個數(shù)的奇偶性等問題。}}沒想太明白這題，希望懂的不吝賜教

查看完整描述

2 回答

慕碼人2483693

TA貢獻(xiàn)1860條經(jīng)驗獲得超9個贊

網(wǎng)上搜了下，參考這個結(jié)論，個人認(rèn)為這個結(jié)論不正確，下午面試完有時間再推理推理，有錯誤歡迎指正。這個結(jié)論提供了分析問題的思路，我先分析到3種水果，從目前的分析來看用遞歸肯定是必然的，因為三種水果問題轉(zhuǎn)換為求兩種水果問題；兩種水果問題轉(zhuǎn)換為求一種水果問題，動態(tài)規(guī)劃?假設(shè)兩個人分別為A（先取）和B（后?。?A先取水果.記水果總個數(shù)為M(即M1+M2+...+Mn).開始分情況討論:(1)有1種水果A必勝(2)有2種水果此時兩個人都不敢全部拿走一種水果,因為那樣會送對方進(jìn)入(1)的必勝態(tài),自己必敗.所以兩個人都只能一個一個拿,這樣誰拿走最后一個就由M的奇偶性決定.若M是奇數(shù)（肯定一種奇數(shù)，一種偶數(shù)）,A必勝;（先取者勝）若M是偶數(shù)（兩種都是偶數(shù)，兩種都是奇數(shù)）如果兩種都是偶數(shù)則A勝利，如果兩種都是奇數(shù)B勝利。**關(guān)于這一點(diǎn)，你可能會說我說的是錯誤的，舉例說明：假如第一種水果3個，第二種水果2個，水果總數(shù)為奇數(shù)，滿足條件，假如A先拿第一種水果，B再拿一個，A再拿一個，然后B拿全部第二種，B贏。如果你這么想，可能A還不夠聰明，如果A足夠聰明為何不拿那個偶數(shù)個的水果，這樣A就贏了。**(3)有3種水果A先取,他有足夠的主動權(quán),讓結(jié)果朝自己有利的方向走.如果M是奇數(shù),說明至少有一種水果有奇數(shù)個,全部取走這一種水果后,因此,水果總數(shù)還有偶數(shù)個，等同于有兩種水果，總個數(shù)偶數(shù)個，就轉(zhuǎn)變?yōu)椋?）中第二種情況。如果M是偶數(shù),由于N為3,因此至少有一種水果有偶數(shù)個,全部取走這一種水果后,因此,因此,水果總數(shù)還有偶數(shù)個，等同于有兩種水果，總個數(shù)偶數(shù)個同樣轉(zhuǎn)換為（2)中第二種情況;

反對回復(fù) 2019-04-21