Re: [轉錄] 益智問題（拈 001,100，1枚~3倍）
原文恕刪
如果是演算法的話，我覺得應該可以用一個Ｎ^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
討論串 (同標題文章)
完整討論串 (本文為第 5 之 10 篇)：