为什么程序没有正确地寻找丢番图方程的通解

Question

我编写了一个程序来寻找丢番图方程的通解，但是当我检查在线计算器时，这个解并不完全正确。例如，对于方程"45x-128y=177“，一般形式的解应该是”x=6549-128 k“和"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()

问题是什么，如何解决？

Answer 1

Python的一个问题是正则表达式与负数不匹配(在示例中，s1[1]是128而不是-128 )。要匹配符号，可以将regex匹配行更改为

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

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

它仍然没有得到正确的答案，但至少在修复后输入应该是正确的。您应该反复检查您的算法编码是否正确，例如，打印中间结果，并对照手工(或Excel)计算检查它们。我们可以在这里帮助你解决编码问题，但不是你的算法问题。