0

我编写了一个程序来寻找丢番图方程的通解，但是当我查看在线计算器时，这个解并不完全正确。例如，对于方程“45x-128y=177”，一般形式的解应该是“x=6549-128k”和“y=2301-45k”，但我得到“x=6549+k 128”和“y =-2301+k 45"。我的代码：

import re

def extended_gcd(a, b):
    if a == 0:
        return (0, 1)

    (x, y) = extended_gcd(b % a, a)

    return (y - (b // a) * x), x


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def main():
    s = input('Enter the Diophantine equation: ')
    s1 = re.findall(r'\d+', s)
    a = int(s1[0])
    b = int(s1[1])
    c = int(s1[2])

    d = gcd(a, b)
    print(f'GCD({a},{b}) = {d}')

    if d % c != 0:
        print('This equation has an infinite set of solutions')
        a1 = a // d
        b1 = b // d
        print(f'Short equation: {a1}s + {b1}t = {1}')
        (s, t) = extended_gcd(a1, b1)

        x0 = (c // d) * s
        y0 = (c // d) * t

        print("General solution")
        print(f"x = {x0} + k * {b // d}")
        print(f"y = {y0} + k * {a // d}")
    else:
        print('This equation has no solution')


if __name__ == "__main__":
    main()

问题是什么以及如何解决？

4

1 回答 1

0

您遇到的一个 Python 问题是您的正则表达式与负数不匹配，即在您的示例s1[1]中128不是-128. 要匹配符号，您可以将正则表达式匹配行更改为

    s1 = re.findall(r'[-+]?\d+', s)

所以s1[1]现在是正确的-128，因为您可以通过在正确的位置打印来检查

它似乎仍然没有产生正确的答案，但至少在修复后输入应该是正确的。您应该仔细检查您是否正确编码了算法，例如打印中间结果并根据您的手动（或 Excel）计算检查它们。我们可以在这里帮助您解决编码问题，但不能帮助您解决算法问题......

于 2020-11-13T20:49:35.207 回答