25

解決策を見つけるためのアルゴリズムまたはコーディングのヒントを探す

a^3 + b^3 = c^3 + d^3、a, b, c and dすべてが範囲内にある場合[1 .. 10000]

面接の質問です。

優先度キューは、少なくともaと のb値を反復することを考えています。いくつかのヒントは素晴らしいでしょう、そこからやり遂げようとします.

4

9 に答える 9

23

ハッシュ マップを使用して を格納する(cube,(a,b))と、可能なすべての整数のペアを反復処理し、必要なキューブの合計が既にマップにあることがわかったら、解を出力できます。

擬似コード:

map <- empty hash_map<int,list<pair<int,int>>>
for each a in range(0,10^5):
  for each b in range(a,10^5): //making sure each pair repeats only once
     cube <- a^3 + b^3
     if map.containsKey(cube):
         for each element e in map.get(cube):
            output e.first(), e.last(), a, b //one solution            
     else:
         map.put(cube,new list<pair<int,int>>)
     //for both cases, add the just found pair to the relevant list
     map.get(cube).add(cube,new pair(a,b))

このソリューションは、平均で O(n^2) スペース(1)と O(n^2 + OUTPUT) 時間です。ここで、OUTPUT は出力のサイズです。

編集：

必要なスペースは実際O(n^2 logn)には です。ここnで、 は範囲 (10^5) です。整数を表すにはビット10^5が必要だからです。ceil(log_2(10^15)) = 50したがって、実際には 500,000,000,000 ビット (+ マップとリストのオーバーヘッド) が必要で、これは ~58.2 GB (+ オーバーヘッド) です。

ほとんどのマシンでは少し多すぎるため、データをディスクに保存することを検討するか、64ビットマシンを使用している場合は、「メモリ」に保存して、OSと仮想メモリシステムにこれを最善の方法で実行させますできる。

(1) 編集が明確にするように、実際にはO(n^2log(n))スペースですが、各整数ストレージをO(1)(通常はそうです) と見なすと、O(n^2)スペースが得られます。明らかに、同じ原則が時間の複雑さに適用されます。

于 2013-01-22T09:36:01.970 に答える
6

プライオリティ キューを使用することは、ほぼ確実に最も簡単なソリューションであり、最も実用的なソリューションでもあります。これは、O(n) ストレージ (bignum が必要な場合はログ ファクターを使用) であるためです。すべての可能な合計を計算してマップに配置することを含むソリューションは、O(n^2) ストレージを必要とし、すぐに非現実的になります。

プライオリティ キューを使用した私の単純で最適化されていない実装は、O(n^2 log(n)) 時間です。それでも、数メガバイトのストレージを使用して、n = 10000 の場合は 5 秒未満、n = 100000 の場合は約 750 秒かかりました。それは確かに改善される可能性があります。

あなたのコメントによると、基本的な考え方は、範囲 [1, N) の a のペア (a, a+1) でプライオリティ キューを初期化し、最小値の 2 番目の値を (キューブの合計で) 繰り返しインクリメントすることです。 ) タプルを N に達するまで繰り返します。キュー内の最小の 2 つの要素が等しい場合はいつでも、解があります。(コードを貼り付けることができましたが、あなたはヒントを求めただけです。)

于 2013-01-22T17:36:48.570 に答える
4

ハッシュマップの使用 (O(n^2) ソリューション): 

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

import static java.lang.Math.pow;

/**
 * Created by Anup on 10-10-2016.
 */

class Pair {
    int a;
    int b;

    Pair(int x, int y) {
        a = x;
        b = y;
    }
}

public class FindCubePair {
    public static void main(String[] args) {
        HashMap<Long, ArrayList<Pair>> hashMap = new HashMap<>();
        int n = 100000;

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                long sum = (long) (pow(i, 3) + pow(j, 3));

                if(hashMap.containsKey(sum)) {
                    List<Pair> list = hashMap.get(sum);
                    for(Pair p : list) {
                        System.out.println(i + " " + j + " " + p.a + " " + p.b);
                    }
                } else {
                    ArrayList<Pair> list = new ArrayList<>();
                    hashMap.put(sum, list);
                }

                hashMap.get(sum).add(new Pair(i, j));
            }
        }
    }
}

残念ながら、リソースの制限により、印刷された整数の値は私のコンピューターでは 1000 にも達しません。

于 2016-10-10T17:42:25.410 に答える
2

自明ではない解決策は次のとおりです。a^3 + b^3 が持つことができるすべての値を計算し、それを使用して a と b のすべての可能な値を保存します。これは、a と b をループして、結果 (a^3 + b^3) をバイナリ ツリーに格納し、各結果に関連付けられた値 (a と b) のリストを作成することによって行われます。

このステップの後、リストをトラバースし、各値について、a、b、c、d のすべての可能な割り当てを選択する必要があります。

このソリューションには O(n^2 log n) の時間と O(n^2) のスペースが必要だと思いますが、何か不足している可能性があります。

于 2013-01-22T09:16:15.747 に答える
1

解決策を考えてみましょう：

a=A, b=B, c=C, and d=D.

任意のソリューションが与えられると、別の3つのソリューションを生成できます

abcd
ABCD

ABDC
BACD
BADC

実際、、、A=Bまたはの場合、C=Dさらに1つまたは2つのソリューションしかない可能性があります。

A <= B注文して最初に探すソリューションを選択できますC <= D。これにより、検索スペースが削減されます。見つかったソリューションから、見逃したソリューションを生成できます。

常に少なくとも1つの解決策があります。ここでA=CとB=D。私たちが探しているのは、いつA>C、そしてB<D。これは順序付けに由来します。これCより大きくすることはできません。これはA、ソリューションのみを確認することを選択したためD>C、キューブの合計が大きすぎるためです。

を計算し、それをキーとして、ペアの値を値としてA^3 + B^3入れることができます。mapvectorA,B

値があり(n^2)/2ます。

すでに値が含まれている場合、vectorそれらはすべて低くAなり、私たちが探しているソリューションです。それらを順列とともにすぐに出力できます。

複雑さについてはよくわかりません。

于 2013-01-22T09:41:50.133 に答える
1

1つの解決策 - ソートされた配列で2つの合計を見つけるという概念を使用します。これは O(n3)

public static void pairSum() {
    int SZ = 100;
    long[] powArray = new long[SZ];
    for(int i = 0; i< SZ; i++){
        int v = i+1;
        powArray[i] = v*v*v;
    }
    int countPairs = 0;
    int N1 = 0, N2 = SZ-1, N3, N4;
    while(N2 > 0) {
        N1=0;
        while(N2-N1 > 2) {
            long ts = powArray[N1] + powArray[N2];
            N3 = N1+1; N4 = N2-1;
            while(N4 > N3) {
                if(powArray[N4]+powArray[N3] < ts) {
                    N3++;
                }else if(powArray[N4]+powArray[N3] > ts) {
                    N4--;
                }else{
                    //System.out.println((N1+1)+" "+(N2+1)+" "+(N3+1)+" "+(N4+1)+" CUBE "+ts);
                    countPairs++;
                    break;
                }
            }
            N1++;
        }
        N2--;
    }
    System.out.println("quadruplet pair count:"+countPairs);
}
于 2016-09-09T15:30:52.880 に答える