原文恕刪 如果是演算法的話，我覺得應該可以用一個Ｎ^2的做法(不確定對不對) 如果是以最多拿兩倍來看(三被其實是一樣的做法) 先做一個二維的表，橫軸代表剩下的數量，縱軸代表上一個回合拿了幾個 因此每一格都是一個狀態，假設ｘ代表處於該狀態的玩家輸了，那麼， 對於n=0時，都應標上ｘ ｍ 10 ｘ 09 ｘ 08 ｘ 07 ｘ 06 ｘ 05 ｘ 04 ｘ 03 ｘ 02 ｘ 01 ｘ 00 01 02 03 04 05 06 07 08 09 10　ｎ 那麼，對於某一格(n,m)的狀態呢？我們需要檢查他所有可能的下一步， Ex : n = 10 , m = 1 時，可能的下一步為：(9,1) , (8,2) 只要有任一格為ｘ 則本格的值就不是ｘ，而是空白。 因此，填完之後，表格會變成： ｍ 10 ｘ 09 ｘ 08 ｘ 07 ｘ 06 ｘ 05 ｘ 04 ｘ 03 ｘ ｘ 02 ｘ　　　　　　 ｘ ｘ 01 ｘ ｘ　　ｘ ｘ 00 01 02 03 04 05 06 07 08 09 10　ｎ 如果用上述的方法，複雜度為Ｎ^3　但是，對於任一的 n 都有一個性質， 就是存在一個 m_0　使得　( n , m ) , m <= m_0 都是ｘ 那要如何找到 m_0 呢？　我們可以發現，若要由 n1 直接走到 n2 的方法就是 拿走 n1-n2 個火柴 那我們會走到 ( n2 , n1-n2 ) 的狀態，對於固定的n1，不論 m 為多少，所要檢查的 (n2,n1-n2) 都會落在一條直線上，也就是 X+Y= n1 我們將 (n2,n1-n2) 改寫成： ( n-m , m ) 那麼，我們從 m=1 開始，枚舉所有的m ( m <= n ) 必存在一個m'使的 ( n-m , m ) , m < m' 接不為ｘ，也就是說， 只要該玩家可以移動的步數小於 m'他就不可能移動到ｘ的格子上 => m_0 = [m'/2] ......... []為下高斯 因此，對於起始狀態為n根火柴的遊戲，可以用 O(n^2)的時間做出這張表，接下來就只要 照著表上所話的，每一次都移動到畫有ｘ的格子就可以了 (由此表也可以發現只要開始時，火柴的數量為fibonacci數，則必敗) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.228.163.130