Jump to content
remy24

estruturas de dados em java

Recommended Posts

remy24

boa tarde caros utilizadores, sou iniciante no estudo de informática e tenho uma unidade curricular de algoritmia e estruturas de dados, o professor propôs que fizéssemos um algoritmo em java e eu nao estou a conseguir implementar nem criar pilhas em java.

o algoritmo proposto é o seguinte:

temos um caracol no fundo de um poço, e sabemos que ele sobe 3 metros por dia e ao fim do dia escorrega um metro, sabendo que o poço tem 10 metros quantos dias demora o caracol a chegar ao topo?

1 [criação da pilha]
Read (n)
TOP<-0
2 [leitura de valores e inicialização]
Read (alt, met_sub, met_desc)
Dia<-0
3[ciclo em processamento]
Do while TOP < ALT
 I <- 1
 Do while TOP<= Alt And I<= Met_Sub
   Push (S, TOP,I)
   I <- I+1
 Dia<- dia+1
 If Top < ALT
   Then do For DES=1 to Met_Desc
     SAID<- POP (S, TOP)
4[imprimir o numero de dias]
S[TOP-I+1]<-X
5 [Terminar]
Exit

esta é a minha solução em pseudo codigo.

nao estou a conseguir passar para java, alguem tem alguma dica?

obrigado

Share this post


Link to post
Share on other sites
HappyHippyHippo

não estou a perceber o teu pseudo-código ...

no entanto, do pouco que percebo, não parece ser a solução


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
remy24

tenho um livro "Algoritmia e Estruturas de Dados", Jose Braga de Vanconcelos que tem la esta solução em pseudo-codigo, nao entendo o sentido do ciclo for que esta quase no fim, so ai é que esta a minha duvida

Share this post


Link to post
Share on other sites
HappyHippyHippo

eu não quero saber de que livro tiraste uma solução qualquer que não fazes a mínima ideia do que se trata (até porque não seria o primeiro livro que eu mandaria dar uma volta ao bilhar grande)

- antes de mais, todas as linhas que começam com um número não estão lá a fazer nada ... e se são comentários, deveriam ser apresentadas como tal

- em pseudo-código os nomes das variáveis necessitam de ser legíveis e claramente identificativas do seu significado (pseudo-código não é código !)

- existem elementos/linhas que não fazem absolutamente nada

- existem operações que não servem para nada

olha bem para o que apresentaste:

1 [criação da pilha] // <------------------- comentário !!! (assinala como tal)
Read (n) // <------------------------------- lês um valor (de n) e não fazes nada com isso ...
TOP<-0 // <--------------------------------- é isto a inicialização da pilha descrita no comentário inicial ?!?!?
2 [leitura de valores e inicialização] // <- comentário !!! (assinala como tal)
Read (alt, met_sub, met_desc) // <---------- eu percebi o que é o "met_sub" e o "met_desc" porque sei o que se deve fazer, e tu, percebeste ?
Dia<-0
3[ciclo em processamento] // <-------------- comentário !!! (assinala como tal)
Do while TOP < ALT
I <- 1 // <--------------------------------- para quê atribuir o valor de 1 a uma variável I ? para que a variável I ...
Do while TOP<= Alt And I<= Met_Sub
 Push (S, TOP,I)
 I <- I+1 // <----------------------------- novamente, para que o incremento de I ?
Dia<- dia+1
If Top < ALT
Then do For DES=1 to Met_Desc
 SAID<- POP (S, TOP) // <------------------ guardar o valor retirado da pilha para uma variável que nunca mais será usada ... para quê ?
4[imprimir o numero de dias] // <----------- comentário !!! (assinala como tal)
S[TOP-I+1]<-X // <-------------------------- de onde apareceu X ? e porque guardar esse valor mágico numa posição qualquer e nunca fazer nada com esse valor ?
5 [Terminar] // <--------------------------- comentário !!! (assinala como tal)
Exit


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
remy24

as tuas duvidas são as minhas também, eu não tenho culpa de isso estar assim, isso é a fotocopia exacta do que esta no livro, eu não digo que o livro esteja certo, mas é isso que lá está, se calhar não consigo fazer porque o que ai está não faz sentido nenhum. dai a minha duvida, serei eu que não percebo nada de programação? ou o que está ai é impossível de fazer? na minha turma anda tudo á nora com isso, e a meu ver nem o prof sabe fazer

Share this post


Link to post
Share on other sites
HappyHippyHippo

eu tenho dúvidas no pseudo-código que apresentaste, não no problema ...

e que tal ignorar esse pseudo-código e pensares por ti ?

ps : acabei de resolver esse problema em 25 linhas de código (completo, com package, import, main e afins)

Edited by HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
Rui Carlos

Corrigi a indentação do código do primeiro post.

O código até deve fazer o que é pedido, mas complica o problema desnecessariamente.

Fica aqui uma versão um pouco mais limpa, que ainda assim mantém a complicação do código original.

top <- 0 // altura da stack
Read(alt, met_sub, met_desc)
dia <- 0
While top < alt
 i <- 1 // controla o metros que tem que subir
 While top <= alt And i <= met_sub // o top <= alt deve ser para evitar oveflows
   Push(s, top, i) // vamos assumir que o top é actualizado pela função
                   // parece-me irrelevante se introduzimos i na stack ou outro valor qualquer
   i <- i+1
 dia <- dia+1
 If top < alt  // se ainda
   Then
     des <- 1 // controla os metros que tem que descer
     While des <= met_desc // passei o For para While para usar algo semelhante ao ciclo anterior
       said <- Pop(s, top)  // said não serve para nada, mas pronto...
       des <- des+1
Write(dia)

Basicamente só o top é que interessa. A stack é desnecessária.

Share this post


Link to post
Share on other sites
HappyHippyHippo

@Rui ... corrigiste somente a indentação, os erros continuam lá

- o "i" não serve para nada, não controla a altura

- o "top" não controla nada (nunca é atribuído ao longo do ciclo)

- 'said' é atribuída mas nunca é usada

- etc ...

continuo a dizer, @remy24, se sabes como usar pilhas, pensa numa solução e cria tu o teu pseudo-código


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
remy24

pode ser algo deste genero?

read (alt, met_sob , met_desc, top, dia)
top <- 0
met_sob <- 3
met_desc <- 1

whie(top<alt)
     push( top)
     met_sob <- top

     while(met_sob<alt)
     pop(top)
     met_desc <- top


dia <- dia+1

if (met_sob >=alt)
 print ('o caracol subiu o posso em' dia 'dias')

Edited by Rui Carlos

Share this post


Link to post
Share on other sites
HappyHippyHippo

explica a tua escolha em cada linha com comentário a dizer o que faz e porquê


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
remy24

read (alt, met_sob , met_desc, top, dia)
top <- 0
met_sob <- 0
alt <- 10

whie(top<alt)    */ enquanto o ponteiro for menor que a altura do poço*/
     push( top+3)    */carrega 3 metros na pilha*/
     met_sob <- top    */ met_sob toma o valor do ponteiro*/

     while(met_sob<alt) */ enquanto os metros que ja subiu for menos que a altura*/
     pop(top-1)    */ decrementa 1 metro na pilha, neste momento a pilha tem 2 elementos, ou seja 2 metros*/
     met_sob <- top */ met_sob toma o valor do top, ou seja 2*/


dia <- dia+1  */ incrementa um dia/*

if (met_sob >=alt)   */ se os metros subidos for maior ou igual a altura do poço sai do programa e imprime o numero de dias, se nao volta ao inicio*/
 print ('o caracol subiu o posso em' dia 'dias')

fiz umas alterações, acho que sim funciona melhor, que me dizem?

Edited by Rui Carlos
Tags code.

Share this post


Link to post
Share on other sites
HappyHippyHippo

- eu quando disse em todas as linhas, era mesmo em todas as linhas

- isto é uma resolução em Java, não existem ponteiros

- já que não sabes usar as tags

 para apresentar a indentação, usa o [i]begin[/i] e o [i]end[/i] (ou outros identificadores de [i]scope[/i])

- não sei como é que o teu último [i]if[/i] faz tudo o que dizes no comentário

- a solução está errada (e não é só por causa do último if ...)


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
Rui Carlos

@Rui ... corrigiste somente a indentação, os erros continuam lá

- o "i" não serve para nada, não controla a altura

- o "top" não controla nada (nunca é atribuído ao longo do ciclo)

- 'said' é atribuída mas nunca é usada

- etc ...

O único que seria um erro era o top (os outros eram simplesmente complexidade desnecessária para este problema). Relativamente ao top, referi: "// vamos assumir que o top é actualizado pela função". O s parece ser simplesmente um array, e o top é necessário para tornar o array numa stack.

O i serve para controlar os metros que estás a subir (embora não sirva de nada na stack).

Não estou de modo algum a sugerir a utilização daquele algoritmo, apenas tentei perceber se ele funcionaria ou não. De resto, nem sequer faz sentido usar uma stack (logo, o que pões e tiras da stack é pouco relevante).

Share this post


Link to post
Share on other sites
HappyHippyHippo

mas isto é um tópico de Java, e em Java existe a classe Stack o que torna o uso da variável top completamente desnecessária.

mesmo que seja usada para determinar a posição de um vector a ser usado, está claramente mal porque nunca é incrementada ou decrementada, tem sempre o valor de 0, ficando no ar a utilidade da variável I ...

como já disse ao longo deste tópico : o melhor é mesmo ignorar o pseudo-código do livro e pensar numa solução razoável (mesmo utilizando uma stack)

<offtopic>

http://www.wook.pt/ficha/algoritmia-e-estruturas-de-dados/a/id/171041

Sinopse

O mais completo e actualizado livro português sobre algoritmos e estruturas de dados, lineares e não lineares, com dezenas de exemplos em pseudocódigo e nas linguagens de programação C e Java. Destinado quer a estudantes quer a profissionais do sector das Tecnologias da Informação.

Este livro foi preparado e concebido para ser utilizado como objecto de estudo em diferentes áreas de conhecimento, dado que apresenta a disciplina de algoritmia como requisito fundamental à resolução de problemas do mundo real. Contudo, tem especial interesse para docentes, alunos e formandos nas áreas das ciências da computação, nomeadamente sistemas de informação, matemáticas aplicadas e cursos de engenharia.

Este livro procura dotar futuros profissionais com as componentes de raciocínio e abstracção necessárias à resolução de problemas. Explora a análise e as técnicas essenciais à concepção de algoritmos e à especificação formal de estruturas de dados lineares e não lineares. Neste sentido, os autores introduzem uma componente prática baseada na apresentação de um conjunto alargado de algoritmos resolvidos. A implementação dos algoritmos é efectuada através das linguagens de programação C e Java, também apresentadas neste livro.

http://www.wook.pt/authors/detail/id/35773

José Braga de Vasconcelos

José Braga de Vasconcelos é doutorado em Ciências da Computação pela Universidade de York (UK). Após o doutoramento produziu e apresentou diversas publicações em conferências e revistas científicas na área de Gestão de Conhecimento Organizacional. Actualmente é Professor Associado na Faculdade de Ciência e Tecnologia da Universidade Fernando Pessoa, e membro fundador do Grupo de Investigação e Desenvolvimento (I&D) em Informática Médica (GIMED). Prestou também consultoria em Sistemas de Informação e Engenharia de Software em empresas. Ultimamente, além da sua área de investigação em Gestão e Modelação de Competências Organizacionais, tem vindo a exercer I&D na área de Sistemas de Informação para a Saúde.

mais um livro que demonstra a sua qualidade espetando mais um prego na consideração que tenho por este tipo de publicações ...

ao menos é só 20 euros ao contrário dos convencionais 40

</offtopic>

Edited by HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
remy24

consegui..... em baixo deixo a minha solucao

package caracol2;

public class Caracol2 {

   private static final int capacidade = 10;
   int pilha[] = new int[capacidade];
   static int top = 0;

   public void push(int metrosSobe, int top) {

       this.top += 3;
       pilha[top] = metrosSobe;
   }

   public void pop(int metrosSobe, int top) {
       this.top -= 1;
      metrosSobe =  pilha[top];
   }

   public static void main(String[] args) {


       int dia = 1;
       int metrosSobe = 0;

       Caracol2 auxCaracol = new Caracol2();
       while (capacidade > top) {

           auxCaracol.push(metrosSobe, top);
           metrosSobe = top;
           if (metrosSobe < capacidade) {
               auxCaracol.pop(metrosSobe, top);
               metrosSobe = top;
           } else {
               break;
           }

           dia = dia + 1;


       }
       System.out.println(String.format("acabou ao fim de %d dias", dia));



   }
}

Edited by thoga31
Tags code + GeSHi

Share this post


Link to post
Share on other sites
HappyHippyHippo

não executaste isso pois não ? sabes como sei que não ? pela simples razão que isso dá ArrayIndexOutOfBounsException (e nem necessita de correr o código para o saber.

queres saber porquê ? olha para o que estás a fazer:

primeiro dia:

- sobre 3 (top = 3)

- desce 1 (top = 2)

segundo dia:

- sobre 3 (top = 5)

- desce 1 (top = 4)

terceiro dia:

- sobre 3 (top = 7)

- desce 1 (top = 6)

quarto dia:

- sobre 3 (top = 9)

- desce 1 (top = 8)

quinto dia:

- sobre 3 (top = 12) // tens uma atribuição ao índice 12 do array pilha logo a seguir ... ups ...

-------

agora olha bem para o código que tens ... achas que altera alguma coisa se remover todas as linhas em que a variável metrosSobe é lida ou atribuída ?


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
HappyHippyHippo

ok ... estive a ver melhor o código ...

isso está uma confusão de variáveis estáticas e não estáticas, é por isso que o valor de top não causa a excepção.

agora a pergunta mais engraçada é : porque é que quando o valor de top é 12 não dá a excepção ? (na realidade o índice atribuído é o 9o)

consegues responder a isto ?

-------------

ps : a solução correcta dentro da filosofia Java (OOP) :

package javaapplication1;

import java.util.Stack;

public class JavaApplication1 {
   static final int AlturaPoco = 10;
   static final int SobePorDia = 3;
   static final int DescePorDia = 1;

   public static void main(String[] args) {
       int dia = 0;
       Stack stack = new Stack();

       while (stack.size() < AlturaPoco) {
           dia++;
           for (int i = 0; stack.size() < AlturaPoco && i < SobePorDia; i++)
               stack.push(dia);

           for (int i = 0; stack.size() < AlturaPoco && i < DescePorDia; i++)
               stack.pop();
       }

       System.out.println("O caracol chegou ao cimo no " + stack.pop() + "o dia");
   }
}


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.