0

基本的にA^5 + B ^ 5 + C ^ 5 + D ^ 5 + E ^ 5 = F^5である5-1の5次ディオファントス方程式を解くコードを書くプログラムがあります。ここで0<A< = B <= C <= D <= E <= F <=N。これを実装する方法は、指定されたN値の値を事前に計算してから、配列に格納することです。したがって、たとえばNが100の場合、1から100までの値が配列に格納されます。

次に、最初のグループA ^ 5 + B ^ 5 + C^5と2番目のグループF^5-（D ^ 5 + E ^ 5）の値を計算し、最初のグループの値を比較します。それらが一致するかどうかを確認するために秒に。一致する場合、解決策が見つかります。

私の質問は、1からNまでの値の配列を使用して、2つのグループのすべての可能な値をどのように計算するのかということです。私は考えを理解していますが、それをコーディングすると、どのようにアプローチするかわかりません。誰かが私にいくつかのヒントを教えてもらえますか？私はそれをコーディングする方法についての解決策を求めているのではなく、コーディングプロセスをもう少しよく理解するのに役立ついくつかのヒント/ヒントが欲しいだけです。ありがとう！

4

3 に答える 3

4

私は間違いなく、1からNまでのすべての数値の5次値をすべて計算することから始め、次にF ^ 5-（A ^ 5 + B ^ 5 + C ^ 5 + D ^ 5 + E ^ 5）、

1）外部ループ、F ^ 5の値を生成します。幸い、Fの最小値は72であることがわかっています。Landerand Parkin（1967）

残りのループは最小値で始まります。

2）2番目のループ、E^5の値を生成します

3）3番目のループ、D ^ 5の値を生成し、F ^ 5の値をテストします-（D ^ 5 + E ^ 5）負の場合、このループを中断できます（ただし、外側のループは中断できません）

残りの3つの値について、残りの3つのループを続行します。方程式の場合、各ループのテスト値はますます少なくなります。方程式が負になるか、すでに使用されている数値に達するたびに停止できるためです。

方程式がゼロに等しい解はすべて解です。

時間分析は困難です。N^2の場合、最初の2つのループが発生しますが、残りの4つのループははるかに小さくなります。

n=600でテストしました。これは
218^5 + 276 ^ 5 + 385 ^ 5 + 409 ^ 5 + 495 ^ 5 = 553 ^5の最大の解を持ちます。N^6方程式は4E16ステップでこの解に到達し、私のものは2E15または5で到達します。時間の％。

これでn^3lognになるかどうかはわかりませんが、大量の誤ったソリューションをスキップすることで、はるかに近づくことができます。

于 2012-11-10T18:07:01.710 に答える
2

より良い解決策は、最初にすべての5次値を生成し、それらを配列に格納することです。

次に、3つのネストされたループを使用して、F ^ 5-E ^ 5-D ^ 5のすべての組み合わせを生成し、これらすべての組み合わせを保存します

次に、3つの異なるネストされたループを使用して、A ^ 5 + B ^ 5 + C ^ 5のすべての組み合わせを生成し、これらすべての値を格納します。

2つのネストされたループを使用して、F ^ 5-E ^ 5-D^5とA^5 + B ^ 5 + C^5の値を比較します。それらが同じである場合、あなたは解決策を持っています。a、b、c、d、e、およびfの対応する値を出力します。

3つのネストされたループの2つのペアのみを使用します。このソリューションは、O（3n）でない場合はO（3nlogn）になります

于 2012-11-11T01:08:53.553 に答える
1

@Gregoryソリューションに対する小さな改善は、あちこちでいくつかの値を削ることです。

1.1。

各文字が前の文字よりも小さいことがわかっているので、与えられた方程式が負のときに停止する必要がある理由がわかりません。その場合、たとえば、最初の2つのループは（N ^ 2/2）ステップを実行する必要があります。

2.2。

2番目のサイクル（E）では、次の事実を考慮することができます。

F^5 =  A^5 + B^5 + C^5 + D^5 + E^5 < 5*E^5

したがって、サイクルでEは0から開始する必要はありませんが、最初E に開始することができます。

5*E^5 > F^5

に移動しF-1ます。

3番目のサイクル（D）では、上記と同様の不等式があります

 F^5 - E^5 = A^5 + B^5 + C^5 + D^5 < 4^D5

Dそして、この条件を満たす最初のもののテストを開始する必要があります。

同じことが残りの内部サイクルにも当てはまります。

これはそれほど多くはないように見えますが、同じアイデアがいくつかの競争問題に役立ちました。

于 2012-11-17T01:09:27.193 に答える