机器人可以到达点（x，y）吗？ [英] Can a Robot reach a Point (x, y)?
问题描述
我在一次求职面试中遇到了这个问题。我找不到解决方案的正确算法，所以，我在这里发布此问题：
I came across this question in one of the Job Interviews & i am unable to find the correct alogorithm of the solution so, i am posting this question here:
有一个机器人可以在eththr的坐标平面上移动两种方式中的一种：
There is a robot who can move on a co-ordinate plane in eithr of the 2 ways:
鉴于机器人的当前位置是（x，y），机器人可以移动等于x&的总和。 y的方向符如下：
Given that the robots current position is (x,y), The robot can move equal to the sum of x & y in either if the directon like so:
(x,y) -> (x+y, y)
(x,y) -> (x, x+y)
现在给定了一个初始点（x1，y1）和一个目标点（x2，y2），您需要编写一个程序来检查机器人是否可以通过任意移动到达目的地。
Now given a initial Point (x1, y1) and an destination point (x2, y2) you need to write a programme to check if the robot can ever reach the destination taking any number of moves.
注意：x1，y1 ，x2，y2> 0
说明：
-
假设机器人的初始点为（2,3），目标为（7,5）
Suppose the robot's initial point is (2,3) and desintation is (7,5)
在这种情况下，结果为yes机器人可以采用以下路径：
Result in this case is yes as the robot can take this path:
（2,3）->（2，2 + 3）=>（2，5）
(2,3) -> (2, 2+3) => (2, 5)
（2,5）->（2 + 5，5）=>（7,5）
(2,5) -> (2+5, 5) => (7,5)
假设机器人的初始点是（2,3），目标点是（4,5）
Suppose the robot's initial point is (2,3) and desintation is (4,5)
在这种情况下，结果为No，因为无论机器人采用哪种路径都无法到达（4 ，5）
Result in this case is No as no matter what path the robot takes it cannot reach (4,5)
推荐答案
幼稚的暴力破解方法
一种方法是递归地探索每一个可能的动作，直到达到目标为止。
A naive brute-force approach
One way would be to recursively explore every possible move until you reach the target.
要考虑的事情是，机器人可以无限期地移动（永远不会到达目标），因此您需要一个端盖，以使功能完成。幸运的是，位置总是在 x 和 y 轴上增加，因此无论是x坐标还是y坐标大于目标，您可以放弃探索该路径。
Something to consider is that the robot can keep moving indefinitely (never reaching the target) so you need an end case so the function completes. Luckily the position is always increasing in the x and y axis, so when either the x-coordinate or y-coordinate is greater than the target, you can give up exploring that path.
所以，像这样：
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)
它的工作原理是：
And it works:
>>> can_reach_target((2,3),(7,5))
True
>>> can_reach_target((2,3),(4,5))
False
一个局限性是它不适用于负坐标-不确定这是否是必需项，请让我知道是否满足要求，然后我将调整答案。
A limitation is that this does not work for negative coordinates - not sure if this is a requirement, just let me know if it is and I will adapt the answer.
另一方面，如果不允许使用负坐标，则我们也可以按照戴夫建议进行处理。这种方式效率更高，因为实现是机器人到达每个坐标只有一种方式。
On the other hand, if negative co-ordinates are not allowed, then we can also approach this as Dave suggests. This is much more efficient, as the realisation is that there is one and only one way of the robot getting to each coordinate.
该方法依赖于能够确定哪个我们步进的方式：增加x坐标或y坐标。我们可以通过选择两者中较大的一个来确定最后更改的坐标。以下证明可以保证是这种情况。
The method relies on being able to determine which way we stepped: either increasing the x-coordinate or the y-coordinate. We can determine which coordinate was last changed, by selecting the larger of the two. The following proof guarantees that this is the case.
状态更改的可能性是：
1. (a, b) => (a+b, b) a x-coordinate change
，并且
2. (a, b) => (a, a+b) a y-coordinate change
在情况（1）中，x-坐标现在变大了，因为：
In case (1), the x-coordinate is now larger, since:
a > 0
a + b > b (add b to both sides)
，并且类似，因为 b 也是> 0 ，我们可以得出 a + b 是> a 。
and similarly, since b is also > 0, we can deduce that a+b is > a.
现在我们可以从目标开始，并问：哪个坐标将我们引到了这里？答案很简单。如果x坐标大于y坐标，则从x坐标减去y坐标，否则从y坐标减去x坐标。
Now we can start from the target and ask: which coordinate led us here? And the answer is simple. If the x-coordinate is greater than the y-coordinate, subtract the y-coordinate from the x-coordinate, otherwise subtract the x-coordinate from the y-coordinate.
也就是说，对于坐标，如果 x>则，那么我们来自（x，y）。 y （xy，y）否则为（x，yx） 。
That is to say, for a coordinate, (x,y), if x > y, then we came from (x-y,y) otherwise (x,y-x).
现在可以将第一个代码修改为：
The first code can now be adapted to:
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
Timings
Timings
>>> 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
因此您可以看到在两种情况下回溯器的速度都快将近三倍。
So you can see that the backtracker is nearly three times faster in both cases.
这篇关于机器人可以到达点（x，y）吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
