c++ - 寻找线性方程的解集？

Question

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

x+2y = N, x<100000和y<100000.

给定N=10，说。

我在python中这样做：

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

我应该如何优化这个速度？我该怎么办？

本质上这是一个与语言无关的问题。C /C++答案也会有所帮助。

score 5 · Accepted Answer

如果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

编辑：你必须注意 Nx 不会变成负数。这min就是应该做的

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

score 3 · Accepted Answer

我们可以遍历 y 的域并计算 x。还考虑到 x 也有一个有限的范围，我们进一步将 y 的域限制为 [1, N/2] （因为任何超过 N/2 的 y 都会给 x 负值）

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

score 1 · Accepted Answer

这在二次时间中运行。您可以通过将方程式重新排列为形式来将其减少为线性时间y = ...。这允许您x仅循环、计算y并检查它是否为整数。

score 0 · Accepted Answer

x您可以尝试只检查给定的偶数N =10；原因是：2y必须是偶数，因此，x必须是偶数。这应该将总运行时间减少到检查 all 的一半x。

如果您还要求答案是自然数，则排除负数。然后，您只需检查介于[0,10]for之间的数字x，因为两者x和2y必须不大于10单独。

score 0 · Accepted Answer

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

5 回答 5