通过加或减求两个整数之间的最短路径
这是这个问题的描述:
给定两个整数 a 和 b。您想要找到将 a 转换为 b 所需的最短操作序列,其中每一步都允许您添加或减去 5、7 或 12。
例如,如果给定 a = -5 且 b = 19,最短路径是
-5 + 12 + 12 = 19
如果给你 1 和 3,最短路径将是
1 + 7 - 5 = 2
我能想到解决这个问题的唯一方法是使用 BFS 以及可能更多的修剪。我可以使用更好的算法吗?
谢谢!
Here's the description of this problem:
You are given two integers a and b. You want to find the shortest sequence of operations necessary to transform a into b, where at each step you are allowed to add or subtract 5, 7, or 12.
For example, if you are given a = -5 and b = 19, the shortest path is
-5 + 12 + 12 = 19
If you were given 1 and 3, the shortest path would be
1 + 7 - 5 = 2
The only way I can think about solving this is using BFS and maybe some more pruning. Is there a better algorithm I could use instead?
Thanks!
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
![扫码二维码加入Web技术交流群](/public/img/jiaqun_03.jpg)
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(6)
让我们从一组有趣的观察开始。正如许多其他人所指出的,目标是找到一些具有整数系数的线性组合 5x + 7y + 12z = b - a ,使得 |x| + |y| + |z|被最小化。但是我们可以利用这三个数字之间的一些非常有趣的联系:
让我们思考一下(1)和(2)共同告诉我们什么。 (1) 表示 x 和 y 上的符号不能相同,因为我们总是可以做得更好。 (2) 表示如果 x 和 z 具有相反的符号,或者如果 y 和 z 具有相反的符号,我们总是可以做得更好。总的来说,这意味着
看到这一点,如果所有三个都非零,如果 x 和 y 具有相同的符号,那么我们可以通过将它们替换为 12 来明显地使解决方案更好。否则,x 和 y 具有相反的符号。因此,如果 x 和 z 具有不同的符号,则通过 (2) 我们可以用更少的 7 来替换它们,否则 y 和 z 具有不同的符号,并且通过 (2) 我们可以用更少的 5 来替换它们。
好吧,这看起来真的很棒!这意味着我们只需要解这三个整数方程并找出哪一个的系数和最小:
幸运的是,通过 Bezout 的身份,因为 gcd(5, 7) = gcd(5, 12) = gcd(7, 12) = 1,所有这些方程组对于任何 b - a 值都有解。
现在,让我们看看如何求解每个方程。幸运的是,我们可以使用一些可爱的技巧来大大减少我们的搜索空间。例如,对于 5x + 7y = b - a,x 的值不能超出 [-6, +6],因为如果超出,我们只需用五个 7 替换七个 5。这意味着我们可以通过执行以下操作来求解上面的方程:
我们可以使用类似的技巧来求解后两个方程 - 对于第二个方程,x 的范围是 -11 到 +11,第三个 y 的范围也是从 -11 到 +11。然后我们可以从所有三个方程中取出最佳答案来看看答案是什么。
这里有一些伪代码来记录尽可能少的步骤。只需记录使用了哪些解决方案,然后将其扩展为完整路径,即可轻松修改以返回这些步骤:
该算法速度快得惊人 - 它运行时间为 O(1),因为所需的迭代次数求解三个线性系统中的每一个是一个常数(最多 23)。它只需要 O(1) 内存来保存可能的值,我认为实际上它可能是您能够编写的最快的算法。
希望这有帮助!
Let's start off with a set of interesting observations. As many others have noted, the goal is to find some linear combination 5x + 7y + 12z = b - a with integer coefficients such that |x| + |y| + |z| is minimized. But there are some very interesting connections between these three numbers that we can exploit:
Let's think about what (1) and (2) collectively tell us. (1) says that the signs on x and y can't be the same, since we can always do better. (2) says that if x and z have opposite signs or if y and z have opposite signs, we can always do better. Collectively this means that
To see this, if all three are nonzero, if x and y have the same sign, then we can clearly make the solution better by replacing them with 12s. Otherwise, x and y have opposite signs. Thus if x and z have different signs, by (2) we can replace them with fewer 7's, otherwise y and z have different signs and by (2) we can replace them with fewer 5's.
Okay, this is looking really great! This means that we just need to solve these three integer equations and find which one has the smallest sum of coefficients:
Fortunately, by Bezout's identity, because gcd(5, 7) = gcd(5, 12) = gcd(7, 12) = 1, all of these systems of equations have a solution for any value of b - a.
Now, let's see how to solve each of these equations. Fortunately, we can use some cute tricks to greatly reduce our search space. For example, for 5x + 7y = b - a, the value of x can't be outside of [-6, +6], since if it were we could just replace seven of the 5's with five 7's. This means that we can solve the above equation by doing the following:
We can use similar tricks to solve the latter two equations - for the second equation, x ranges from -11 to +11, and for the third y ranges from -11 to +11 as well. We can then just take the best answer out of all three equations to see what the answer is.
Here's some pseudocode to record the fewest number of steps possible. This can easily be modified to return what those steps are by just recording which of the solutions was used and then expanding it out into a full path:
This algorithm is amazingly fast - it runs in O(1) time because the number of iterations required to solve each three of the linear systems is a constant (at most 23). It requires only O(1) memory to hold the possible values, and I think that in practice it's probably the fastest algorithm you'll be able to write.
Hope this helps!
这个问题相当于获取数字
ab
。或abs(ab)
,因为它围绕零对称。我认为通过采用动态编程可以轻松完成此任务。例如,最快获得 23 的方法是获得23+5,23-5,23+7,23-7,23+12
或23-12
的最快方法代码> 加一运算。如果您在开始条件上应用几次(+5、-5、.. 的成本为 1,其他为无限),您将在O(ab)
中得到答案。The problem is equivalent to getting the number
a-b
. Orabs(a-b)
, since it's symmetric around zero. I think this can be done easily with an adoption of dynamic programming. For example, to quickest way to get 23 is the quickest way to get23+5,23-5,23+7,23-7,23+12
or23-12
plus one operation. If you apply that a couple of times on the start condition (cost of +5,-5,.. is 1, others are infinite), you'll have your answer inO(a-b)
.你需要解 5x+7y+12z = ba。使得|x| + |y| + |z|是最小值。也许有一种简单的数学方法。也许这有帮助: 链接< /a>
You need to solve 5x+7y+12z = b-a. such that |x| + |y| + |z| is minimum. Perhaps there is a straightforward mathematical way. Perhaps this helps: Link
我想你可以看看子集和问题来获取想法。
I guess you could have a look at the Subset Sum Problem for ideas.
预先计算第一个最小范围所需的运算,然后继续添加+12的倍数。
Pre calculate the operations needed for the first minimum range, after that just keep adding multiples of +12.
将所有操作组合预先计算到哈希图中,然后只需查找答案即可。
预计算步骤需要时间,但一旦完成,您就可以在预计算范围内找到答案,即 1 次查找操作。
这是一个小型 JavaScript 演示:
Pre-calculate all your operations combos into a hash map then just do a look-up on the answer.
The pre-calculation step will take time but once its done you have finds for answers within the pre-calculated range that are 1 look-up operation.
Here is a small JavaScript demonstration: