Minmuim步骤达到一个数组点

Question

有一个无限的一维数组范围从（-infinity，无穷大）。你目前在0号单元。你的目标是达到H号单元。允许有两种移动。

U =右边的步骤（正面）。
D =左侧的步数（负侧）。
我们必须找到最低数量。的移动如果（possiable）

用于h = 2 U = 2 d = 1个

第一个举动2个步骤，以达到细胞数目2。然后1个步骤向右向左到达单元编号1和2最后更多的步骤来实现目标的权利。因此需要3次移动，这是最小的。

什么是算法来解决这个问题。我的方法进行递归调用，即h + u和h-d，直到h == 0。

Answer 1

让我们米是数字的移动必须被朝向的移动的正侧和Ñ许多必须被向负侧进行制造。 米和ñ必须满足以下公式：

h = u * m - d * n 

我们知道^h，ü和d。为你的例子将如下所示的公式（我假设^h应该是3而不是2，还看到我的评论）：

3 = m * 2 - n * 1 
-> 
n = 2 * m - 3 

我们也知道，米> = 0，ñ > = 0和m和n是整数。现在，最简单的方式找到米和ñ将计算ñ为米 = 0,1,2,3,4 ......直到你将收到ň满足所有条件（你也可以根据n计算m）。在您的例子将是：

m = 0 -> n = -3 is an integer but n < 0 so it is not an answer 
m = 1 -> n = -1 is an integer but n < 0 so it is not an answer 
m = 2 -> n = 1 

所以答案是米 = 2和ñ = 1。您不必检查其他m的结果，因为您将始终收到更高的值（h = u * m - d * n是一个正在增加的功能）。

这不是一切。可能存在没有整数解的方程。在这种partocular情况下，我们正在考虑的线性不定方程根据Wikipedia具有整数解：

当且仅当ħ是d和ü

的最大公约数的倍数

让我们再次回到您的例子。 2和1的GCD是1，3是1的乘积，因此存在整数解。然而，让我们考虑h = 9,d = 2和u = 4。 GCD（2,4）是2并且9不是乘法2，所以没有解决方案。您必须在尝试查找m和n之前检查此条件，否则您将以不定式循环结束。