Решение простого линейного уравнения

Предположим, мне нужно решить следующее уравнение:

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);

... есть ли способ эффективно найти все решения для этой независимой системы?


algorithm linear-algebra linear-equation
person Matt Olan    schedule 25.02.2015    source источник

Ответы (3)


arrow_upward
3
arrow_downward

В вашем случае, поскольку x и y принимают значения только между 0 и 10, алгоритм грубой силы может быть лучшим вариантом, поскольку для его реализации требуется меньше времени.

Однако, если вам нужно найти все пары интегральных решений (x, y) в большем диапазоне, вам действительно следует применить правильный математический инструмент для решения этой задачи.

Вы пытаетесь решить линейное диофантово уравнение, и хорошо известно, что интегральное решение существует тогда и только тогда, когда наибольший общий делитель d чисел a и b делит c.

Если решения не существует, то все готово. В противном случае вам следует сначала применить Расширенный алгоритм Евклида, чтобы найти конкретное решение уравнения ax + by = d.

И согласно тождеству Безу, все остальные интегральные решения имеют вид :

http://upload.wikimedia.org/math/8/6/9/869734595b839cf44b8a1cb01607580f.png

где k — произвольное целое число.

Но обратите внимание, что нас интересует решение ax + by = c, мы должны масштабировать все наши пары (x, y) с коэффициентом c / d.

person chiwangc    schedule 25.02.2015

arrow_upward
0
arrow_downward

Вы только перебираете x, а затем вычисляете y. (x, y) является решением, если y является целым числом и находится в диапазоне от 0 до 10.

In 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);
    }
}
person Khanh Nguyen    schedule 25.02.2015

arrow_upward
0
arrow_downward

Вы можете избежать второго цикла for, напрямую проверив, является ли (c-a*x)/b целым числом.

EDIT: мой код менее чистый, чем я надеялся, из-за некоторых неосторожных упущений с моей стороны, указанных в комментариях, но он все же быстрее, чем вложенные 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);
        }
    }
}
person eigenchris    schedule 25.02.2015
comment
y также должен быть между 0 и 10 включительно. - person caveman; 25.02.2015
comment
Что произойдет, когда b равно 0? - person hk6279; 25.02.2015