7

c斜辺 (典型的な方程式)が与えられた場合、とa*a + b*b = c*cのすべての可能な整数値を計算する効率的な方法はa何bですかa < b?

注: 私はよりcも大きい1e12を見てきました。c*clong.MaxValuec*cdecimal

4

5 に答える 5

7

すべてのピタゴラス数 (a、b、c) は、ある整数 k、m、n に対して、

a=k(m^2-n^2)、b=2kmn、c=k(m^2 + n^2)

なので、因数分解から始めましょう。次に、c のすべての別個の因子 k (つまり、因子のすべての別個のサブセットを掛け合わせたもの) について、c/k = (m^2 + n^2) を満たすすべての m と n を見つけます。後者を行うと、他の人が提案した力ずくのアプローチよりも大幅に時間がかかりません (c^2 ではなく、合計が c/k になる平方を見つけるだけで済みます) が、すべてのトリプル (a、b、c) を識別します。 . 中間結果はすべて long に収まるため、bignum を使用する必要もありません。

また、Web ページhttp://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Pythag/pythag.htmlの「A more general Pythagorean Triple Calculator」という見出しの下をチェックすることをお勧めします。あなたが望むことを正確に行うJavaScriptで書かれた埋め込み電卓。

于 2010-01-28T04:46:12.533 に答える
6

c の値が大きい場合でも、a と b をすばやく見つける数学的解があります。残念ながら、それはそれほど単純ではありません。アルゴリズムの簡単な説明をしようとしています。あまり混乱しないことを願っています。

c が与えられ、a と b を探しているので、基本的に次の形式のディオファントス方程式を解きたいと考えています。

n=x^2+y^2,

ここで n が与えられます。n = c*c が正方であることはあまり役に立たないので、任意の n の解を説明しています。n が素数 の場合、フェルマーの定理を使用して、方程式が解けるかどうかを判断し、Moron が指摘したように Hermite-Serret アルゴリズムを使用して、解がある場合は解を見つけることができます。

n が素数でない場合を解決するには、 ガウス整数を使用することをお勧めします。(ガウス整数は整数係数を持つ単なる複素数です)。特に、x+yi のノルムは

N(x+yi) = x^2+y^2.

したがって、ノルムが n であるガウス整数 x+yi を見つけなければなりません。ノルムは乗法であるため、この方程式を因数 n について解いてから、個々の方程式のガウス整数を掛ければ十分です。例を挙げましょう。解決したい

65 = x^2 + y^2.

これは、次のような x,y を見つけることと同じです。

N(x+yi) = 65

ガウス整数上。65 = 5 * 13 を因数分解し、フェルマーを使用して、5 と 13 の両方が 2 つの平方和として表現できることに注意します。最後に、Hermite-Serret アルゴリズムを使用して、総当りを使用していずれかを見つけます。

N(2+i) = N(1+2i) = ... = 5
N(2+3i) = N(3+2i) = ... = 13

負の係数を持つ Gaussion 整数 2-i、-2+i などを除外したことに注意してください。もちろん、それらも解決策です。

したがって、これらのソリューションを掛け合わせて、

65 = 5*13 = N(2+i) * N(2+3i) = N((2+i) * (2+3i)) = N(1 + 8i)

と

65 = 5 * 13 = N(2+i) * N(3+2i) = N((2+i) * (3+2i)) = N(4 + 7i)。

したがって、2つの解が得られます

1*1 + 8*8 = 65
4*4 + 7*7 = 65

負の係数など、その他の組み合わせもチェックする必要があります。彼らは、順列と記号の変更以外の新しい解決策を提供しません。

すべての解を計算するには、c*c を計算する必要がないことを追加することもできます。c の因数を見つけるだけで十分です。また、a と b はどちらも c よりも小さいため、ガウス整数の積が 64 ビット整数係数で表現できないということは起こりません。したがって、注意すれば、64 ビット整数は問題を解決するのに十分な精度です。もちろん、この種のオーバーフローの問題がない Python のような言語を使用する方が常に簡単です。

于 2010-01-28T09:39:57.600 に答える
0

a の値は 1、b の値は c から始めます。

と比較c*c - b*bしてくださいa*a。それらが等しい場合は、一致しています。

どちらの辺が大きいかに応じて、a と b を同じになるまで変更します。

于 2010-01-28T01:24:28.593 に答える
0

BigNum ライブラリを使用することもできます。

a と b を見つける効率的な方法については、次のとおりです。

b の各値 (c-1 から始まり、b * b < c * c / 2 まで) について、c * c - b * b を計算し、それが完全な正方形かどうかを確認します。

于 2010-01-28T01:17:29.910 に答える
0

与えられた交流：

b > a なので、a が最小 (a = 1) の場合、b = sqrt(c*c - 1) となります。

したがって、b はその値と c -1 の間でなければなりません。

また、b は整数でなければならないため、これが整数である最初の値を見つける必要があります。

Now, a property of squares:
The squares are: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, ...
The differences: -, 3, 5, 07, 09, 11, 13, 15, 17, 019, 021, ...
That means a square can be written as a summation of ODD numbers:
    1 + 3 + 5 + 7 + n+...
where n = number the summation is a square of.

したがって、c*c より小さい平方数は正確に c 個あり、単純な減算を使用してそれらを特定できます。

最初に戻って、b = sqrt(c c - 1) を取り、切り捨てて b b を取ると、2 乗 b が上でなければならず、a a = 1 が得られます。c c - ( a a + b b)を見つけます。これにより、c*c を達成するために追加する必要がある数値が得られます。

3 + 5 + 7 + ...aとb に加算できるb+2 + b+4 + b+6 + ...ので、平方自体ではなく和に基づいて適切な項を見つける必要があります :)

于 2010-01-28T02:09:48.853 に答える