algorithm - 计算玩家 1 在 2 人游戏中获胜的方式数

Question

我遇到了以下问题，

2 名玩家玩游戏。在每个回合中，两名玩家都会获得 -x 到 +x(均包括在内)范围内的点数。玩家 1 从分数 p1 开始，玩家 2 从分数 p2 开始。如果他们总共玩了 k 轮，求出玩家 1 赢得游戏的方式总数，即在 k 轮结束时，玩家 1 的分数比玩家 2 多。

所以简而言之，我的理解是我们需要找到玩家 1 和玩家 2 的点组合总数，使得(玩家 1 的点集总和)-(玩家 2 点集总和)> = p2- p1+1

我不确定如何解决这个问题。请提出一种方法。提前致谢。

Answer 1

递归地解决这个问题。使用您的变量，让我们看一下案例:。让

score_range = [-x : x]

调用函数win_count

基本情况，k==1

如果k == 1，还有一圈要走。分差为p2-p1。如果玩家 2 在本轮中获得 n2 分，则玩家 1 在本轮结束时至少需要 (p2 + n2) - p1 + 1 分。现在，p1, p2 in score_range 有多少组合可用？您可以直接根据给定的整数进行计算。

返回该计数作为函数值。

递归情况，k > 1

浏览本轮所有可能的分数。重复计算游戏剩余部分的可能性。

count = 0
for n1 in score_range
    for n2 in score_range
        count += win_count(p1+n1, p2+n2, k-1, x)

你能从那里拿走它吗？