當前位置:編程學習大全網 - 編程語言 - 撿火柴堆的問題?

撿火柴堆的問題?

撿火柴問題的終極解決方案;

挑配遊戲,無論是3、5、7、3、4、5,甚至是5、6、7、8這4堆,都可以通過以下方式解決。

拿火柴問題的勝負關鍵在於判斷火柴數量是否處於穩定狀態,誰拿火柴能獲得穩定狀態,誰拿火柴破壞穩定狀態就輸了。

判斷穩態,需要用數字的二進制表示。記住使用十進制數的二進制表示:

1=0001

2=0010

3=0011

4=0100

5=0101

6=0110

7=0111

8=1000

9=1001

在上面的二進制中,單位中的1代表1,十分之壹的1代表2,百分之壹的1代表4,千分之壹的1代表8。例如,以千為單位的1001代表8,以單位為單位的1代表1,所以1001 = 8+1 = 9;同理,0111 = 4+2+1 = 7。

穩態的判斷:將幾堆火柴的二進制表示壹壹對齊。如果每個數字中1的個數,如10,100,1000,都是偶數(0,2,4,...),本組匹配數構成壹個穩態。只要任意壹位數字中的1的個數不是偶數,這個組的匹配數就是不穩定的。

問題1。假設有三堆火柴,每堆有三根、五根和七根,兩個人可以壹次從任意壹堆或全部中拿1,最後壹根火柴為勝者。

狀態3、5和7這三個數的二進制表示如下:

3=0011

5=0101

7=0111

這組數字有三個1,十位數有兩個1,百位數有兩個1,所以這組數字不穩定。在不穩定狀態下,只要通過拿火柴把不穩定狀態轉化為穩定狀態,先拿火柴的人就能贏。

在3、5、7的不穩定狀態下,有三種方法可以將匹配數變為穩定狀態,即從第壹堆取1變為2、5、7,或者從第二堆取1變為3、4、7,或者從第三堆取1變為3、5、6。這三種狀態是穩定狀態,例如:

2=0010

5=0101

7=0111

百位中1的個數是偶數2,穩定。

3=0011

4=0100

7=0111

百位中1的個數是偶數2,穩定。

3=0011

5=0101

6=0110

百位中1的個數是偶數2,穩定。

面對上述穩定狀態,後面拿火柴的人會破壞穩定狀態,變成不穩定狀態,必然會輸。

假設最後壹個取牌者從第三堆拿走兩塊,匹配堆數變成2、5、5,變成不穩定狀態。

2=0010

5=0101

5=0101

十位數只有1 1,不穩定。

這時候唯壹正確的取第壹的方法就是取第壹堆,匹配數變成:0,5,5,轉到穩定狀態。

0=0000

5=0101

5=0101

單位裏有兩個1,第十個0個1,第壹百個2個1,穩定。

總之,第壹個接受者只要把後面遇到的不穩定狀態全部轉化為穩定狀態,他就贏了。

問題2:假設有三堆火柴,每堆有三根、四根、五根火柴,兩個人可以壹次從任意壹堆或全部中取1,最後壹根火柴為勝者。

狀態3、4和5這三個數的二進制表示如下:

3=0011

4=0100

5=0101

壹位數有兩個1,十位數只有1,百位有兩個1,所以這組數字是不穩定的。第壹個拿的人只有壹個辦法:從第壹堆裏拿兩張火柴,把這組數字變成1,4,5的穩定狀態,就可以贏了。

1=0001

4=0100

5=0101

單位中有兩個1,十位中有零個1,百位中有兩個1,所以處於穩定狀態。

問題3:假設有4堆火柴,每堆有3、4、5、6根火柴,兩個人可以壹次從任意壹堆或全部中拿1,最後壹次拿到火柴的人獲勝。

狀態3、4、5和6的四個數字的二進制表示如下:

3=0011

4=0100

5=0101

6=0110

這組數字在單位中有兩個1,十位數中有兩個1,百位數中有三個1,這組數字是不穩定的。第壹個接受者,只要在百位中盡量減少1這個數,就可以把這組數變成壹個穩定的狀態。這個數有三種取法,即把四堆火柴的個數換算成:3,0,5,6,或3,4,1,6或3,4,5,2。

問題4:假設有4堆火柴,每堆有6、7、8、9根火柴,兩個人可以壹次從任意壹堆或全部中拿1,最後壹次拿到火柴的人獲勝。

狀態6、7、8和9的四個數字的二進制表示如下:

6=0110

7=0111

8=1000

9=1001

這組數字在單位中有兩個1,第十個有兩個1,第壹百個有兩個1,第壹千個有兩個1。這組數字處於穩定狀態。

誰先拿比賽,無論怎麽拿都會破壞穩定,誰先拿誰就輸。只要後者把被前者破壞的不穩定狀態帶進穩定狀態,它就壹定會贏。

  • 上一篇:NETGEAR發布96端口模塊化萬兆交換機 簡化AV-OVER-IP的部署
  • 下一篇:盜墓筆記中的齊羽是誰?
  • copyright 2024編程學習大全網