Ir para o conteúdo
remy24

estruturas de dados em java

Mensagens Recomendadas

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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)

Editado por HappyHippyHippo

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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')

Editado por Rui Carlos

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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?

Editado por Rui Carlos
Tags code.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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).

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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>

Editado por HappyHippyHippo

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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));



   }
}

Editado por thoga31
Tags code + GeSHi

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação 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

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.