4

我试图从 Project Euler 中解决问题。我知道我的方法会合乎逻辑地工作（它几乎可以立即返回小规模问题的答案）。但是，它的扩展非常可怕。我已经尝试更改 .ini 文件，但无济于事。

这是我的代码：

public class Number28 {

    static int SIZE = 101; //this should be an odd number, i accidentally posted 100
    /**
     * @param args
     */
    public static void main(String[] args) {
        double start = System.currentTimeMillis();
        long spiral[][]= spiral(SIZE);
        long sum = 0;
        for(int i = 0; i < SIZE; i++)
        {
            sum += spiral[i][i];
            sum += spiral[i][SIZE - 1 - i];
        }
        System.out.println(sum - 1);
        double time = System.currentTimeMillis() - start;
        System.out.println(time);

    }
    public static long[][] spiral(int size){
        long spiral[][]= new long[size][size];
        if(size == 1){
            spiral[0][0] = 1;
            return spiral;
        }
        else{
            long subspiral[][]= new long[size - 2][size - 2];
            subspiral = spiral(size - 2);
            for(int r = 0; r < size - 2; r++){
                for(int c = 0; c < size - 2; c++){
                    spiral[r + 1][c + 1] = subspiral[r][c];
                }
            }
            long counter = subspiral[0][size - 3];
            for(int r = 1; r < size ; r++){
                counter++;
                spiral[r][size - 1] = counter;
            }
            for(int c = size - 2; c >= 0; c--){
                counter++;
                spiral[size - 1][c] = counter;
            }
            for(int r = size - 2 ; r >= 0 ; r--){
                counter++;
                spiral[r][0] = counter;
            }
            for(int c = 1; c < size ; c++){
                counter++;
                spiral[0][c] = counter;
            }

            return spiral;
        }
    }
}

这是编辑后的代码，就像宝石一样工作：

public class Number28 {
    static int SIZE = 1001;
    static long spiral[][]= new long[SIZE][SIZE];

    /**
     * @param args
     */
    public static void main(String[] args) {
        double start = System.currentTimeMillis();
        long spiral[][]= spiral(SIZE);
        long sum = 0;
        for(int i = 0; i < SIZE; i++)
        {
            sum += spiral[i][i];
            sum += spiral[i][SIZE - 1 - i];
        }
        System.out.println(sum - 1);
        double time = System.currentTimeMillis() - start;
        System.out.println(time);

    }
    public static long[][] spiral(int size){
        if(size == 1){
            spiral[SIZE / 2][SIZE / 2] = 1;
            return spiral;
        }
        else{
            long subspiral[][]= spiral(size - 2);
            int edge = (SIZE - size) / 2;
            long counter = subspiral[edge + 1][edge + size - 2];

              for(int r = 1; r < size ; r++){
                  counter++;
                  spiral[edge + r][edge + size - 1] = counter;
          }
          for(int c = size - 2; c >= 0; c--){
                  counter++;
                  spiral[edge + size - 1][edge + c] = counter;
          }
          for(int r = size - 2 ; r >= 0 ; r--){
                  counter++;
                  spiral[edge + r][edge] = counter;
          }
          for(int c = 1; c < size ; c++){
                  counter++;
                  spiral[edge][edge + c] = counter;
          }
            return spiral;
        }
    }
}
4

4 回答 4

5

作为 Project Euler 的一般建议，如果您的解决方案无法扩展，几乎可以肯定有更好的方法来解决它。如果您在较早的问题上使用了相同类型的解决方案，则可以浏览其他用户在较早问题上的帖子，以获取以不同方式解决问题的想法。

于 2009-05-19T17:14:56.980 回答
4

不熟悉欧拉问题，但是当您递归调用基本情况时，恐怖似乎是您不断分配和重新分配基本上是一次性的中间螺旋的东西。

重组，以便您预先分配完整的螺旋。然后调用你的递归函数，通过引用将你的完整螺旋作为参数传递，以及一个“级别”参数，该参数将随着每次递归调用而改变。例如，初始调用是 100x100 螺旋和 100 级；下一个（递归）调用具有相同的螺旋，通过引用和级别 98。函数内的操作都将在唯一分配的螺旋上完成。

简而言之：分配一次数据结构，即使您递归地操作该数据结构。

于 2009-05-19T17:24:18.437 回答
0

我看到的第一个问题是在运行 SIZE = 100 的程序时出现 NegativeArraySizeException。我想这与每个递归调用如何将大小减小 2 有关。

我相信史蒂文关于钱的评论是正确的。您正在分配数组的大小，它们进行递归调用。这会导致 (SIZE - 1) 数量的数组被分配，占用你所有的内存。删除那一行应该可以防止在必要时分配任何内存。

于 2009-05-19T17:28:26.543 回答
0

这是一个不存储矩阵的简化解决方案：

public class P28 {

    private final static int N = 1001;

    public static void main(String[] args) {

        int limit = (N + 1) / 2;
        int sum = -3;
        int first = 4;
        int r = 20;
        for (int i = 1; i <= limit; i++) {
            sum += first;
            first += r;
            r += 32;
        }
        System.out.println(sum);
    }

}

解释：

从1你可以看到4个总和：

  • 1 + 3 + 13 + 31 + 57 + ...
  • 1 + 5 + 17 + 37 + 65 + ...
  • 1 + 7 + 21 + 43 + 73 + ...
  • 1 + 9 + 25 + 49 + 81 + ...

1sum加了 4 次，这就是为什么默认值为-3.

让我们收集这些总和：

  • 4 + 24 + 76 + 160 + 276 + ...（这就是为什么firstis4和ris 20= 24 - 4）

您可以观察到每一步r增加32（24-4 = 32 + 76 - 24 = 32 + 32 + 160 - 76 = ...），实际数字（first）增加r。

于 2014-12-05T23:00:10.637 回答