Superar problemas de estouro de pilha

votos
4

Tentei resolver problemas de projeto Euler. Eu sei que o meu método iria funcionar logicamente (ele retorna respostas para o problema de pequena escala quase que instantaneamente). No entanto, ele pode ser expandido horrivelmente. Já tentou alterar o arquivo ini, mas sem sucesso.

Aqui está o meu código:

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

Aqui está o código editado, funcionou como uma jóia:

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;
        }
    }
}
Publicado 19/05/2009 em 18:07
fonte usuário
Em outras línguas...                            


4 respostas

votos
5

Como um pedaço geral do conselho Projeto Euler, se a sua solução não escala, há quase certamente a melhor maneira de resolvê-lo. Se você já usou o mesmo tipo de solução em um problema mais cedo você pode percorrer as mensagens de outros usuários sobre a questão antes de obter ideias para resolver o problema de diferentes maneiras.

Respondeu 19/05/2009 em 18:14
fonte usuário

votos
4

Não está familiarizado com os problemas de Euler, mas o horror parece ser sua alocação contínua e re-alocação de quais são espirais intermediárias basicamente descartáveis, como você chama para baixo de forma recursiva para o caso base.

Reestruturar de modo que você alocar seu espiral completo na frente. Em seguida, chamar a função recursiva, passando a sua espiral cheia como um parâmetro por referência, juntamente com um parâmetro "nível", que vai mudar com cada chamada recursiva. Por exemplo, chamada inicial é com 100x100 espiral eo nível 100; próxima chamada (recursiva) é com a mesma espiral, por referência, e de nível 98. Operações dentro da função tudo será feito na espiral one-and-only-alocado.

Em poucas palavras: alocar sua estrutura de dados uma vez, mesmo se você operar em que a estrutura de dados de forma recursiva.

Respondeu 19/05/2009 em 18:24
fonte usuário

votos
0

Aqui está uma solução simplificada que não armazena uma matriz:

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

}

Explicação:

Partindo 1você pode ver 4 somas:

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

1é adicionado 4 vezes, é por isso que o valor padrão para sumé -3.

Vamos juntar esses montantes:

  • 24 + 4 + 76 + 160 + 276 + ... (é por isso que firsté 4e ré 20= 24-4)

É possível observar que raumenta de 32acordo com o passo (24-4 = 32 + 76-24 = 32 + 32 + 160-76 = ...) e o número real ( first) aumenta pela r.

Respondeu 05/12/2014 em 23:00
fonte usuário

votos
0

O primeiro problema que eu vi foi um NegativeArraySizeException ao executar o seu programa com SIZE = 100. Eu acho que isso tem algo a ver com a forma como cada chamada recursiva é diminuir o tamanho por 2.

Eu acredito que o comentário de Steven está certo sobre o dinheiro. Você está alocando o tamanho da matriz, eles fazer uma chamada recursiva. Isso faz com que (SIZE - 1) número de matrizes para ser a atribuição, comendo toda a sua memória. Removendo que uma linha deve evitar qualquer memória seja alocada até que seja necessário.

Respondeu 19/05/2009 em 18:28
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more