求线性方程组的解集？

Question

我需要为这个方程找到所有可能的解决方案：

x+2y = N，x<100000和y<100000。

比如说，给定N=10。

我在蟒蛇里这样做

for x in range(1,100000):
    for y in range(1,100000):
        if x + 2*y == 10:
             print x, y

我应该如何为速度优化这一点？我该怎么办？

本质上这是一个Language-Agnostic问题。C/C++回答也会有帮助。

Answer 1

Lefteris E的回答是走的路，

但我确实觉得y应该在[1,N/2]而不是[1,2*N]的范围内

解释：

x+2*y = N

//replace x with N-2*y
N-2*(y) + 2*y = N
N-2*(N/2) + 2*y = N
2*y = N

//therefore, when x=0, y is maximum, and y = N/2
y = N/2

所以现在你可以做：

for y in range(1,int(N/2)):
   x = N - (y<<1)
   print x, y

Answer 2

如果是x+2y = N，那么y = (N-x)/2 (假设N-x是偶数)。您不需要在整个range(1,100000)中进行迭代

像这样(对于给定的N)

if (N % 2): x0 = 1
else: x0 = 0
for x in range(x0, min(x,100000), 2):
    print x, (N-x)/2

编辑:你必须小心N-x不会变成负值。这就是min应该做的

Leftris的答案实际上比我的要好，因为这些特殊情况是以一种优雅的方式处理的。

Answer 3

我们可以在y的区域上迭代并计算x。同时考虑到x也有一个有限的范围，我们进一步将y的区域限制为1, N/2。

x=N;
for y in range(1,N/2-1):
     x = x-2
     print x, y

• 这只是循环N/2次(而不是50000次)。
• 它甚至不做那些昂贵的乘法和除法