0

ユーザーが数値「N」を入力すると、A ^ 5 + B ^ 5 + C ^ 5 のすべての可能な値を見つけるアルゴリズムを作成しようとしています。

たとえば、N=100 の場合、配列の各スロットに A^5 + B^5 + C^5 の 1 ～ 100 の数字を差し込むことで見つかった数字が含まれる、すべての可能な値を含む配列を作成したい. したがって、配列内の位置の 1 つには (1^5 + 1^5 + 1^5) の 1 が含まれます。配列内の別の位置には、数値 355447518 (19^5 + 43^5 + 46^5 から) が含まれています。したがって、配列には 100^3 要素が含まれます。

public long[] possibleValues(int n)
{

    long[] solutionSet = new long[(int) Math.pow(n, 3)];

    for(int i=1;i<=n;i++)
    {
        solutionSet[i] = ((long) Math.pow(i, 5) + (long) Math.pow(i, 5) + (long) Math.pow(i, 5));

       //testing purposes
        System.out.println(i +"^5 " + "+" + i+"^5 " + "+" + i+"^5" + "=" + solutionSet[i]);
    }


    return solutionSet;
}

それは私がこれまでに持っているものですが、私の問題は、Nのすべての順列を実行できないことです.Nのすべての可能な順列を取得する最良の方法は何ですか? これを必要以上に複雑にしていますか？可能なすべての (A、B、C) をどのように配置しますか?

4

8 に答える 8

2

ネストされた forloop を使用します。

index=0;
for (int i=1;i<=n;i++){
  for (int j=1;i<=n;j++){
    for (int k=1;i<=n;k++){

       solutionSet[index++] = ((long) Math.pow(i, 5) + (long) Math.pow(j, 5) + (long) Math.pow(k, 5));
    }
  }
}

N までのすべての 5 乗を含む配列を使用すると、すべてのべき乗をすばやく計算できます。

于 2013-09-25T15:23:09.600 に答える
1

3 つの項すべてにを使用iしているため、基本的に の順列を計算しています
A^5 + A^5 + A^5 = 3A^5。

3 次元配列と 3 つの for ループが必要です。

public long[][][] possibleValues(int n)
{
    long[][][] solutionSet = new long[n+1][n+1][n+1];

    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    for(int k=1;k<=n;k++)
    {
        solutionSet[i][j][k] = ((long) Math.pow(i, 5) + (long) Math.pow(j, 5) + (long) Math.pow(k, 5));

       //testing purposes
        System.out.println(i +"^5 " + "+" + j+"^5 " + "+" + k+"^5" + "=" + solutionSet[i][j][k]);
    }

    return solutionSet;
}

実際に 1 次元配列のみが必要な場合は、上記と同様のことを行います。インデックス用に別の変数を用意するだけです。

おそらく値を過度に繰り返したくないので、おそらくjfromiとkfrom から始めることができますj。

public long[] possibleValues(int n)
{
    long[] solutionSet = new long[n*n*n];

    int c = 0;
    for(int i = 1; i <= n; i++)
    for(int j = i; j <= n; j++)
    for(int k = j; k <= n; k++)
    {
        solutionSet[c] = ((long) Math.pow(i, 5) + (long) Math.pow(j, 5) + (long) Math.pow(k, 5));

       //testing purposes
        System.out.println(i +"^5 " + "+" + j+"^5 " + "+" + k+"^5" + "=" + solutionSet[c]);
        c++;
    }

    return solutionSet;
}

いくつかの重要な最適化は引き続き実行できます。

  • Math.powピーターが言ったように、特に効率的ではありません。
  • 最初のバージョンでは、特定の状況で以前の値から値を導出できます。
于 2013-09-25T15:23:35.763 に答える
0

3 つのループを使用します。A、B、C にそれぞれ 1 つ。これは疑似コードであり、Java 構文に準拠していません。

for(int A:100){
  for(int B:100){
     for(int C:100) {
         calculate A^5 * B^5 * C^5
     }
   }
}
于 2013-09-25T15:22:59.447 に答える
0

それを行うための本当に強引な方法は、3 つのネストされたループを必要とします。

for(int a = 1; a <= n; ++a)
{
    for(int b = 1; b <= n; ++b)
    {
        for(int c = 1; c <= n; ++c)
        {
            // Add this combination to your array, and print it out.
            // It may be more convenient to use ArrayList instead of long[].
        }
    }
}

これには O(n^3) 時間がかかるため、計算に永遠にかかる前に n を非常に大きくする必要はありません (また、すべてのメモリを使い果たします)。

于 2013-09-25T15:23:08.960 に答える
0

順列ではなく組み合わせを探していると思います。また、A、B、および C を 1 から N までのすべての可能な値にしたいようです。その場合、ネストされた for ループをそのままにして、組み合わせのみを計算する必要があります。

for (int a = 0; a < n; a++) {
    for (int b = 0; b <= a; b++) {
        for (int c = 0; c <= b; c++) {
            pow5(a) + pow5(b) + pow5(c);
        }
    }
}

また、ファイルからロードできるルックアップ テーブルを使用することもできます。ルックアップ テーブルの値が多いほど、アルゴリズムの実行速度が速くなります。私の意見では、最善の方法は、必要な操作の数を減らすことです。つまり、実行時にすべての値を計算するわけではありません。または、メモリ使用量を最適化し、単純なアルゴリズムを使用することもできます。さらに、アルゴリズムのパフォーマンスを測定する必要があります。ここに例があります。

// for all number > 0 and <= 25
public static final double[] powersOf5 = {1.0, 32.0, 243.0, 1024.0, 3125.0,
7776.0, 16807.0, 32768.0, 59049.0, 100000.0, 161051.0, 248832.0, 371293.0,
537824.0, 759375.0, 1048576.0, 1419857.0, 1889568.0, 2476099.0, 3200000.0,
4084101.0, 5153632.0, 6436343.0, 7962624.0, 9765625.0};

// calc pow(i, 5) and use a lookup table for small values i
public static double pow5(int i) {
    if (i > 0 && i <= 25) {
        return powersOf5[i-1];
    } else {
        return Math.pow(i, 5);
    }
}

public static void main(String[] args) {
    long start = System.currentTimeMillis();

    for (int i = 0; i < 100; i++) {
        System.out.println(pow5(i));
    }

    long end = System.currentTimeMillis();

    System.out.println("Execution time: " + (end - start) + " ms");
}
于 2013-09-25T15:53:01.333 に答える
0

@Dukelingの以前の回答から始めて：私はpowers配列を使用してべき乗を計算しnます（ ではありませんn*n*n）

public static void test(int n){
    long[] powers = new long[n+1];
    for (int i=0; i<powers.length; i++)
        powers[i] = (long) Math.pow(i, 5);

    long[][][] solutionSet = new long[n+1][n+1][n+1];

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
            {
                solutionSet[i][j][k] = ((long) powers[i] + (long) powers[i] + (long) powers[i]);

               //testing purposes
                System.out.println(i +"^5 " + "+" + j+"^5 " + "+" + k+"^5" + "=" + solutionSet[i][j][k]);
            }
}
于 2013-09-25T15:45:51.227 に答える
0

最初に考える

1. 1^5 + 2^5 + 3^5 = 3^5 + 2^5 +1^5 , So i<j<k
 for(i=0;i<N;i++)
  for(j=i;j<N;j++)
    for(k=j;k<N;k++)


2.  A^5+B^5+C^5=D^5+E^5+F^5
    If we use array , there may be lots of same value in it.
    we can use Set to save memory, if time is not the most important.

3.  A^5 cannot be saved by Long type, when A is too big.
    So, do we make sure N is little? otherwise, there may be a bug.

4.  Multiplication cost lots of time.
    Give a example, if N=100, to get all result, how many times does it spend
    calc 5^5.
    5^5+1^5+1^5
    5^5+1^5+2^5
    5^5+1^5+3^5
    ...
    How about if there is an array save the answer
    define array[i] = i^5
    Then it save our time;

もっと考えてみれば、アルゴリズムはこういうもの

それでは、Math.pow(); について詳しく説明しましょう。

はい、それはあなたを助ける良い方法ですが、これはimplのアルゴリズムです.A^NではなくA^5を知りたいだけです.2番目のパラメータは静的です;

自分でメソッドを実装してみませんか。

まず、このようなメソッドを実装しようとします

public Long powOf5(Long A){
   return A*A*A*A*A;
}

次に、それを最適化できることがわかりました。

public Long powOf5(Long A){
   Long A2 = A*A;
   return A2*A2*A;
}

これは 3 倍、あれは 4 倍です。

このメソッドは Math.pow() よりも高速であると確信しています

于 2013-09-25T16:03:38.287 に答える