求解一个简单的线性方程

Question

假设我需要求解以下方程，

ax + by = c

其中a、b、c为已知值，x、y为0到10（含）之间的自然数。

除了

的简单解决方案

for (x = 0; x <= 10; x++)
    for (y = 0; y <= 10; y++)
         if (a * x + b * y == c)
             printf("%d %d", x, y);

...有没有办法高效地找到这个独立系统的所有解决方案？

Answer 1

您可以通过直接检查 (c-a*x)/b 是否为整数来避免第二个 for 循环。

编辑：由于我在评论中指出的一些粗心疏忽，我的代码没有我希望的那么干净，但它仍然比嵌套 for 循环。

int by;
for (x = 0; x <= 10; x++) {
    by = c-a*x;                         // this is b*y

    if(b==0) {                          // check for special case of b==0
        if (by==0) {
            printf("%d and any value for y", x);
        }
    } else {                            // b!=0 case
        y  = by/b;                  
        if (by%b==0 && 0<=y && y<=10) { // is y an integer between 0 and 10?
            printf("%d %d", x, by/b);
        }
    }
}

Answer 2

您只需循环遍历 x，然后计算 y。如果 y 是整数且介于 0 和 10 之间，则 (x, y) 是一个解。

在 C:

for (int x = 0; x <= 10; ++x) {
    double y = (double)(c - ax) / b;
    // If y is an integer, and it's between 0 and 10, then (x, y) is a solution
    BOOL isInteger = abs(floor(y) - y) < 0.001;
    if (isInteger && 0 <= y && y <= 10) {
        printf("%d %d", x, y);
    }
}

Answer 3

在你的例子中，由于 x 和 y 只取 0 和 10 之间的值，暴力算法可能是最好的选择，因为它花费更少的时间实施。

但是，如果你必须在更大的范围内找到所有对的积分解(x, y)，你真的应该使用正确的数学工具来解决这个问题。

您正在尝试求解线性丢番图方程，众所周知，当且仅当 a 的最大公约数 d 和 b 除以 c.

如果不存在解决方案，那么您就完成了。否则，您应该先应用 Extended Euclidean Algorithm 求方程 ax + by = d.

的特解

并且根据Bézout's identity，所有其他积分解的形式为：

其中 k 是任意整数。

但请注意，我们对 ax + by = c 的解很感兴趣，我们必须将所有 (x, y) 对缩放 c / d。

求解一个简单的线性方程

Solving a simple linear equation

algorithm

linear-equation

linear-algebra