机器人可以到达点(x,y)吗？

Question

我在其中一个求职面试中遇到了这个问题,我无法找到解决方案的正确算法,所以我在这里发布这个问题:

有一种机器人可以通过两种方式在一个坐标平面上移动:

假设机器人当前位置是(x,y),机器人可以移动等于x和y的总和,如果直接像这样:

(x,y)  ->  (x+y, y)
(x,y)  ->  (x, x+y)

现在给出一个初始Point(x1,y1)和一个目标点(x2,y2),你需要编写一个程序来检查机器人是否可以通过任意数量的移动到达目的地.

注意:x1,y1,x2,y2> 0

说明:

1. 假设机器人的初始点是(2,3),而desintation是(7,5)

   这种情况下的结果是肯定的,因为机器人可以采用此路径:

   (2,3) - >(2,2 + 3)=>(2,5)

   (2,5) - >(2 + 5,5)=>(7,5)

2. 假设机器人的初始点是(2,3)并且desintation是(4,5)

   在这种情况下的结果是否,因为无论机器人采取何种路径都无法到达(4,5)

Answer 1

一种天真的蛮力方法

一种方法是递归地探索每一个可能的移动,直到你到达目标.

需要考虑的是机器人可以无限期地继续移动(永远不会到达目标),因此您需要一个结束案例,以便功能完成.幸运的是,位置始终在x和y轴上增加,因此当x坐标或y坐标大于目标时,您可以放弃探索该路径.

所以类似于:

def can_reach_target(pos, target):
    if pos == target: 
        return True
    if pos[0] > target[0] or pos[1] > target[1]: 
        return False
    return can_reach_target((pos[0], sum(pos)), target) or \
           can_reach_target((sum(pos), pos[1]), target)

它有效:

>>> can_reach_target((2,3),(7,5))
True
>>> can_reach_target((2,3),(4,5))
False

一个限制是,这不适用于负坐标 - 不确定这是否是一个要求,只是让我知道它是否是,我会调整答案.

Bactracking

另一方面,如果不允许负坐标,那么我们也可以像Dave所说的那样接近这一点.这样效率要高得多,因为实现机器人只有一种方法可以到达每个坐标.

该方法依赖于能够确定我们步进的方式:增加x坐标或y坐标.我们可以通过选择两者中较大的一个来确定最后一次更改的坐标.以下证明保证了这种情况.

国家变化的可能性是:

1. (a, b) => (a+b, b)       a x-coordinate change

和,

2. (a, b) => (a, a+b)       a y-coordinate change

在情况(1)中,x坐标现在更大,因为:

    a > 0
a + b > b  (add b to both sides)

同样,因为b是也> 0,我们可以推断出a+b是> a.

现在我们可以从目标开始并询问:哪个坐标引导我们在这里？答案很简单.如果x坐标大于y坐标,则从x坐标中减去y坐标,否则从y坐标中减去x坐标.

也就是说,对于一个坐标(x,y),如果x > y,那么我们来自(x-y,y)其他方面(x,y-x).

第一个代码现在可以适用于:

def can_reach_target(pos, target):
    if pos == target: 
        return True
    if target[0] < pos[0] or target[1] < pos[1]: 
        return False
    x, y = target
    return can_reach_target(pos, (x-y,y) if x > y  else (x,y-x))

它按预期工作:

>>> can_reach_target((2,3),(7,5))
True
>>> can_reach_target((2,3),(4,5))
False

计时

>>> timeit.timeit('brute_force((2,3),(62,3))',globals=locals(),number=10**5)
3.41243960801512
>>> timeit.timeit('backtracker((2,3),(62,3))',globals=locals(),number=10**5)
1.4046142909792252
>>> timeit.timeit('brute_force((2,3),(602,3))',globals=locals(),number=10**4)
3.518286211998202
>>> timeit.timeit('backtracker((2,3),(602,3))',globals=locals(),number=10**4)
1.4182081500184722

因此,您可以看到两种情况下回溯速度几乎快三倍.

Answer 2

倒退.我假设起始坐标是正的.假设您想知道(a,b)的起点是否与(x,y)的终点兼容.从(x,y)返回一步你是(xy,y)或(x,yx).如果x> y选择前者,否则选择后者.

Answer 3

我同意Dave的看法,倒退是一种有效的方法.如果只有正坐标是合法的,那么每个坐标最多只有一个有效父坐标.这使您可以在没有组合爆炸的情况下向后工作.

这是一个示例实现:

def get_path(source, destination):
    path = [destination]
    c,d = destination
    while True:
        if (c,d) == source:
            return list(reversed(path))
        if c > d:
            c -= d
        else:
            d -= c
        path.append((c,d))
        if c < source[0] or d < source[1]:
            return None

print(get_path((1,1), (1,1)))
print(get_path((2,3), (7,5)))
print(get_path((2,3), (4,5)))
print(get_path((1,1), (6761, 1966)))
print(get_path((4795, 1966), (6761, 1966)))

结果:

[(1, 1)]
[(2, 3), (2, 5), (7, 5)]
None
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (6, 5), (11, 5), (16, 5), (21, 5), (26, 5), (31, 5), (36, 5), (41, 5), (46, 5), (46, 51), (46, 97), (143, 97), (143, 240), (383, 240), (623, 240), (863, 240), (863, 1103), (863, 1966), (2829, 1966), (4795, 1966), (6761, 1966)]
[(4795, 1966), (6761, 1966)]

附录:我在查找O(1)解决方案时可能有用的一些观察结果:

• (a,b)可以从(1,1)到达,当且仅当a和b是互质的时候.
• 如果a和b具有共同因子,则(a,b)的所有子项也具有该共同因子.等效地,如果存在从(a,b)到(c,d)的路径,那么对于任何正的路径,也存在从(n*a,n*b)到(n*c,n*d)的路径.整数
• 如果a和b是互质的而不是(1,1),那么无限多的互质坐标是无法从(a,b)得到的.通过选择(a,b)作为起点,您实际上将自己限制在由(1,1)形成的树的某个子分支中.你永远无法到达(a,b)的任何兄弟分支,其中有无限多的坐标.