是否有任何算法可以求解在不同模空间中表示的方程组? 例如,考虑这个方程组:
(x1 + x2 ) % 2 = 0
( x2 + x3) % 2 = 0
(x1 + x2 + x3) % 3 = 2
本系统的解决方案之一是:
x1 = 0
x2 = 2
x3 = 0
我如何通过算术找到这个解决方案(不使用蛮力算法)?
谢谢
最佳答案
您可以将这些等式重写为
x1 + x2 = 2*n1
x2 + x3 = 2*n2
x1 + x2 + x3 = 3*n3 + 2
现在,这是一个线性丢番图方程问题,在文献中有解。
示例:http://www.wikihow.com/Solve-a-Linear-Diophantine-Equation
另见:https://www.math.uwaterloo.ca/~wgilbert/Research/GilbertPathria.pdf
算法:
将xi写成nks的函数
在这种情况下:
x3 = 3*n3 + 2 - 2*n1
x2 = 2*n2 - (3*n3 + 2 - 2*n1)
x1 = 2*n1 - (2*n2 - (3*n3 + 2 - 2*n1))
由于右侧没有除法,所以选择任意一个 (n1, n2, n3),你应该得到一个解决方案。
关于algorithm - 解决具有不同模数的链接方程组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42044831/