原文恕删 如果是演算法的话，我觉得应该可以用一个Ｎ^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