盒子裡有 n 個小球，兩人按規則輪流從盒中取球，勝負何解？

1樓：

大神，我數學是體育老師教的，下面給出我的一些小分析。

假設數列A(n)代表A的輸贏，0代表必輸，1代表必勝，我們可以得到如下遞迴關係：if(

A(n)

==0)又有關係：A(

n)=(((

n>1)

&&A(n

-1)==

1)&&((

n>3)

&&A(n

-3)==

1)&&((

n>7)

&&A(n

-7)==

1)&&((

n>8)

&&A(n

-8)==

1))?0

:1;也就是說對數列的第n(n > 8)項，如果n - 1，n - 3, n - 7, n - 8項都是1，那麼自己就是0，否則就是1，n < 8的時候可以把所有的n取值<=0的項看成1，因為非正數索引對數列沒有貢獻

可以很簡單的得到前8項

(<= 0)12345678 -> idx

(1 1 1 1)01010101 -> value

n > 8 && n < 16 的時候，由於前面0 1交錯，n - 1，n - 3, n - 7, n - 8項不可能全部同時為1，所以

9101112131415-> idx

1111111-> value

n = 16會發現n - 1，n - 3, n - 7, n - 8項都是1，然後你就發現尼瑪和開始又一樣子了

910111213141516171819-> idx

11111110101-> value

我感覺這是乙個馬爾可夫鏈的擴充套件，「馬爾可夫鏈 (Markov Chain)，它描述了一種狀態序列，其每個狀態值取決於前面有限個狀態。」我模模糊糊的記得可以使用一步狀態轉移矩陣的n次方化成單位陣，那個n貌似就是馬爾可夫鏈的週期，尼瑪我數學太爛了，模模糊糊的沒法往下給出嚴格的證明。汗！

盒子裡有 n 個小球， 兩人按規則輪流從盒中取球，勝負何解？