Posted on 2007-10-16 11:30
ZelluX 閱讀(554)
評論(0) 編輯 收藏 所屬分類:
Mathematics
更詳細(xì)的分析google Nim Game
http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf
發(fā)信人: flyskyf (flysky), 信區(qū): Algorithm
標(biāo) 題: 拿糖果問題
發(fā)信站: 水木社區(qū) (Mon Oct 15 19:07:51 2007), 站內(nèi)
現(xiàn)有4堆糖果.分別為1,2,4,8
甲乙兩人分別從中拿糖果
規(guī)則:
1 每人可以從某一堆中拿任意多個
2 甲乙兩人交替拿
3 誰拿到最后一個糖果或最后幾個糖果算贏.
請問誰有必勝把握?怎樣實現(xiàn)?
發(fā)信人: meeme (米鳴), 信區(qū): Algorithm
標(biāo) 題: Re: 拿糖果問題
發(fā)信站: 水木社區(qū) (Mon Oct 15 19:26:32 2007), 站內(nèi)
轉(zhuǎn)成二進(jìn)制
1 =0001
2 =0010
4 =0100
8-1 =0111 +
-----------
0222
這樣每個位上都有兩個1。
比如個位上，1和7在個位上都有一個1
對方不可能同時把這兩個1拿走。所以對方是拿不完的。
對方拿完之后，自己再拿若干個調(diào)整成這種狀態(tài)。
中間應(yīng)該有不少證明...