Python Линейное диофантово уравнение

Question

Я делаю домашнюю работу для класса, и я проводил некоторые исследования. Я нашел пример уравнения для нахождения диофантова уравнения. Назначение дается, когда есть gcd (a, b) == 1, тогда есть диофантово уравнение, где ax + by = 1.

Я понял, как это уравнение находит значение для x и y, но я Я не уверен, как эта функция работает. Я получил часть, где есть функция divmod и рекурсивный метод внутри функции, но я не знаю, когда она остановится.

извините за сложные и неоднозначные вопросы, но я хочу знать, как работает это уравнение. Я имею в виду, как заканчивается это уравнение. Например, когда задано число 43 и 486, тогда gcd (43, 486) == 1. Это означает, что есть уравнение, где 43x + 486y = 1. Решение говорит 43 (-113) + 486 (10) = 1. И функция решить также получила значения x и y.

Я пытался просмотреть код и посмотреть, как он обрабатывается, но я не понимаю else: part.

def isolve(a, b):
    quotient, remainder = divmod(a, b)
    if remainder == 0:
        return [0, 1 / b]
    else:
        sol = isolve(b, remainder)
        x = sol[0]
        y = sol[1]
        return [y, x - quotient * y]

Answer 1

Я не уверен, что точно понимаю, что вы ищете, но давайте рассмотрим следующий модифицированный код:

def simple_linear_diophantine_r(a, b):
    q, r = divmod(a, b)
    if r == 0:
        return (0, b)
    else:
        x, y = simple_linear_diophantine_r(b, r)
        return (y, x - q * y)


a, b = 43, 486
x, y = simple_linear_diophantine_r(a, b)
print(f'({a}) * ({x}) + ({b}) * ({y}) == {a * x + b * y}')
# (43) * (-113) + (486) * (10) == 1

, который работает, как и ожидалось. По сравнению с исходным кодом я переписал математику таким образом, что используются только int -защищенные операции (без разделения float). Кроме того, я переименовал саму функцию и некоторые внутренние переменные.

Пока это более или менее то, что вы уже знали.

Теперь, один способ понять, что происходит, это использовать отладчик Python .

Более простой для иллюстрации подход заключается в размещении вызовов print() в Strategi c местах:

def simple_linear_diophantine_r(a, b):
    q, r = divmod(a, b)
    print(f'a={a}, b={b}, q={q}, r={r}')  # DEBUG
    if r == 0:
        return (0, b)
    else:
        x, y = simple_linear_diophantine_r(b, r)
        print(f'x={x}, y={y}')  # DEBUG
        return (y, x - q * y)


a, b = 43, 486
x, y = simple_linear_diophantine_r(a, b)
print(f'({a}) * ({x}) + ({b}) * ({y}) == {a * x + b * y}')

вывод которого теперь:

a=43, b=486, q=0, r=43
a=486, b=43, q=11, r=13
a=43, b=13, q=3, r=4
a=13, b=4, q=3, r=1
a=4, b=1, q=4, r=0
x=0, y=1
x=1, y=-3
x=-3, y=10
x=10, y=-113
(43) * (-113) + (486) * (10) == 1

, и теперь вы можете более легко следить за тем, что происходит при каждом вызове функции.