找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

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

[复制链接]

7

主题

2

精华

110

积分

资深会员

Rank: 2

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

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

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

x
Alice和Bob在玩一个取石子游戏,规则如下:2 Z7 r: ~  A/ [! \, O2 ~+ @
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 ]# r  u* y# I$ A
1,共有16颗石子时,谁将胜出?
, Z7 W$ _. P' g8 ^+ o' X0 g  F2,共有n (n>=1) 颗石子时,谁将胜出?

0

主题

0

精华

265

积分

高级会员

Rank: 3Rank: 3

积分
265
发表于 9-9-2014 11:04 PM | 显示全部楼层
n % 3 == 0先手输,否则,先手赢。% u, E2 q( ]4 f( e
因为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
5 f9 ]7 V; f) i) X( h  n5 n, |3 y感觉可以用dp来做

6 c  i( _- y4 P0 ^9 E2 E6 UDP是对的,但这题有O(1)解法,可以再多思考一下。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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