在笛卡尔平面上移动的概率

Question

我正在研究下面的编码问题，它看起来更像是概率问题而不是编码问题

你有一个由 5 个方块组成的菱形平台。瓦片的坐标是：(-1,0), (0.-1)。 （0,0），（0.1）。 (1.0)。您从坐标 (xs,ys) 开始 并继续向左（即 x 坐标减少 1）、向右（即 x 坐标增加 1）、向上（即 y 坐标增加 1）或 向下（即 y 坐标减少 1）。后续移动的方向是独立的。你到达坐标 (xe, ye) 的概率是多少 在从平台上掉下来之前？ 约束： [(-1.0), (0.-1), (0.0), (0.1), (1,0)] 中的 (xs, ys) (xe, ye) 在 [(-1,0), (0.-1), (0,0), (0,1), (1.0)] xs != xe 或 ys != ye

输入 xs, ys = -1, 0 xe, ye = 0, 0 输出应该是 0.25

下面是我实施的，它适用于我分享的案例，但对所有其他案例都失败了

def calculate_probability(xs, ys, xe, ye):
    edges = [[-1, 0], [0, -1], [0, 1], [1, 0]]
    if [xs, ys] in edges:
        if xe == 0 and ye == 0:
            return 0.25
        elif xs == xe and ys == ye:
            return 1.0
        elif [xe, ye] in edges:
            return 0.075
    
    if xs == 0 and ys == 0:
        if [xe, ye] in edges:
            return 0.3
        elif xe == 0 and ye == 0:
            return 1
    return 0

Answer 1

如果我们处理你从目的地开始的边缘情况，或者你从边缘开始而目的地是中心，我们会留下一个简单的场景：找到你到中心的路，然后到目的地。到达原点是一个平坦的

0.25

概率，然后它只是到达右边缘的问题。如果你随机走错了方向，你总能以

0.25

的成功概率原路返回。在以正确的方向（到达目的地）行走之前，这可以重复任意次数。

这意味着从原点来看，我们有1/4的机会选错方向，有3/4的机会选错方向。如果我们选对了方向就完了，如果我们选错了方向，我们就得选相反的方向才能回到原点，避免掉下来，这是1/4的机会。将这些结合起来，我们有 1/4 的第一次是正确的，而 3/8 的机会是第二次。如此反复，我们最终得到如下公式：

1/4 + 1/4 * (3/8) + 1/4 * (3/8)^2 + 1/4 * (3/8)^3 + ...
= 1/4 * (1 + (3/8) + (3/8)^2 + (3/8)^3 + ...)
= 1/4 * (8/5)
= 2/5

所以从原点来看，我们有

2/5

的机会走到正确的边瓦而不掉下来

代码中：

def solve(xs, ys, xe, ye):
    # already at destination
    if xs == xe and ys == ye:
        return 1

    # if destination is the origin, the probability is a flat 0.25
    if xe == 0 and ye == 0:
        return 0.25

    # first move must take you to the origin if not already there
    prob = 0.25 if xs != 0 or ys != 0 else 1

    # multiply by probability of walking from origin to destination
    return prob * 2 / 5