Estruturas de Dados

De Softwiki

Tarefas de programação para estruturas de dados:

1. Jogo do rato no labirinto: 27/02 2. Solução aleatória para o problema das 8 rainhas: 28/02 Neste problema você deve criar um programa que chuta aleatoriamente 8 posições distintas no tabuleiro. Então deve-se verificar se alguma dessas posições oferece ataque a outra. Em caso afirmativo o programa deve gerar outro conjunto de valores aleatórios e repetir a execução, até que encontre a disposição correta.

3. Implementação do Jogo Life usando Swing: 07/03 (adiado)

4. Raposas e Galinhas

Na fazenda do Sr. Buscapé existe um certo número de galinhas. Enquanto elas estão dormindo profundamente, alguns raposas famintas tentam invadir a fazenda e atacar as galinhas. Galinhas normais ficariam indefesas diante de tal ameaça, mas felizmente as galinhas do Sr. Buscapé são ninjas e conseguem defender-se adequadamente.

A fazenda possui um formato retangular e consiste de ninhos arranjados em linhas e colunas. Cada ninho pode conter uma galinha (representada pela letra ‘k’), uma raposa (letra ‘v’), uma cerca (símbolo ‘#’) ou simplesmente estar vazio (símbolo ‘.’).

Consideramos que dois ninhos pertencem a um mesmo galinheiro se podemos ir de um ninho ao outro através de um caminho formado somente com movimentos horizontais ou verticais, sem passar por uma cerca. Na fazenda podem existir ninhos vazios que não pertencem a nenhum galinheiro. Um ninho vazio não pertence a nenhum galinheiro se é possível “escapar” da fazenda a partir desse ninho (ou seja, caso exista um caminho desse ninho até a borda da fazenda).

Durante a noite, as galinhas conseguem combater as raposas que estão no mesmo galinheiro, da seguinte forma: se em um determinado galinheiro houver mais galinhas do que raposas, as galinhas sobrevivem e matam todos as raposas naquele galinheiro. Caso contrário, as galinhas daquele galinheiro são comidas pelas raposas, que sobrevivem. Note que caso um galinheiro possua o mesmo número de raposas e galinhas, somente os raposas sobreviverão, já que raposas são predadores naturais, ao contrário de galinhas.

Tarefa

Escreva um programa que, dado um mapa da fazenda do Sr. Buscapé indicando a posição das cercas, galinhas e raposas, determine quantas galinhas e quantas raposas estarão vivas na manhã seguinte.

Entrada A entrada contém vários conjuntos de testes, que devem ser lidos de um arquivo. A primeira linha da entrada contém dois inteiros R e C que indicam o número de linhas (3 ≤ R ≤ 200) e de colunas (3 ≤ C ≤ 200) de ninhos da fazenda. Cada uma das R linhas seguintes contém C caracteres, representando o conteúdo do ninho localizado naquela linha e coluna (espaço vazio, cerca, ovelha ou raposa).

Saída

Seu programa deve imprimir, na saída padrão, uma única linha, contendo dois inteiros, sendo que o primeiro representa o número de galinhas e o segundo representa o número de raposas que ainda estão vivos na manhã seguinte.

Exemplo de Entrada

6 6 
...#.. 
.##v#. 
#v.#.# 
#.k#.# 
.###.# 
...### 

8 8 
.######. 
#..k...# 
#.####.# 
#.#v.#.# 
#.#.k#k# 
#k.##..# 
#.v..v.# 
.######. 

9 12 
.###.#####.. 
#.kk#...#v#. 
#..k#.#.#.#. 
#..##k#...#. 
#.#v#k###.#. 
#..#v#....#. 
#...v#v####. 
.####.#vv.k# 
.......##### 

0 0 

Saída 
0 2 
3 1 
3 5 

5. Uma lista circular é parecida com uma lista ligada simples. Ela também é identificada por uma variável apontando para o primeiro elemento, mas a diferença é que o último elemento, em vez de apontar para NULL, aponta para o primeiro elemento. Para este exercício você pode usar um nó que armazena números inteiros. Se a lista está vazia, a variável início aponta para NULL. Se a lista só tem um elemento, seu próximo é ele mesmo. (a) Implemente as classes ListaCircularSimples, No e Teste; (b) Faça um método para inserir um novo elemento no início da lista ligada circular; (c) Faça um método para remover o último elemento da lista ligada.

6. Seu objetivo é fazer um programa que trabalha com imagens PGM em tons de cinza, no formato P5 e P2. Para ajudar sua tarefa, veja a página da Unicamp com o enunciado do exercício. Tarefas: (a) conversão de imagens P5 para P2 e vice-versa; (b) impressão do histograma e do histograma acumulado; (c) equalização por histograma; (d) negativo; (e) threshold

7. Exercício de compactação de arquivos usando árvores. (a) implemente inicialmente um programa que gere a tabela de ocorrência de caracteres em arquivos; (b) implemente agora a geração da árvore de huffman e do arquivo compactado. Eles podem ficar em arquivos diferentes; (c) implemente então a descompactação do arquivo.

8. Simulação de Aeroporto Simulação Aeroporto

O objetivo deste exercício-programa (EP) é implementar um sistema de gerenciamento das pistas de um aeroporto de grande movimento. As estruturas de dados deverão ser econômicas e os algoritmos, eficientes.

O bom gerenciamento das pistas de um aeroporto, que são usadas para pousos e decolagens, é fundamental para o funcionamento do mesmo. Os aviões que solicitam pouso têm combustível limitado e não podem circular indefinidamente à espera de autorização para pouso. Similarmente, atrasos nas decolagens são indesejáveis e causam transtornos aos passageiros e grandes prejuízos às companhias aéreas.

O aeroporto que simularemos tem três pistas, numeradas de 1 a 3. As duas primeiras pistas podem ser utilizadas para pousos ou decolagens. A pista 3 é usada apenas para decolagens, a menos que ocorra uma situação de emergência.

A simulaçãao dependerá do valor de alguns parâmetros descritos a seguir. Em cada unidade de tempo, de 0 a K aviões comunicam à torre o desejo de decolar ou pousar. Os aviões — ou, mais precisamente, os vôos — são identificados por uma sequência de duas letras (identificação da companhia aérea) e três números. Além disso, os voos trazem um código de três letras correspondente ao aeroporto de/para onde vão/vêm. Ao contactar a torre, o piloto se identifica por meio do identificador do voo e aeroporto de destino/origem. Caso deseje pousar, ele comunica também quanto tempo tem de combustível (de 1 a C unidades de tempo). Caso deseje decolar, ele comunica qual é a duração aproximada do voo (de 1 a V unidades de tempo). Se um avião que está esperando a autorização de pouso chegar a ter tempo de combustível 0, deve pousar imediatamente.

De tempos em tempos (probabilidade menor que 15%), surge um vôo de emergência (transporte de doentes, presidentes, sequestros etc). Estes vôos devem ter passagem livre para decolagem ou aterrissagem, assim que se comunicam com a torre. Cada pista pode manejar uma decolagem ou um pouso em cada unidade de tempo.

Os aviões que estão no ar para pousar permanecem circulando o aeroporto até que a torre escolha e libere uma pista para o pouso. Estes aviões são atendidos em uma estratégia de "fila", ou seja, os aviões que se comunicaram primeiro com a torre devem ser atendidos antes. Há duas exceções a esta regra: as emergências e os aviões que ficam sem combustível. Nestes dois casos, o avião deve pousar imediatamente, independente dos demais aviões. Similarmente, os aviões que querem decolar são atendidos também na ordem em que se comunicaram com a torre, exceto pelas emergências e os casos de aviões que estejam esperando a liberação da pista por mais de 10% do seu tempo estimado de vôo. Os dois últimos casos têm prioridade sobre os demais aviões que esperam para decolar. A cada unidade de tempo, os aviões se comunicam com a torre antes de acontecerem efetivamente decolagens ou pousos.

Você deve implementar uma estratégia que não permita que aviões caiam por falta de combustível. Seu programa deve detectar situações críticas (4 ou mais aviões ficarão sem combustível em um mesmo instante, por exemplo), e poderá escolher alguns desses aviões problemáticos para desviar suas rotas para outros aeroportos da região. Para isso, seu programa deverá manter uma tabela de aeroportos da região, que estejam a uma distância de até 50 unidades de tempo. Seu programa deverá ser o mais eficiente possível, e sua estratégia para designação e liber ação de pistas deverá fazer com que o tempo de espera seja o mínimo possível e o número de aviões desviados seja o menor possível. Não deverá haver duplicação de informações! Um avião deve ser representado por apenas um registro. As filas deverão ter apontadores para o registro do avião. A escolha do tipo de fila a ser utilizado e da implementação de cada fila deve ser feita para que as operações envolvidas na simulação sejam tão eficientes quanto possível. Isso será levado em conta fortemente na nota do seu EP.

Os aviões devem ser de pelo menos 5 companhias aéreas diferentes, e os aeroportos de origem/ destino pelo menos 30. Lembrem que certas companhias aéreas operam somente em alguns aeroportos.

A simulação deverá ocorrer durante T unidades de tempo. A saída de seu programa deve indicar com clareza o que está acontecendo a cada momento. Mostre na tela, a cada unidade de tempo,

• (a) os aviões que estão nas filas de decolagem e pouso, na ordem em que aparecem na respectiva fila;
• (b) o tempo médio de espera para decolagem;
• (c) o tempo médio de espera para pouso;
• (d) a quantidade média de combustível dos aviões esperando para pousar;
• (e) a quantidade média de combustível disponível nos aviões que pousaram;
• (f) a quantidade de aviões pousando/decolando em condições de emergência e
• (g) o número de aviões desviados desde o início da simulação.

A saída deve ser fácil de compreender e auto-explicativa. Isso também será levado em conta na nota do seu EP. A entrada da simulação depende dos parâmetros K, C, V e T, já descritos. Ela deve ser criada usando um gerador de números pseudo-aleatórios para decidir dentre as várias possibilidades: quantos aviões, entre 0 e K, se comunicam com a torre em uma dada unidade de tempo, qual é o seu identificador, quantos destes querem pousar, quantos querem decolar, quanto combustível tem cada avião que comunica que quer pousar, quanto é o tempo estimado de vôo de um avião que comunica que quer decolar, etc. Lembre-se de fixar a semente do gerador uma única vez no seu programa, de maneira que seja fácil reproduzir uma mesma entrada novamente durante a fase de depuração do seu programa, e mesmo na correção deste.

Além de entregar o seu EP, você deve entregar um pequeno relatório descrevendo os testes que você fez e indicando como o monitor poderá reproduzi-los. Tente conseguir informações de um aeroporto real, como Cumbica ou Congonhas, e discretize-as para utilizá-las no seu programa. Um bônus será dado na nota do seu EP se você conseguir dados reais e preparar o seu programa para tanto aceitar dados gerados aleatoriamente (como descrito acima) como aceitar dados de um arquivo de entrada criado por você.