Algoritimo complicado

Tu faz construção e analise de algoritmos na PUCRS né.

Cara, tenta pensar assim:

1…X…tamRua
|-------------------------|
…Sn…Sn

x seria o numero da confeitaria, onde a soma do numero de todas as casas antes dela é igual a soma do numeros das casas depois dela.

Os numeros sao uma PA que varia de 1 em 1, pega a formula da soma de todos os termos da PA e iguala uma com a outra depois isola o X.

O problema é que você tem um loop infinito nas linhas 26 a 29, e dentro desse loop você faz um append no StringBuilder. Assim, você vai alocando memória até ela se esgotar.

Se fosse em C no Win98 era tela azul …

FelipeRs:

Tu faz construção e analise de algoritmos na PUCRS né.

Cara, tenta pensar assim:

1…X…tamRua
|-------------------------|
…Sn…Sn

x seria o numero da confeitaria, onde a soma do numero de todas as casas antes dela é igual a soma do numeros das casas depois dela.

Os numeros sao uma PA que varia de 1 em 1, pega a formula da soma de todos os termos da PA e iguala uma com a outra depois isola o X.

É aquela velha matemática de colegial que faz falta. Meia dúzia de continhas e o algoritmo sai fácil fácil, e em tempo constante!

humm!

Bah mew esse troço eh mto foda!
Vou tentar com essas dicas, se tiverem alguma formula ql qr coisa q poderá me ajudar eu aceito!

vlw!

FelipeRs:

Tu faz construção e analise de algoritmos na PUCRS né.

Cara, tenta pensar assim:

1…X…tamRua
|-------------------------|
…Sn…Sn

x seria o numero da confeitaria, onde a soma do numero de todas as casas antes dela é igual a soma do numeros das casas depois dela.

Os numeros sao uma PA que varia de 1 em 1, pega a formula da soma de todos os termos da PA e iguala uma com a outra depois isola o X.

Não existe nenhuma restrição sobre o tamanho da rua ? Pois pelo que pude perceber, não é para todo tamanho de rua que o problema tem solução …

Se a tela azul se limitasse a Win98 e a C seria tão bom…

rmendes08:

FelipeRs:

Tu faz construção e analise de algoritmos na PUCRS né.

Cara, tenta pensar assim:

1…X…tamRua
|-------------------------|
…Sn…Sn

x seria o numero da confeitaria, onde a soma do numero de todas as casas antes dela é igual a soma do numeros das casas depois dela.

Os numeros sao uma PA que varia de 1 em 1, pega a formula da soma de todos os termos da PA e iguala uma com a outra depois isola o X.

Não existe nenhuma restrição sobre o tamanho da rua ? Pois pelo que pude perceber, não é para todo tamanho de rua que o problema tem solução …

É para ver se tem uma confeitaria com o tamanho da rua variando de 1 até 400 milhões, alguns tamanhos de rua nao possuem confeitaria. Faz uns dias que nao trabalho mais nesse algoritmo mas antes eu tava com um problema pra guardar os numeros, double estoura rapidinho.

FelipeRs:

rmendes08:

FelipeRs:

Tu faz construção e analise de algoritmos na PUCRS né.

Cara, tenta pensar assim:

1…X…tamRua
|-------------------------|
…Sn…Sn

x seria o numero da confeitaria, onde a soma do numero de todas as casas antes dela é igual a soma do numeros das casas depois dela.

Os numeros sao uma PA que varia de 1 em 1, pega a formula da soma de todos os termos da PA e iguala uma com a outra depois isola o X.

Não existe nenhuma restrição sobre o tamanho da rua ? Pois pelo que pude perceber, não é para todo tamanho de rua que o problema tem solução …

É para ver se tem uma confeitaria com o tamanho da rua variando de 1 até 400 milhões, alguns tamanhos de rua nao possuem confeitaria. Faz uns dias que nao trabalho mais nesse algoritmo mas antes eu tava com um problema pra guardar os numeros, double estoura rapidinho.

E você chegou a fazer a igualdade entre as somas de PAs ? Eu fiz aqui em casa e cheguei em uma equação de 2 grau, acho que era 2x^2 + x - N^2 + 1 = 0, onde N era o tamanho da rua, por isso eu perguntei …

rmendes08:

FelipeRs:

rmendes08:

FelipeRs:

Tu faz construção e analise de algoritmos na PUCRS né.

Cara, tenta pensar assim:

1…X…tamRua
|-------------------------|
…Sn…Sn

x seria o numero da confeitaria, onde a soma do numero de todas as casas antes dela é igual a soma do numeros das casas depois dela.

Os numeros sao uma PA que varia de 1 em 1, pega a formula da soma de todos os termos da PA e iguala uma com a outra depois isola o X.

Não existe nenhuma restrição sobre o tamanho da rua ? Pois pelo que pude perceber, não é para todo tamanho de rua que o problema tem solução …

É para ver se tem uma confeitaria com o tamanho da rua variando de 1 até 400 milhões, alguns tamanhos de rua nao possuem confeitaria. Faz uns dias que nao trabalho mais nesse algoritmo mas antes eu tava com um problema pra guardar os numeros, double estoura rapidinho.

E você chegou a fazer a igualdade entre as somas de PAs ? Eu fiz aqui em casa e cheguei em uma equação de 2 grau, acho que era 2x^2 + x - N^2 + 1 = 0, onde N era o tamanho da rua, por isso eu perguntei …

Sim, eu fiz a igualdade mas ficou um pouco diferente, fica x^2 = (n^2 + n) /2, vc sabe um jeito de fazer operaçoes com numeros gigantesco com casas decimais no java ?

Depende do seu problema, se o problema for precisão e/ou magnetude, você pode utilizar BigDecimal, mas é mais pesado e consome mais memória. Agora se o problema for o estouro de memória então o problema é o algoritmo mesmo e não tem jeito, tem que otimizar.

Parece até um daqueles problema do TopCoder ou da Maratona de Programação ACM.

É o trabalho final da cadeira de construçao e analise de algoritmos da PUCRS, acho que vou ter que fazer em C ai da pra usar unsigned long long int.

É o trabalho final da cadeira de construçao e analise de algoritmos da PUCRS, acho que vou ter que fazer em C ai da pra usar unsigned long long int.

E qual é o tamanho desse tipo em C ? Só é vantagem se for pelo menos 64 bits sem sinal.

HAHA, mais uma dica, nada de numeros extraordinariamente grandes soh podera ser usado int’s

Mas aí é que tá … o quão grande pode ser esse int ? O tamanho do tipo depende da linguagem e da plataforma … em Java é sempre 32 bits, em C pode ser 16 ou 32, dependendo da plataforma

Tenho quase certeza que da pra fazer com long long int sim, se nao vou ter que apelar pra String.

Tenho quase certeza que da pra fazer com long long int sim, se nao vou ter que apelar pra String.

String ?

Tenho quase certeza que da pra fazer com long long int sim, se nao vou ter que apelar pra String.

String ?

Essa eu roubei do entanglement, http://www.guj.com.br/posts/list/200693.java

Tenho quase certeza que da pra fazer com long long int sim, se nao vou ter que apelar pra String.

String ?

Essa eu roubei do entanglement, http://www.guj.com.br/posts/list/200693.java

Essa String me embrulhou mais ainda!

PS.: o int que eu falo eh 32 bits, programo em JAVA!

Ainda to penando aki gente, estacionei e não consigo sair desse lugar!

Meu algoritimo hoje:

package Teste;
public class Teste {

    public int somaMen(int i){
       return ((i+1)*i)/2;
    }
    
    public int somaMai(int i, int j){
        int maiores =0;
        for(int g = i+1; g>i && g<j; g++){
            maiores += g;
        }
        return maiores;
    }

    public String confeitaria(){
        StringBuilder sb = new StringBuilder();
        for(int tamRua = 0; tamRua < 400000000; tamRua++){
            for(int i = 0; i < tamRua; i++){
                for(int j = i; ;j++){
                    if(somaMen(i) == somaMai(j,tamRua))
                        sb.append(j);
                }
            }
        }
        return sb.toString();
    }

    public static void main (String[] args){
        Teste t = new Teste();
        t.confeitaria();
        //System.out.println(t.somaMen(5));
    }
}

ainda ta estourando a memoria, Vocês tem alguma ideia de como fazer isso com inteiros (int) de 32 bits?

Acho que o primeiro passo é colocar o metodo somaMai() em uma formula matematica certo?

Se puderem me ajudar eu agradeço muito!

Galera andei trabalhando um pouco nesse algoritimo, mas soh consegui isso:

package Teste;
public class Teste {

    public int somaMen(int i){
       return ((i+1)*i)/2;
    }
    
    public int somaMai(int i, int j){
        return (1+1)*(j-i);
//        int maiores =0;
//        for(int g = i; g<=j; g++){
//            maiores += g;
//        }
//        return maiores;
    }

    public String confeitaria(){
        StringBuilder sb = new StringBuilder();
        for(int tamRua = 0; tamRua < 400000000; tamRua++){
            for(int i = 0; i < tamRua; i++){
                for(int j = i; ;j++){
                    if(somaMen(i) == somaMai(j,tamRua))
                        sb.append(j);
                }
            }
        }
        return sb.toString();
    }

    public static void main (String[] args){
        Teste t = new Teste();
       // t.confeitaria();
        System.out.println(t.somaMen(6));
        System.out.println(t.somaMai(6,8));
    }
}

Galera meu problema ta no segundo metodo, não consigo achar uma formula matematica pra ele, to enlouquecendo com isso!

ah mais uma duvidasinha!

Tipo o metodo "confeitaria()" deve percorrer o laço pegando cada proximo numero e vendo se a soma de todos numeros anteriores é igual a soma de todos proximos numeros (que deve ser o tamanho do laço atual, onde especifico com o tamRua) Isso ta funcionando? tem algum bug?

Poderiam dar uma olhadinha?
Brigadão mesmo!
PS.: o metodo somaMai(int, int) soh funciona com o laço