这道题给我整不会了，求大神

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1248 天前的主题，其中的信息可能已经有所发展或是发生改变。

爆炸数游戏：
规定一个数字 n 作为爆炸数，x 名玩家从 0 开始轮流喊数，每人每次最多能说 m 个数，喊道爆炸数的那个玩家将输掉游戏。
当 n,x,m 不同时，每个玩家的输赢概率也不同，请写一个函数返回输掉游戏概率最大的玩家是第几位,返回结果为数字或者数组。
比如当 n=3，x=3，m=1 时，那么很显然游戏将这样进行：
玩家 1:0
玩家 2:1
玩家 3:2
玩家 1:3
那么玩家 1 输的概率为 100%，概率最大，结果返回数字 1
input:
n=3
x=3
m=1
output:
1

第 1 条附言 · 2021-06-22 20:17:59 +08:00

<pre>
很多人没有理解题意，数字是连续报的，比如每个人最多说 3 个，第一个人说 0 、1 、2，第二个人说 3 、4，数字从 0 开始到 n，每个人都要从前一个人说的数的末尾项+1 作为开始。

当 n，x，m 都是确定的，游戏有很多种情况，举个例子，这里所有情况数设为 sum，所有情况中，爆炸数 n 落在第一位玩家的次数设为 times，那 rate=times/sum 就是第一位玩家输掉的概率，如果 rate 最低，那么返回 1，如果第一位和第二位玩家的 rate 都是最低，那么返回数组[1,2]
</pre>

玩家

概率

爆炸

11 条回复 • 2021-06-22 19:09:52 +08:00

Mithril

2021-06-22 17:48:45 +08:00

显然当 n<=m+1 的时候，第一个人胜率 100%，这时候输出啥？数组？

lidlesseye11

2021-06-22 17:53:30 +08:00

玩家是随机喊的吗？还是说每个玩家都是聪明绝顶的博弈大师，只会喊对自己最有利的数？

leaveeel

2021-06-22 17:58:23 +08:00

从 0 开始，一共 n+1 个数，ceil((n+1)/m)就是轮数 z，z%x 就是输的那个人

leaveeel

2021-06-22 18:01:33 +08:00

哦不是按数字顺序报数啊，那就是博弈论。上面就不对了
@leaveeel

konar

2021-06-22 18:03:17 +08:00

int t = (n / m + (n % m == 0 ? 0 : 1) + 1) % x;
return t == 0 ? x : t;

我理解的题意是 m == 3 时，玩家 1 喊出 0，01，012 的概率各为 1/3
画了个图，猜的当每人都按最多个数来喊时输掉的那个人的下一个人按随机喊输掉概率最大

kop1989

2021-06-22 18:06:47 +08:00

假设所有人智商在线，那么当所剩数字（ n-已经喊的数字）<=m 的时候，下一个人必然输。
所以最优策略应该是保证（ n-已经喊的数字）<=m 这个事件，不出现在自己的前一个人身上。

但是当 x>2 时，根本没法保证。
所以这并不是一个概率学问题，这是个博弈论问题。

Vegetable

2021-06-22 18:11:53 +08:00

描述感觉不太完整，这个题目看起来是脱胎于猜数字这个游戏，还不太一样。

我觉得还有以下约束

- 玩家并不知道目标数字是多少，因此玩家喊 1~m 个数字的概率是相等的
- 每个人每次至少要喊一个数字，至多 m 个数字，但是每次喊的必须比上一个数字大

这样的话，从 0 开始到喊道 n，可以出现的情况数量就是有限集合，可以穷举了。

Vegetable

2021-06-22 18:13:27 +08:00

如果玩家知道 n，概率就是不可计算的了。而如果 m 等于 1，则结果只可能有一种。

wjfz

2021-06-22 18:23:16 +08:00

岳云鹏最擅长这个。

coderluan

2021-06-22 18:23:21 +08:00

因为输家只有一个, 不输就全是赢家, 这样所有人只要脑子没屁, 每次都只会报 1, 不明白这个思路可以参考下俄罗斯轮盘, 只是想自己活的人, 绝对不会多对自己开一枪的, 那么结果实际是固定的, 求下余数就行了, 也就是当子弹放枪里的一刻, 谁死就已经注定了, 所以是这题出的明显有问题, 设计了个烂游戏.

palfortime

2021-06-22 19:09:52 +08:00 via Android

每轮从[1..m]的 m 个数选择，找出和为 n 的且最后一次选择是 1 的排列，以这些排列总数作为分母 s，s[i]作为第 i 个人输的排列总数(i 由 1 开始)，对于每个排列长度 l，s[l%n] += 1，s[i]/s 就是第 i 个人输的概率。