0

我正在尝试编写一个算法，当用户输入数字“N”时，该算法将找到 A^5 + B^5 + C^5 的所有可能值。

例如，如果 N=100 我想创建一个包含所有可能值的数组，其中数组中的每个插槽都包含一个数字，该数字是通过插入 1-100 之间的数字 A^5 + B^5 + C^5 找到的. 所以数组中的一个位置包含来自 (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 的所有五次方的数组来更快地计算所有次方。

于 2013-09-25T15:23:09.600 回答
1

您正在使用i所有 3 个术语，因此您实际上是在计算
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;
}

如果您确实只想要一个一维数组，您将执行与上述类似的操作，只需为索引设置一个单独的变量：

由于您可能不希望过度重复值，因此您可能可以j从.ikj

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

我同意关于嵌套 forloops 的其他答案。为了获得更好的性能，将答案存储在哈希表中可能是有利可图的，这样您就不会重新计算相同的值。例如，您计算 15^5，然后将该答案存储在 ans['155'] = 759375 之类的数组中。因此，当您再次计算 15^5 时，您可以执行 if 语句 if(ans[num.tostring+' 5']) 然后使用该值而不是再次计算 15^5。

于 2013-09-25T15:36:09.240 回答
0

使用三个循环。A、B、C 各一个。这是伪代码，不符合 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

真正的蛮力方法需要三个嵌套循环：

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

从@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

我相信您正在寻找组合而不是排列。您似乎还希望 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

先想想

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^5，而不是 A^N，第二个参数是静态的；

为什么不自己实现一个方法。

首先，我们尝试实现这样的方法

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 回答