两个坐标的可能路径

问题描述 投票:3回答:2

我最近接受了一次采访,我的算法只通过了除一个以外的所有测试用例,我无法弄清楚为什么。我需要解决的问题是:

给定2D网格中的站点(a,b)是否可以到达目的地点(x,y)。他唯一能做的就是从某个点(a,b)移动到(a + b,b)或(a,a + b)点。

我试图用gcd来解决它。例如如果gcd(a,b)= gcd(x,y)那么其他可能就没有了。直觉是如果k是a&b的gcd。那么,k也会除(a + b)。我使用以下算法来计算gcd:

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

编辑:数字a,b,x和y都是正整数。

algorithm traversal
2个回答
0
投票

您现在在帖子上有两个问题:

  1. 我该如何解决算法? Photonlink涵盖了这一点。
  2. 为什么GCD没有工作?

GCD是必要但不充分的条件。

是的,如果a = b,那么如果GCD(x,y)= a = b,则可以得到(x,y)。但是,这并不能概括为所有问题对。平凡的反例试图从(N,1)到达(1,N),其中N> 1。另一个是(2,3)=>(4,5)。


所以,让我们进入定性部分:“我无法弄明白......”。我怀疑问题是你看到Euclid算法和你的加法步骤之间的相似性。更强大的是,链接中的“向后”算法表明Euclid的算法适用。

它可以在某种程度上,但不像你试​​图使用它那样简单和普遍。将该问题视为笛卡尔平面中正整数格的图。允许的操作(有向边)定义了如何从一个点移动到另一个点。

这里的关键术语是指向的:一旦你从一个起点“移动”到一个定义你系统中GCD的那个,你就没有自由回溯这些步骤了。您可以向前或向后移动图表空间。

例如,虽然您的向后过渡允许您从(4,1)移动到(1,1)或从(1,4)移动到(1,1),但您不能使用它来从(4,1)结束路径)至(1,4):这些动作的一半是不允许的方向。


这有助于消除混乱吗?


1
投票

GCD(3,7)= GCD(7,3),但两者都无法到达。你的病情是必要的,但还不够。

请注意,每个点都有一个独特的可能前身。即对于点(a,b),如果a> b,那么前一个是(a-b,b),否则前一个是(a,b-a)。

© www.soinside.com 2019 - 2024. All rights reserved.