Алгоритм вычисления множества решений простого простого уравнения с двумя переменными

Предположим, что у меня есть простое уравнение вида:

7x + 4y = n

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

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) в худшем случае. Есть ли лучший алгоритм для вычисления решения?

Ответ 1

Рассмотрим более общую задачу

Для двух взаимно простых натуральных чисел 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/b в шагах O (log b). Оба алгоритма, естественно, дают уникальный c < b с этим свойством.

Тогда минимальным кандидатом для x является остаток x0 of n*c по модулю b.

Задача имеет решение с неотрицательными x и y тогда и только тогда, когда x0*a <= n, а затем x0 является минимальным неотрицательным x, появляющимся в любом решении с неотрицательными x и y.

Конечно, для малых a и b как 7 и 4, грубая сила не медленнее, чем вычисление инверсии a по модулю b.

Ответ 2

Мы имеем

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.

Ответ 3

Я бы рекомендовал проверить метод Simplex в Numericical Recipes in C book. Вы можете легко обработать код C как псевдокод и сделать java-версию. Версия симплекса, которую вы хотите, это "ограниченный-симплекс", который имеет дело только с положительными значениями. Книга доступна онлайн бесплатно. Начните с раздела 10.8 и прочитайте вперед.

Ответ 4

O (n):

y=n/4;
while((n-4y)%7!=0 && y!=0){
 y--;
}
x=(n-4y)/7;