13

假设我有一个简单的公式：

7x + 4y = n

其中 n 由我们选择，x、y 和 n 都是正整数。这是给我们的唯一等式。在可能的解决方案中，我们需要 x 最小的解决方案 (x,y)。例如

7x + 4y = 14, then (2, 0) is the solution
7x + 4y = 15, then (1, 2) is the solution
7x + 4y = 32, then (4, 1) and (0, 8) are the possible solutions,
of which (0, 8) is the correct solution

我想设计一种算法以尽可能少的运行时间计算它。我想到的当前算法是这样的：

Given an input n
Calculate max(x) = n/7
for i = 0 to max(x)
    If the equation 7*i + 4*y = n holds
        return value of i and y
    else
        continue

我认为，在最坏的情况下，该算法的运行时间可达 O(n)。有没有更好的算法来计算解决方案？

4

4 回答 4

7

让我们考虑更一般的问题

  • 对于两个互质的正整数a和b，给定一个正整数n，找到一(x,y)对非负整数，使得a*x + b*y = n具有最小x。（如果有。不必有，例如7*x + 4*y = 5没有非负x和的解y。）

暂时忽略非否定性，给出任何解决方案

a*x0 + b*y0 = n

所有解决方案都有(x0 - k*b, y0 + k*a)一些整数的形式k。所以x模b和y模的余数a是解的不变量，我们有

a*x ≡ n (mod b), and b*y ≡ n (mod a)

所以我们需要解方程a*x ≡ n (mod b)——另一个方程如下。

设0 < c为 的整数a*c ≡ 1 (mod b)。例如，您可以通过扩展欧几里得算法或（等效地）a/bO(log b) 步骤中的连分数展开来找到它。两种算法自然会产生c < b具有该属性的唯一性。

那么最小的候选是modulox的余数。x0n*cb

该问题有一个非负的解x，y当且仅当x0*a <= n，然后是出现在任何非负和的解x0中的最小非负数。xxy

当然，对于像 7 和 4 这样的小a，b蛮力并不比计算amodulo的倒数慢b。

于 2012-05-03T14:05:28.960 回答
6

我们有

7(x-4)+4(y+7)=7x+4y

所以如果 (x, y) 是一个解，那么 (x-4,y+7) 也是一个解。因此，如果有一个解决方案，那么就有一个 x<4。这就是为什么您只需要测试在恒定时间内运行的 x=0..3 的原因。

这可以扩展到任何形式为 ax+by=n 的方程，您只需要测试 x=0..b-1。

于 2012-05-03T13:45:08.063 回答
2

我建议您查看“ C 中的数值食谱”一书中的 Simplex 方法。您可以轻松地将 C 代码视为伪代码并制作 java 版本。您想要的单纯形的版本是“约束单纯形”，它只处理正值。该书可在线免费获得。从第 10.8 节开始并向前阅读。

于 2012-05-03T14:05:04.873 回答
1

上） ：

y=n/4;
while((n-4y)%7!=0 && y!=0){
 y--;
}
x=(n-4y)/7;
于 2012-05-03T13:55:57.580 回答