找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 3740|回复: 10
收起左侧

[面经题目讨论] 题目 - Alice和Bob取石子

[复制链接]

7

主题

2

精华

110

积分

资深会员

Rank: 2

积分
110
发表于 9-9-2014 09:03 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
Alice和Bob在玩一个取石子游戏,规则如下:' w* T" v1 T" L2 {$ D$ o
1,Alice先手,两人轮流取,每次可以取1/2/4颗。) q$ e$ x+ z3 x9 u1 a6 w
2,取走最后一颗石子的人胜出。
' `& _6 I, a) b9 M6 j  g% Z7 [9 T6 Y  h6 z; B
问题:( Y' {% \# f" e4 G, W
1,共有16颗石子时,谁将胜出?
) h/ O. r6 v4 F( O2,共有n (n>=1) 颗石子时,谁将胜出?

0

主题

0

精华

265

积分

高级会员

Rank: 3Rank: 3

积分
265
发表于 9-9-2014 11:04 PM | 显示全部楼层
n % 3 == 0先手输,否则,先手赢。
. `4 N1 L2 i. W6 |- \$ {4 h因为3是先手必败态,取1,2,4,向前推,能推出6也是先手必败态,以此类推,3的倍数都是先手必败态。

4

主题

0

精华

253

积分

高级会员

Rank: 3Rank: 3

积分
253
发表于 9-9-2014 09:21 PM | 显示全部楼层
感觉可以用dp来做

7

主题

2

精华

110

积分

资深会员

Rank: 2

积分
110
 楼主| 发表于 9-9-2014 10:36 PM | 显示全部楼层
lothar 发表于 9-9-2014 09:21 PM
- C% n! w: j6 z. s感觉可以用dp来做

& ?# Q% j5 ~# y% \7 Y; q! U6 cDP是对的,但这题有O(1)解法,可以再多思考一下。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表