Блог

моя цель состоит в том,чтобы работать в обратном направлении в алгоритме Евклида, чтобы найти такие положительные целые числа s, t, и именно с этой частью я борюсь. Я уже смог настроить алгоритм Евклида, но работать в обратном направлении мне очень сложно.

Идея заключается в следующем: мы вычисляем наибольший общий коэффициент из любых двух целых чисел, затем мы работаем в обратном направлении, здесь я продемонстрирую пример.

гхф(101, 7)

Разделите 7 на 101:

 101 - 7 * 14 = 3
 

Разделите 3 на 7:

 7 - 3 * 2 = 1
 

Разделите 1 на 3

 3 - 1 * 3 = 0
 

Теперь мы работаем в обратном направлении…

 1 = 7 - 3 * 2

1 = 7 - (101 - 7 * 14)*2

1 = 7 - 101 * 2   7 * 14 * 2

1 = 7 * 29 - 101 * 2
 

Так что, в частности, эти положительные целые числа s,t равны 29, 2.

Вот мой код до сих пор, проблема с кодом заключается в том, что для обратной реализации я прямо борюсь с тем, как заставить его дать мне такой результат.

Приведенный ниже код должен давать целое число s, такое, что s = 31, что равно (2 * 109 — 7 * 31). Однако это не так, поскольку оно неполное. Буду признателен за любой совет.

И да, нам нужны эти ценности s, t, вот и вся причина, по которой мы это делаем.

     def div(a, b):
        q, r = divmod(a, b)
        return q, r
    
    
    list_a = []
    list_b = []
    
    c, d = 109, 7
    q, r = div(c, d)
    list_a.append((c, q, r))
    list_a.append((c, q, r))  # Needed copy..
    
    print(f"{c} - {d}*{q} = {r}")
    
    c, d = 7, 4
    q, r = div(c, d)
    list_a.append((c, q, r))
    print(f"{c} - {d}*{q} = {r}")
    
    c, d = 4, 3
    q, r = div(c, d)
    list_a.append((c, q, r))
    print(f"{c} - {d}*{q} = {r}")
    
    c, d = 3, 1
    q, r = div(c, d)
    list_a.append((c, q, r))
    print(f"{c} - {d}*{q} = {r}")
    
    del list_a[-1]
    print(list_a)
    
    x, y, z = (
        list_a[-1][0],
        list_a[-2][2],
        list_a[-1][1],
    )
    
    for k in range(1, len(list_a)):
        x, y, z = (
            list_a[-k][0],
            list_a[-k - 1][2],
            list_a[-k][1],
        )
        if x == list_a[-k][2]:
            print("hmm")
            pass
            # Assign x as list_a[-k][0] - list_a[-k][1]
        if y == list_a[-k][2]:
            print("ymm")
            pass
            # Assign y as list_a[-k][0] - list_a[-k][1]
        print("%d - %d * %d" % (x, y, z))