Aula Prática #08 - Consolidação de Conhecimentos (Listas, Pilhas e Filas)
(semana de 13/04 a 17/04)
Aula de Recuperação e Consolidação
Nesta semana iremos fazer uma aula mais de recuperação e consolidação de conhecimentos. Se ainda não o fez, a sua prioridade deverá ser primeiro fazer os exercícios principais sugeridos nas aulas #06 e #07 (nos guiões dessas aulas pode encontrar dicas para cada um dos exercícios sugeridos). Em particular, certifique-se que:
Percebeu o conceito e implementação de listas ligadas simples (SinglyLinkedList) dada nas aulas e que submeteu com sucesso no Mooshak de EDados os seguintes exercícios que obrigam a mexer na estrutura de dados em si:
O ideia deste exercício é resolver um problema um pouco maior usando os conceitos que aprendeu de listas, pilhas e filas. O objectivo é submeter com sucesso o problema [ED098] Triagem de Manchester ("Volume 4 (Pilhas e Filas)") criando um código adequado e estruturado. Não se esqueça de ir testando sempre as coisas que vai implementando!
O início.
Comece por ler com muita atenção o enunciado do problema, para perceber o que é pedido.
Código inicial.
Para este problema vamos guiá-lo detalhadamente para uma solução minimamente organizada. Deverá por isso começar por ir buscar o seguinte código inicial: ED098_codigo_inicial.java (ver em html)
Espreite um pouco o programa para ficar com uma ideia por alto da sua organização:
Existem 3 classes: Doente, Equipa e ED098 (a classe com o main()).
Veja as constantes declaradas (variáveis declaradas como final): o número de cores (NUM_CORES) e as strings representando as cores em si (array de strings CORES[]).
Os dados do problema vão ser guardados essencialmente nestas três estruturas de dados:
Um array com 5 filas de doentes
(emEspera[]), uma para cada
cor, onde os doentes são guardados na ordem em que
chegam. (note que foi criada uma classe para conter a fila, pois o Java proíbe a criação direta de arrays de genéricos, ou seja, uma linha como MyQueue<Doente> emEspera[] daria um erro ao compilar)
Uma lista atendidos para guardar os doentes à medida que vão sendo atendidos. (usamos uma lista do próprio Java para ilustrar a semelhança com as nossas listas e para exemplificar a instrução for-each para iterar: ver método mostrarAtendidos())
Um array equipas[] para guardar os dados de cada uma das equipas de urgência
O main já lê a flag e o número de equipas, chamando depois os métodos inicializar() e lerDoentes()
flag==0.
A primeira flag pede essencialmente para ler os dados dizer o número de doentes de cada tipo, bem como o total de doentes.
O método lerDoentes() já consegue ler os nomes dos pacientes. Experimente executar o código com o primeiro input de exemplo e certifique-se que percebe como os doentes foram lidos.
Para esta flag podia fazer-se algo ainda mais simples, mas vamos já começar a preparar o código para as outras flags. A ideia é à medida que vamos lendo ir acrescentando os doentes à fila da cor respetiva:
Queremos associar um número inteiro de 0 a 4 a cada cor (da mais prioritária para a menos prioritária). Complete por isso o método indiceCor(). Por exemplo, uma chamada a indiceCor("Vermelho") deve devolver 0, e uma chamada a indiceCor("Amarelo") deve devolver 2. Para implementar o método use o array CORES[] já definido: basta percorrer o método e ver qual a cor igual (compara com equals()). Não se esqueça de testar o método!
Ao ler o doente, em vez de escrever o que leu, deve adicioná-lo à fila respetiva, ou seja, dentro do ciclo de leitura, sabendo que o indíce da cor do doente atual é i, adeve adicioná-lo à fila de emEspera[i] (use o método enqueue()). Aproveite e incremente a variável numDoentes, que deverá no final conter o número total de doentes.
Se já fez a leitura corretamente, as filas já estão com os doentes respetivos. Para escrever o output desejado, basta agora completar o método mostrarCores(): para cada cor possível (iterar um inteiro i) mostrar o nome da cor (CORES[i]) e a quantidade de doentes com essa cor (tamanho da fila de emEspera[i]).
Para escrever de forma corretamente alinhada pode usar o método printf(). Por exemplo, para alinhar uma string s à direita num campo de 10 caracteres podia fazer System.out.printf("%10s", s). No caso deste output precisa primeiro de escrever a cor (alinhada à direita num campo de 8 caracteres), seguida de um espaço, seguida do número de doentes (alinhada à direita num campo de 3 dígitos).
Depois de ter verificado que o programa está a funcionar, submeta no Mooshak e obtenha 25 pontos, que correspondem precisamente aos exemplos de input com flag==0.
flag==1.[para fazer este problema bastaria fazer a flag2, que "inclui" a flag1, mas vamos fazer uma de cada vez]
Esta flag pede para simular o que acontece quando existe apenas uma equipa de urgência.
Tem de começar por completar o método simular(), cuja ideia é simular o que vai acontecendo. Imagine que tem uma variável tempo indicando o tempo atual (em minutos). Inicialmente ela deve ser zero. Depois deve fazer algo como:
enquanto (numAtendidos < numDoentes) fazer: (atendidos.size() < numDoentes)
Seja D o próximo doente a ser atendido (D = emEspera[proximoDoente(tempo)].fila.deueue()) [se necessário avançar tempo até termos um doente disponível]
Actualizar tempo de entrada do doente D (D.entrada = tempo)
Avançar tempo até terminar de ser atendido (tempo += D.atendimento)
Adicionar doente D à fila de doentes atendidos (atendidos.addLast(D))
Para saber o próximo doente complete o método proximoDoente(tempo), cuja ideia é devolver o indíce mais prioritário (menor) da cor cujo primeiro doente pode ser atendido (ou seja, que tem tempo de chegada menor ou igual ao tempo actual). Se não existir nenhum pode por exemplo devolver -1 (e usar esse resultado para saber que tem de avançar o tempo).
[como os inputs são pequenos - máximo tempo é 1440 - pode optar por incrementar o tempo de um em um; uma opção melhor seria procurar o menor tempo de chegada de um doente e avançar logo até lá]
Falta ainda completar o método mostrarAtendidos(). Note como já são escritos os nomes. Em cada doente falta agora escrever o tempo de chegada (atributo do doente), o tempo de espera (tempo de entrada - tempo de chegada) e o tempo de saída (tempo de entrada + tempo de atendimento). No final do método tem também de escrever o tempo médio de espera: pode por exemplo ir acumulando os tempos de espera à medida que escreve os doentes atendidos e depois dividir pelo número de doentes (cuidado com o uso de inteiros: é necessária uma média com casas decimais).
Depois de ter verificado que o programa está a funcionar, submeta no Mooshak e obtenha 60 pontos, que correspondem precisamente aos exemplos de input com flag==0 ou flag==1.
flag==2.
Agora temos de ter em conta que podem existir várias equipas na urgência. O ciclo principal fica parecido com a anterior mas agora temos de ter cuidado com a equipa que fica com o doente e a maneira como o tempo avança:
enquanto (numAtendidos < numDoentes) fazer:
Seja E a próxima equipa livre (usar método (E = proximaEquipaLivre()))
Avançar tempo até existir uma equipa livre (tempo = equipas[E.livre])
Seja D o próximo doente a ser atendido (D = emEspera[proximoDoente(tempo)].fila.deueue()) [se necessário avançar tempo até termos um doente disponível]
Adicionar doente à equipa respetiva (equipas[e].novoDoente(d, tempo)) [entre outras coisas, deve atualizar o tempo em que a equipa fica novamente livre]
Actualizar tempo de entrada do doente D (D.entrada = tempo)
Adicionar doente D à fila de doentes atendidos (atendidos.addLast(D))
Já ajudamos tanto que não precisa de mais dicas, certo? Não se esqueça de completar os métodos proximaEquipaLivre() e mostrarEquipas()). Depois de verificar o programa, submeta com sucesso para obter os 100 pontos no Mooshak!
Exercício 2) Quartel de Bombeiros
Resolva agora "sozinho" um problema semelhante ao anterior, mas um pouco mais fácil. Procure fazer um código organizado, com várias classes representando as várias entidades do problemas, e vários métodos, cada um dedicado à sua (pequena) tarefa.
Crie três classes: Bombeiro (deve guardar nome, nº de eventos e nº de minutos), Evento (deve guardar lista de bombeiros e minuto de início) e ED198.
Crie uma fila de bombeiros (MyQueue<Bombeiro> para representar a fila no quartel
Crie um array de eventos, onde a posição i representa o evento de código i (Evento[])
Para cada partida, é só retirar elementos da fila do quarter e adicionar ao evento; para cada chegada é só voltar a adicionar os elementos ao quartel (sendo que ao fazer isso pode aproveitar para atualizar os minutos e número de eventos dos bombeiros respetivos).
Exercícios extra para consolidação de conhecimentos
Mais problemas de pilhas e filas
Tem disponíveis no Mooshak de EDados, no "Volume 4 (Pilhas e Filas)", mais alguns problemas envolvendo pilhas e filas, que lhe permitem testar a sua organização de código. Em particular deve procurar resolver o seguinte problema (que já foi dado como extra na aula passada), parecido com os dois problemas sugeridos nesta aula:
Jogos de Cartas.
Para testar a sua organização faça agora algo diferente:
Cria uma classe Carta para representar uma carta. Deverá ter como atributos naipe (copas, espadas, ouros ou paus) e valor (ás, rei, valete, dama ou valor entre 2 e 10). De que tipos devem ser estes atributos?
Crie uma classe Baralho para representar um baralho de 52 cartas. Deverá ter como atributo um array de 52 cartas e o seu construtor padrão deverá colocar no baralho as 52 diferentes cartas existentes.
Na classe Baralho crie um método baralhar que mistura as cartas do baralho, colocando-os por ordem aleatória. Dica: use a classe Random.
Crie uma classe Mao para conter um conjunto de n cartas. O número n dev e ser passado no construtor.
Crie um programa que deixe o utilizador jogar Blackjack. Use as classes que definiu anteriormente para representar as cartas e o baralho.
Exercício de Desafio
Para esta semana disponibilizo um problema não muito complicado, também da minha autoria, e que foi usado numa fase de qualificação das Olimpíadas Nacionais de Informática:
O limite de tempo de execução para cada caso de teste é de 2 segundos, pelo que a solução só será aceite e com pontuação máxima no Mooshak se for minimimamente eficiente (sendo que já dei mais alguma "margem de manobra": a solução oficial demora bem menos que 1s, mesmo para um caso com os 3000 pontos).