algorithm - 求解一个简单的线性方程

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

在您的情况下，由于x并且y仅取 和 之间的值0，因此10蛮力算法可能是最佳选择，因为它需要更少的时间来实现。

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

您正在尝试求解线性丢番图方程，并且众所周知，当且仅当 和 的最大公约数除以 时，积分解d才存在abc。

如果解决方案不存在，那么您就完成了。否则，您应该首先应用扩展欧几里得算法来找到方程的特殊解ax + by = d。

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

其中k是一个任意整数。

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

Answer 2

您只需循环 x，然后计算 y。(x, y) 是一个解，如果 y 是整数，并且在 0 到 10 之间。

在 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

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

编辑：由于我在评论中指出的一些粗心疏忽，我的代码没有我希望的那么干净，但它仍然比嵌套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);
        }
    }
}