题目 - Alice和Bob取石子

ACFaster

Alice和Bob在玩一个取石子游戏，规则如下：
1，Alice先手，两人轮流取，每次可以取1/2/4颗。
/ n$ |4 u& F5 y6 p) p2，取走最后一颗石子的人胜出。
. d) I" G  W- t! O  z/ @1 l: m( `
$ b' E# s4 l, J& w0 _问题：
1，共有16颗石子时，谁将胜出？
, Z7 W$ _. P' g8 ^+ o' X0 g  F2，共有n (n>=1) 颗石子时，谁将胜出？

Ricky

n % 3 == 0先手输，否则，先手赢。
因为3是先手必败态，取1，2，4，向前推，能推出6也是先手必败态，以此类推，3的倍数都是先手必败态。

lothar

感觉可以用dp来做

ACFaster

lothar 发表于 9-9-2014 09:21 PM
5 f9 ]7 V; f) i) X( h  n5 n, |3 y感觉可以用dp来做

6 c  i( _- y4 P0 ^9 E2 E6 UDP是对的，但这题有O(1)解法，可以再多思考一下。