克服堆溢出问题

Question

我试图解决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;
        }
    }
}

这是编辑过的代码,像gem一样工作:

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;
        }
    }
}

Answer 1

作为Project Euler建议的一般部分,如果您的解决方案无法扩展,那么几乎可以肯定有更好的方法来解决它.如果您在早期问题上使用了相同类型的解决方案,则可以通过前面问题的其他用户发布帖子,以获得以不同方式解决问题的想法.