おはようございます、私はここで新しいです、そして私は小さな問題をもたらします。次の問題の効率的なアルゴリズムを開発するのに問題があります。x+y、x --y、y + z、y --z、x + zとなるように、3つの正の数x、y、zの組み合わせを見つける必要があります。 x-zは完全な正方形です。問題は、1から2,000,000の間のx、y、zのすべての組み合わせを見つけるアルゴリズムを開発することです。
現在、私は孫が生まれる前に確実に終わらないfor範囲内で使用しています。for
質問する
4889 次
2 に答える
4
次のような置換から始める基本的な考え方：
u = x + y
v = x - y
w = y + z
次に、x + y、x --y、y + z、y --z、x + z、およびx--zは次のようになります。
u, v, w, u - v - w, v + w, u - w [all have to be squares]
次に、別の置換、u =a²、v =b²、w =c²を使用すると、次のようになります。
a², b², c², a² - b² - c², b² + c², a² - c² [all have to be squares]
これで、すでに十分に高速である可能性のあるすべてのa、b、csを列挙できます。
さらなるアイデアは、最初にピタゴラストリプルを使用してすべてのb²、c²、b²+c²を 列挙し（mとnに置き換え、すべての互いに素（m、n）を列挙し、次にEuclid式を使用することによって）、次に与えられた（b、c ）同様の方法で（たとえば、a²--c²=x²をa²=x²+c²に変更し、トリプルを再度使用します）。
于 2013-03-11T13:50:52.977 に答える
0
BeniBelaの答えを拡張すると、
x + y = (x - z) + (y + z)
x + y = (x + z) + (y - z)
したがって、トリプレットは、斜辺が 2 つの異なる形式で表現できる場合にのみ有効です。(x - z) と (x + z) もピタゴラスのトリプレットの斜辺を形成することを観察することによって、さらにフィルタリングを行うことができます。
于 2013-03-11T15:35:27.237 に答える