计算平面上所有非负整数值的点

Question

我们得到一个由 Ax+By+Cz-D = 0 定义的平面，其中 D 明显大于 A、B、C 且 GCD(A,B,C) = 1。我如何找到所有点 (x, y , z), 其中 x,y,z 是整数并且 >= 0, 以有效的方式位于平面上?

我尝试暴力破解这个问题，通过计算 D/A、D/B 和 D/C 并简单地遍历该区域中的所有点来找到 x、y、z 的最大值。然而，这不是很有效并且需要很长时间才能完成，尤其是当 D 变大时。我想知道是否有更有效的算法来执行此操作或我可以进行任何优化以更快地解决问题？

暴力破解的Python代码：

points = []
for x in range(d//z + 1):
    for y in range((d - a*x)//y + 1):
        z = (d - a*x - b*y)//c
        if a*x + b*y + c*z == d:
            points.append ((x,y,x))

Answer 1

约束规划 (CP) 求解器可能会有所帮助。这里我使用 python-constraint 包。

from constraint import *
A = 3; B = 4; C = 7; D = 1000
problem = Problem()
problem.addVariables(['x','y','z'],range(0,D+1))
problem.addConstraint(ExactSumConstraint(D,[A,B,C]))
solutions = problem.getSolutions()
print(f"number of solutions: {len(solutions)}")
display(solutions)

输出：

number of solutions: 6036
Output exceeds the size limit. Open the full output data in a text editor
[{'z': 142, 'y': 0, 'x': 2},
 {'z': 141, 'y': 1, 'x': 3},
 {'z': 140, 'y': 5, 'x': 0},
 {'z': 140, 'y': 2, 'x': 4},
 {'z': 139, 'y': 6, 'x': 1},
 {'z': 139, 'y': 3, 'x': 5},
 {'z': 139, 'y': 0, 'x': 9},
 {'z': 138, 'y': 7, 'x': 2},
 {'z': 138, 'y': 4, 'x': 6},
 {'z': 138, 'y': 1, 'x': 10},
 {'z': 137, 'y': 8, 'x': 3},
 {'z': 137, 'y': 5, 'x': 7},
 {'z': 137, 'y': 2, 'x': 11},
 {'z': 136, 'y': 12, 'x': 0},
 {'z': 136, 'y': 9, 'x': 4},
 {'z': 136, 'y': 6, 'x': 8},
 {'z': 136, 'y': 3, 'x': 12},
 {'z': 136, 'y': 0, 'x': 16},
 {'z': 135, 'y': 13, 'x': 1},
 {'z': 135, 'y': 10, 'x': 5},
 {'z': 135, 'y': 7, 'x': 9},
 {'z': 135, 'y': 4, 'x': 13},
 {'z': 135, 'y': 1, 'x': 17},
 {'z': 134, 'y': 14, 'x': 2},
 {'z': 134, 'y': 11, 'x': 6},
...
 {'z': 85, 'y': 39, 'x': 83},
 {'z': 85, 'y': 36, 'x': 87},
 {'z': 85, 'y': 33, 'x': 91},
 {'z': 85, 'y': 30, 'x': 95},
 ...]

这花了 2.9 秒。指定 CP 模型只需 4 行代码。