题目 - Alice和Bob取石子

ACFaster

Alice和Bob在玩一个取石子游戏，规则如下：
1，Alice先手，两人轮流取，每次可以取1/2/4颗。
2，取走最后一颗石子的人胜出。
' `& _6 I, a) b9 M6 j  g% Z
问题：
1，共有16颗石子时，谁将胜出？
) h/ O. r6 v4 F( O2，共有n (n>=1) 颗石子时，谁将胜出？

Ricky

n % 3 == 0先手输，否则，先手赢。
. `4 N1 L2 i. W6 |- \$ {4 h因为3是先手必败态，取1，2，4，向前推，能推出6也是先手必败态，以此类推，3的倍数都是先手必败态。

lothar

感觉可以用dp来做

ACFaster

lothar 发表于 9-9-2014 09:21 PM
- C% n! w: j6 z. s感觉可以用dp来做

& ?# Q% j5 ~# y% \7 Y; q! U6 cDP是对的，但这题有O(1)解法，可以再多思考一下。