Поиск набора решений линейного уравнения?

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 

Как следует оптимизировать это для скорости? Что мне делать?

По существу это Язык-Агностик вопрос. Ответ C/C++ также поможет.

Answer 1

Lefteris E «s ответ является путь,

но я делать чувствуют 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 

EDIT: вы должны позаботиться о том, N-й не станет отрицательным. Вот что min предполагается сделать

Ответ Leftris на самом деле лучше, чем у меня, потому что эти особые случаи заботятся изящным образом

Answer 3

Это работает в квадратичное время. Вы можете уменьшить его до линейного времени, переставив уравнение в форму y = .... Это позволяет вам перебирать только x, рассчитать y и проверить, является ли это целым числом.

Answer 4

Вы можете попытаться рассмотреть только цифры для x с учетом N =10; причина такова: 2y должен быть ровным, поэтому x должен быть ровным. Это должно сократить общее время работы до половины проверки всех x.

Если вы также требуете, чтобы ответ был натуральным числом, поэтому отрицательные числа исключаются. тогда вам может потребоваться только проверить номера, которые находятся между [0,10] для x, так как оба x и 2y не должны превышать 10.

Answer 5

Рассчитать y по x. Для целого положительного x и реальной y:

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

Answer 6

мы можем перебрать области у и вычислить х.Кроме того, принимая во внимание, что х также имеет ограниченный диапазон, мы дополнительно ограничить область у, как [1, N/2] (как и все над N/2 при у даст отрицательное значение х)

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

• Это просто петли N/2 раз (вместо 50000)
• Он даже не делать эти дорогие умножения и деления