• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Djoblack

Duvida num labirinto

24 mensagens neste tópico

Boas, alguém já fez um labirinto em java?Se sim, como é que vocês representaram o labirinto?....Alguém pode dar-me uma dica????

Obs:não posso representar o labirinto com um array bidimensional....é aí que está a minha dificuldade,,,eu tenho outra maneira que não seja através do array bidimensiona de o representarl?? :D

Ajuda please

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Podes usar cadeias de objectos!!

Por exemplo tens classe Posição que tem um var que indica se é parede ou caminho, e tem quarto objectos Posição, ou seja a Posição, á esquerda, direita, frente e trás, assim crias cadeias de objectos e fazes o labirinto :D Se não fui suficientemente claro diz lol

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

hum,,,,tou a ver a ideia,,,mas em java como faço isso??.....nunca trabalhei com cadeia de objectos :D

Obrigado

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

assim simples simples seria algo tipo

public class Posicao{
    private int tipo; //0 para caminho 1 para parede
    private Posicao esq;
    private Posicao dir;
    private Posicao front;
    private Posicao back;

    public Posicao( int tipo, Posicao esq, Posicao dir, Posicao back, Prosicao front ){
        this.tipo = tipo;
        this.esq = esq;
        //....
    }
}

Depois podes meter mais coisas como posição etc... coisas para facilitar o trabalho mais tarde.

Para usar era só criar objectos deste e ligar, no caso de não haver esq ou dir ou front ou back seria só passar o argumento com null assim sabias que ao achar 1 null então não ai não havia labirinto.

Eu faria assim, parece-se o mais fácil e lógico mas devem haver outras formas.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Devia aprender bem OO antes de começar Java, é difícil explicar-te se não percebes o OO :\

Deixa lá ver se consigo

Imagina que o labirinto tem apenas 4 posições e são as 4 paredes, ou seja sem entrada nem saída, não tem lógica e eu mas é para ser simples de explicar.

Algo tipo:

11

11

ou seja

p1p2

p3p4

Então terias qq tipo :

//....

Posicao p1 = new Posicao(1,null,null,null,null);
Posicao p2 = new Posicao(1,p1,null,null,null);
Posicao p3 = new Posicao(1,null,null,p1,null);
Posicao p4 = new Posicao(1,p3,null,p2,null);

p1.setDir(p2);
p1.setFront(p3);
p2.setFront(p4)
p3.setDir(p4)

Até podias usar apenas os setDir ao invés dos construtores para não ficar tão confuso.

Assim podes percorrer tudo, com o p1 consegues ir para o p2 ou para o p3, depois deles podes ir para o outro, sempre andando para a esq, dir, frente ou trás :D Espero ter ajudado.

Acho que isto é meio complicado para quem não percebe OO  :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Boas, alguém já fez um labirinto em java?Se sim, como é que vocês representaram o labirinto?....Alguém pode dar-me uma dica????

Obs:não posso representar o labirinto com um array bidimensional....é aí que está a minha dificuldade,,,eu tenho outra maneira que não seja através do array bidimensiona de o representarl?? :D

Ajuda please

Achei um projecto engraçado, não queres por o enunciado aqui ?

Não me parece dificil .. Dava para fazer um jogo...

E quanto ao raciocinio do magician  está excelente, mas tal como ele disse tens que ter noçoes de Orientação em Objectos.

Depois é criar um array desse tipo, e implementar o algoritmo de forma q quer sejam aleatorios :D

è engraçado .. contanos mais :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O enunciado é elaborar  uma classe em que se  pode representar um labirinto sem o uso de arrays...tens ideias?  :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

E quanto ao raciocinio do magician  está excelente, mas tal como ele disse tens que ter noçoes de Orientação em Objectos.

Depois é criar um array desse tipo, e implementar o algoritmo de forma q quer sejam aleatorios :D

Não precisas do array para nada depois de criados os objectos ficas com uma estrutura de dados, como uma árvores mas neste caso quadrada lol

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Como posso faze system.out.println deste código para ver a posiçao no ecrã?

Posicao p1 = new Posicao(1,null,null,null,null)

eu fiz  System.out.println("a posicao  é"+p1).....só que não aparece (1,null,null,null,nul)l no ecrã.....mas um número esquisito  :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Dentro da classe posição faz cria o método public String toString() que retorna uma String com o que queres que apareça.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

public String toString() como assim?......isso vai me devolver uma String,como é que isso vai me ajudar ao fazer o System.out.println? :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O método toString dá-te uma representação textual da estrutura das tuas classes, isto é, das suas variáveis de instância.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Continuo confuso....podes dar-me um pequeno exemplo?.....estou a começar agora em java :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Supondo que tens a classe Ponto que representa um ponto no plano XoY com as seguintes variáveis de instância:

- X

- Y

O seu método toString() ficaria algo do género:

public String toString() {
StringBuilder s = new StringBuilder();
s.append("Ponto : (");
s.append(this.x);
s.append(",");
s.append(this.y);
s.append(")");
return s.toString();
}

Isto retornaria: "Ponto: (3,4)" para o caso em que x=3 e y=4.

Usei uma instância de StringBuilder porque como vais fazer concatenações sucessivas de Strings, e sendo estas imutáveis em Java e, por conseguinte, pouco eficientes no que toca à sua concatenação, torna-se mais eficiente usar uma instância de StringBuilder fazendo no fim a sua conversão para String de modo a corresponder ao tipo de retorno do método que estamos a definir.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Usei uma instância de StringBuilder porque como vais fazer concatenações sucessivas de Strings, e sendo estas imutáveis em Java e, por conseguinte, pouco eficientes no que toca à sua concatenação, torna-se mais eficiente usar uma instância de StringBuilder fazendo no fim a sua conversão para String de modo a corresponder ao tipo de retorno do método que estamos a definir.

Adorei o detalhe :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Usei uma instância de StringBuilder porque como vais fazer concatenações sucessivas de Strings, e sendo estas imutáveis em Java e, por conseguinte, pouco eficientes no que toca à sua concatenação, torna-se mais eficiente usar uma instância de StringBuilder fazendo no fim a sua conversão para String de modo a corresponder ao tipo de retorno do método que estamos a definir.

Micro-optimização! Por 5 concatenações não ganhas assim tanto quanto isso, comparado com o tempo que demoras a instanciar um objecto e a fazer chamadas a métodos da instância. Além de que não tens qualquer informação que te diga que esse bloco de código causa qualquer problema de performance na aplicação.

O sistema é tão simples que esse tipo de optimização nem te será fácil de medir. Cuidado com optimizações prematuras e micro-optimizações. Sei que não é objectivo do código, nem do tópico, explicar optimização, mas ao darem esse tipo de indicações estão a induzir em erro um programador que esteja a começar, bem como a perpetuar a ideia que "optimizar", porque não sabes ainda se isso resulta mesmo em melhor performance, é algo que se faz sem testes, o que é completamente errado.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mas é sempre bom ter ideias de como optimizar as coisas. Se correres aquela função 5 milhões de vezes, talvez poupes algumas execuções do GC.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mas é sempre bom ter ideias de como optimizar as coisas. Se correres aquela função 5 milhões de vezes, talvez poupes algumas execuções do GC.

Porque é que haverias poupar mais execuções do GC usando um objecto instanciado por ti, em vez de concatenações de strings?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não percebi a pergunta... o StringBuilder é que reduz a instanciação de objectos, logo poupa memória, logo poupa chamadas ao GC.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O StringBuilder é um objecto que vais ter de instanciar, em oposição às Strings que a JVM irá instanciar.

Teres 1 objecto ou 50 não faz com que existam mais chamadas ao GC. Eventualmente poderão existir, mas à primeira vista, e olhando para esta situação, tens um objecto num método, que quando o método terminar deixará de estar referenciado, o GC vai executar uma vez e encontrar um objecto para limpar. Agora eu uso concatenação, vou criar vários objectos dentro do mesmo método, o GC executa uma vez e encontra vários objectos.

Resultado, o GC executou apenas uma vez nas duas situações, e nas duas situações, numa só passagem, eliminou os objectos que tinha que eliminar, portanto usar o StringBuilder não aumenta qualquer performance por reduzir o número de chamadas ao GC, que são as mesmas nas duas situações. Logo não se poupam chamadas ao GC :D

Quanto à memória que mencionaste agora, teres 5 strings ou um objecto com uma String cujo tamanho é a soma das anteriores 5, vais obter uma diferença de memória de tal ordem diminuta que existir ou não, não ajuda em nada, se a isso acrescentarmos o facto de que a JVM ao arrancar reserva imediatamente o valor mínimo de memória definido pelo SO ou pelos parâmetros de configuração, que é coisa para andar em torno dos 32MB a 64MB, usados e consumidos logo pela JVM, podemos ver que precisarias de alguns milhares de Strings concatenadas para que o consumo de memória fosse importante.

Em tudo isto, não vejo qualquer optimização dado que estarias a tentar resolver um problema que não existia. Optimizar é melhor problemas de performance identificados, aqui, além de não terem sido identificados nenhuns, por uma análise superficial, não consigo ver onde poderias ter um qualquer problema de performance.

Não digo que esses pormenores não sejam importantes, mas devem ser introduzidos quando existam bases suficientes para se saber o que realmente se está a passar e se estamos mesmo a optimizar ou a perder tempo, podendo muitas vezes estar a "des"-optimizar, dado que é objectivo do JIT fazer optimização de código. E algumas das opções típicas de optimização atrapalham o que o JIT pode fazer.

Introduzir o uso do StringBuilder como algo que optimiza sem explicar porque é que optimiza, onde altera, em que situações o seu uso é realmente vantajoso e em que situações é pura perda de tempo, sem ensinar realmente o que se está a passar, é propagar uma ideia errada sobre o StringBuilder e sobre a tecnologia/linguagem. Se nestes casos pode ser algo inóquo, afinal apenas dá direito a uma "descasca" de um utilizador mais chato :), noutras pode ser a diferença entre uma boa decisão e uma programação lastimável.

Optimizar sim, mas quando realmente necessário, e ensinar a optimizar apenas quando quem está a aprender tem bases sólidas e conhecimentos da linguagem/tecnologia, senão é ensinar algo que não se compreenderá completamente.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Repara:

Se correres aquela função 5 milhões de vezes, talvez poupes algumas execuções do GC.

5 milhões de vezes a executar

	string s = "Ponto : (" + this.x + "," + this.y + ")";

quantas instâncias de string contas? Eu conto 9*5 milhões.

E aqui:

	StringBuilder s = new StringBuilder();
s.append("Ponto : (");
s.append(this.x);
s.append(",");
s.append(this.y);
s.append(")");
return s.toString();

? Eu conto, no máximo, 6*5 milhões. E isto não sabendo exactamente como são tratados os this.x e o this.y, porque caso não sejam convertidos para string, passa a 4*5 milhões. Mais um StringBuilder. Não me digas que não acreditas que haja um impacte na performance do programa :P

E quanto às chamadas do GC: uma vez mais, pensa em 5 milhões de chamadas ao método, com 9*5milhões de instâncias de string vs 6*5 milhões de instanciações de strings + 1 StringBuilder. Não notas uma possível redução nas execuções do GC?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

(...) E isto não sabendo exactamente como são tratados os this.x e o this.y, porque caso não sejam convertidos para string, passa a 4*5 milhões. Mais um StringBuilder. Não me digas que não acreditas que haja um impacte na performance do programa :P

São tratados como se convertidos com String.valueOf, acrescentando várias verificações para garantir que o int passado não ultrapassa os valores permitidos.

E sim, sei que existe impacto na performance, mas o problema não é esse, nem foi nisso que peguei. A questão é estar a incutir esse pormenor, porque neste caso, e na grande maioria das situações que o utilizador que iniciou o tópico irá encontrar durante muito tempo, não passa de um pormenor. Estar a incutir, dizia eu, como sendo algo importante para quem está a aprender. Para mim isso é um erro.

Não que a optimização não seja importante, mas porque para que a optimização possa ser feita correctamente, é necessário muito conhecimento sobre o funcionamento da plataforma, da linguagem, e neste caso tanto da JVM usada como do JIT onde a aplicação está a ser executada. Não é algo que se deva incluir de animo leve em explicações.

O StringBuilder é bom para casos onde se tenha verificado após implementação e testes, que a forma usada era penalizadora, antes disso, em desenvolvimento, nada garante que estejamos a melhorar, até porque no caso do StringBuilder, a vantagem de performance é acompanhada de uma penalização devido à complexidade de algumas das operações do objecto, pelo que só notarás vantagem em algumas situações. Isso não é algo que se verifique por código.

Posso pensar no exemplo de uma aplicação que fiz, onde pensei que o maior problema de performance fosse a leitura de ficheiros, em que para cada ficheiro lido estão a ser criados, pelo menos 3 objectos, e a ser invocados outros tantos. Daí seria de esperar que ao leres 50.000 ficheiros numa directoria terias problemas, e na verdade o problema de performance existe apenas no acesso a uma BD, que até é local à aplicação, correndo na mesma JVM. Este é apenas um exemplo de como o que em desenvolvimento podemos pensar que é problemático, na verdade só pode ser verificado testando a aplicação. Eu perdi umas horas a "optimizar" algo que não tinha qualquer problema de performance, quando podia ter gasto esse tempo a melhorar o que era importante.

Se posso considerar que até detenho alguns parcos conhecimentos sobre Java e sobre a JVM da Sun e mesmo assim cometi um erro grave para o desenvolvimento, podes ver como me oponho a que este tipo de conceitos sejam introduzidos muito cedo na aprendizagem. Além de ser algo complexo, e só ser confirmado em testes, é uma área que gera muita desinformação e que é frequentemente dá origem a aplicações menos boas porque o programador aprendeu a optimizar quando devia ter aprendido a programar.

E quanto às chamadas do GC: uma vez mais, pensa em 5 milhões de chamadas ao método, com 9*5milhões de instâncias de string vs 6*5 milhões de instanciações de strings + 1 StringBuilder. Não notas uma possível redução nas execuções do GC?

O giro do GC é que não é controlado pelo programador ;), podes ter esses milhões todos a executar e, se executarem em menos de 5 minutos é bem possível que o GC não tenha executado uma única vez. Mesmo que invoques a linha de código para pedir a execução do GC, isso não passa de um pedido, o GC tanto pode ser executado imediatamente a seguir como segundos ou até minutos depois.

Por isso, não, não conto aí menos execuções ou reduções, porque simplesmente não tens garantia de quando é executado. O único contracto que o GC te faz é que a memória que seja para libertar será libertada, agora quando, só ele sabe :P.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ok, concordo com tudo o que escreveste no último post.

O meu grande problema com a ocupação de memória é derivado de ter desenvolvido principalmente para dispositivos móveis, e nesse ambiente cada execução do GC nota-se bem. Esse projecto fazia uso extensivo de concatenações de strings (não eram 3 ou 4 concatenações por execução, eram à volta de 90, 9 concatenações por linha em 10 linhas, isto de cada vez que era pressionada uma tecla no telemóvel, e antes de se proceder à optimização do código), e volta e meia lá estava o GC a ser executado. Algo que foi solucionado através do uso do StringBuilder.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora