1

この方程式のすべての可能な解を見つける必要があります。

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++の回答も役立ちます。

4

5 に答える 5

5

の場合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の答えは実際には私のものよりも優れています

于 2013-04-08T14:37:49.943 に答える
1

これは二次時間で実行されます。方程式を の形に並べ替えることで、線形時間に短縮できますy = ...。これにより、ループxのみを実行し、 を計算yして、整数かどうかを確認できます。

于 2013-04-08T14:38:09.833 に答える
0

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
于 2013-04-08T15:40:36.617 に答える
0

x指定されたの偶数のみを調べようとする場合がありN =10ます。その理由は、偶数でなければなら2yない、したがって、偶数でxなければならないということです。これにより、合計実行時間が、すべてを調べる場合の半分に短縮されますx。

答えが自然数であることも必要な場合は、負の数は除外されます。との両方が単独よりも大きくてはならない[0,10]ため、の間の偶数の数値のみを調べる必要があります。xx2y10

于 2013-04-08T14:38:48.553 に答える