益智問題（拈之變形） - 拼圖

原文恕刪

如果是演算法的話，我覺得應該可以用一個Ｎ^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數，則必敗)


--