[Calendário] [Changelog] [Introdução] [Descrição] [Interface] [Avaliação] [Mooshak] [FAQ] [Observações]
Este enunciado descreve o trabalho prático da disciplina de Algoritmos e Estruturas de Dados do 1º ano da Licenciatura em Engenharia Eletrotécnica e Computadores. Os alunos podem e devem tirar todas as dúvidas com os docentes da disciplina.
O trabalho é para ser realizado por grupos de 2 alunos do mesmo turno. Qualquer exceção a esta regra, se porventura vier a existir, terá de ter por base uma autorização por escrito (por ex. por email) dos docentes da disciplina.
O trabalho tem 2 fases de entrega. Serão aqui anunciados os detalhes nos próximos dias, incluindo as duas datas de entrega.
Vão ser realizadas discussões do projeto.
O programa deve ser escrito em ANSI-C (a norma oficial do C), e deve ser desenvolvido usando a metodologia de programação da disciplina. Se quiser, pode usar este código como ponto de partida: drones.zip [basta clicar para fazer download].
Este código oferecido respeita a metodologia de programação que foi apresentada na aula teórica 9. Mas o código tem algumas imperfeições nos detalhes: (1) faltam os comentários nos ficheiros ".h", incluindo as tão importantes precondições; (2) há um erro ao escrever-se "eh" em vez de "e'", (3) o comando T não está a validar o argumento (que não pode ser negativo); talvez haja mais casos... São sinais de que este código é para ser olhado criticamente e poderá precisar de modificações.
Para além da gestão dos drones e das encomendas, a aplicação efetua simulação da passagem do tempo. Por exemplo, num dado momento é possível saber em que ponto da sua viagem se encontra um drone. A resolução do relógio é 1 hora, o que significa que iremos trabalhar sempre com tempos que são múltiplos de 1 hora. Quando a aplicação começa, o relógio começa com o valor zero.
Cada drone possui um identificador único (um inteiro que é atribuído automaticamente no momento da criação, sequencialmente a começar em 1), uma distância máxima de voo disponível antes de precisar de manutenção, e um limite de carga transportável. Poderá guardar ainda mais informação, dependendo da forma como forem implementadas as funcionalidades do programa.
Os drones voam a velocidade constante de 10 km/hora. A distância de ida é sempre arredondada para cima, para o primeiro múltiplo de 10, para garantir que o tempo de voo é um múltiplo de 1 hora. Note também que, quando um drone faz uma viagem, ele percorre a distância entre a base e a localização do cliente, mas depois precisa de regressar à base, o que duplica a distância percorrida. Por exemplo, se o endereço do cliente se encontrar a 24 km, isso significa que se considera que a viagem de ida é de 30 km e que vai durar três horas. A viagem de regresso também é de 30 km e dura 3 horas.
A razão de ser de todos estes arredondamentos é evitar a inexatidão dos números reais, que poderia ser um problema no Mooshak.
Cada encomenda possui um identificador único (um inteiro que é atribuído automaticamente no momento da criação a começar em 1001), um peso, as coordenadas de destino e ainda três valores temporais relevantes que são registados quando estiverem disponíveis: o momento em que a encomenda foi feita, o momento em que saiu da base, e o momento em que chegou ao destino. Poderá guardar ainda mais informação, dependendo da forma como forem implementadas as funcionalidades do programa.
Vamos então trabalhar com os conceitos de drone básico e de drone coletivo. A partir de agora, a palavra drone será usada para referir quaisquer elementos destas duas categorias.
Um drone coletivo é constituído por uma coleção de drones básicos (é proibido um drone coletivo fazer parte de outro drone coletivo). Um drone básico que faça parte dum coletivo, só efetua transportes integrado no coletivo. Está disponível uma operação para criar drones coletivos e outra para destruir drones coletivos, deixando livres os drones básicos constituintes. Para criar um novo drone coletivo, só se podem usar drones básicos que estejam livres, ou seja, estacionados à espera de trabalho e que não façam já parte de algum drone coletivo.
Um drone coletivo combina a capacidade dos seus drones básicos, adicionando as capacidades de transporte desses drones. Já o alcance máximo de voo dum drone coletivo é limitado pelo alcance mais baixo de qualquer um dos seus componentes.
Não é possível fazer a manutenção direta dum drone coletivo. É preciso primeiro destruir o coletivo. Quando se destrói um drone coletivo, os seus elementos retomam a sua individualidade e são imediatamente alvo de manutenção. Normalmente, o utilizador do sistema cria um drone coletivo especificamente para fazer o envio duma encomenda pesada, e depois destrói esse drone coletivo logo após o seu regresso (mas não é obrigado a fazer isso).
O programa funciona através de comandos. É o utilizador que regista as encomendas, cria os drones, envia as encomendas, manda efetuar manutenções, etc.
Nesta secção, após alguma informação geral sobre os comandos, iremos apresentar todos os comandos que o sistema deve ser capaz de executar.
Os comandos são pedidos ao utilizador usando o prompt '> '. Cada comando é identificado por um caráter que, no caso de ser uma letra, pode ser dada em maiúsculas ou minúsculas. Por exemplo, o comando de criação dum drone básico pode ser introduzido pelo utilizador usando a forma 'b' ou 'B'.
O formato do output dos comandos é rígido, para poder avaliado pelo Mooshak.
Nos exemplos deste documento, todo o texto introduzido pelo utilizador aparece em negrito. Já texto escrito pelo programa aparece de forma normal. Em diversos contextos explicitamos as mudanças de linha usando o símbolo '↩'.
Se o utilizador introduzir um comando desconhecido, o programa escreve a mensagem "Comando desconhecido.↩". Por exemplo:
> H↩ Comando desconhecido.↩
Muitos dos comandos possuem argumentos, que no nosso caso serão sempre números inteiros, geralmente não negativos. Por favor, assuma que o utilizador nunca comete o erro de introduzir uma string ou um número real em vez dum número inteiro. O utilizador poderá é enganar-se na quantidade de argumentos e também poderá introduzir valores negativos por engano (só são permitidos inteiros negativos na especificação de coordenadas). Estes dois últimos aspetos precisam de ser validados.
Se o utilizador introduzir um comando com um erro destes, o programa escreve a mensagem "Dados invalidos.↩". Por exemplo:
> B -10 100 123↩ Dados invalidos.↩
Qualquer outra situação em que o utilizador tente fazer algo de impossível, por exemplo tentar fazer voar um drone que não existe ou que está em manutenção, o programa escreve escrever a mensagem "Nao pode fazer isso.↩". Há dezenas de possibilidades relativamente a pedidos impossíveis de concretizar, mas a mensagem de erro é sempre a mesma. Por exemplo, assumindo que o drone 3 está em manutenção:
> D 1001 3↩ Nao pode fazer isso.↩
> .↩ Obrigado. Volte sempre!↩
> ?↩ Menu:↩ B - cria um novo drone Basico e regista-o na base↩ C - cria um novo drone Coletivo e regista-o na base↩ D - Despacha uma encomenda usando um drone↩ E - cria uma nova Encomenda↩ L - Lista drones e encomendas↩ R - Remove drone da base e destroi-o↩ T - avanca o Tempo um dado numero de horas↩ ? - mostra os comandos disponiveis↩ . - finaliza a execucao do programa↩Repare que cada comando é identificado por uma letra maiúscula que aparece algures no respetivo texto. Por exemplo, 'B' diz respeito à palavra "Basico", que ocorre no meio do texto.
> B 40 400↩ Adicionado drone(cat=basico, id=1, cap=40, alc=400/400, voo=0, manut=0)↩Como se vê, é mostrada muita informação sobre o drone:
> B 40 400↩ Adicionado drone(cat=basico, id=1, cap=40, alc=400/400, voo=0, manut=0)↩ > B 30 200↩ Adicionado drone(cat=basico, id=2, cap=30, alc=200/200, voo=0, manut=0) > C 1 2↩ Adicionado drone(cat=coletivo, id=3, cap=70, alc=200/200, voo=0, manut=0, elems=(1 2))Como se vê, as características do novo drone são derivadas dos drones constituintes, usando as regras já explicadas. Também é mostrado um novo campo:
Tem dois argumentos: o id da encomenda a enviar e o id do drone a usar no transporte. O drone começa a voar imediatamente, se estiver disponível para o envio.
Um drone pode não estar disponível para um envio. Um drone básico não está disponível para um envio: se já estiver a voar; ou se estiver em manutenção; ou se fizer parte dum drone coletivo; ou se não tiver alcance suficiente para a encomenda; ou se não tiver capacidade de carga suficiente para a encomenda. Um drone básico não está disponível para um envio: se já estiver a voar; ou se não tiver alcance suficiente para a encomenda; ou se não tiver capacidade de carga suficiente para a encomenda.
Claro que uma encomenda que está no ar a ser transportada, ou que já foi enviada no passado, não pode ser enviada outra vez.
> D 1001 3↩ Encomenda 1001 enviada pelo drone 3↩
> E 60 120 -20↩ Adicionada encomenda(id=1001, peso=60, coord=(120,-20), cria=10, saida=0, entrega=0)↩Como se vê, é mostrada muita informação sobre a encomenda:
Se não existir registado qualquer drone ou encomenda, o comando escreve "Nao existem drones nem encomendas↩".
> L↩ drone(cat=basico, id=1, cap=40, alc=400/400, voo=0, manut=0)↩ drone(cat=basico, id=2, cap=30, alc=200/200, voo=0, manut=0)↩ drone(cat=coletivo, id=3, cap=70, alc=200/200, voo=4, manut=0, elems=(1 2))↩ encomenda(id=1001, peso=60, coord=(120,-20), cria=10, saida=22, entrega=42)↩ encomenda(id=1002, peso=30, coord=(20,20), cria=15, saida=0, entrega=0)↩
> R 1↩ Removido o drone 1
> T 10↩ O novo tempo e' 10↩ > E 60 120 -20↩ Adicionada encomenda(id=1001, peso=60, coord=(120,-20), cria=10, saida=0, entrega=0)↩ > B 30 300↩ Adicionado drone(cat=basico, id=1, cap=30, alc=300/300, voo=0, manut=0)↩ > B 50 400↩ Adicionado drone(cat=basico, id=2, cap=50, alc=400/400, voo=0, manut=0)↩ > C 1 2↩ Adicionado drone(cat=coletivo, id=3, cap=80, alc=300/300, voo=0, manut=0, elems=(1 2))↩ > T 2↩ O novo tempo e' 12↩ > D 1001 3↩ Encomenda 1001 enviada pelo drone 3↩ > L↩ drone(cat=basico, id=1, cap=30, alc=300/300, voo=26, manut=0)↩ drone(cat=basico, id=2, cap=50, alc=400/400, voo=26, manut=0)↩ drone(cat=coletivo, id=3, cap=80, alc=300/300, voo=26, manut=0, elems=(1 2))↩ encomenda(id=1001, peso=60, coord=(120,-20), cria=10, saida=12, entrega=0)↩ > T 10↩ O novo tempo e' 22↩ > L↩ drone(cat=basico, id=1, cap=30, alc=200/300, voo=16, manut=0)↩ drone(cat=basico, id=2, cap=50, alc=300/400, voo=16, manut=0)↩ drone(cat=coletivo, id=3, cap=80, alc=200/300, voo=16, manut=0, elems=(1 2))↩ encomenda(id=1001, peso=60, coord=(120,-20), cria=10, saida=12, entrega=0)↩ > T 15↩ O novo tempo e' 37↩ > L↩ drone(cat=basico, id=1, cap=30, alc=50/300, voo=1, manut=0)↩ drone(cat=basico, id=2, cap=50, alc=150/400, voo=1, manut=0)↩ drone(cat=coletivo, id=3, cap=80, alc=50/300, voo=1, manut=0, elems=(1 2))↩ encomenda(id=1001, peso=60, coord=(120,-20), cria=10, saida=12, entrega=25)↩ > T 2↩ O novo tempo e' 39↩ > L↩ drone(cat=basico, id=1, cap=30, alc=40/300, voo=0, manut=0)↩ drone(cat=basico, id=2, cap=50, alc=140/400, voo=0, manut=0)↩ drone(cat=coletivo, id=3, cap=80, alc=40/300, voo=0, manut=0, elems=(1 2))↩ encomenda(id=1001, peso=60, coord=(120,-20), cria=10, saida=12, entrega=25)↩ > R 3↩ Removido o drone 3↩ > L↩ drone(cat=basico, id=1, cap=30, alc=40/300, voo=0, manut=3)↩ drone(cat=basico, id=2, cap=50, alc=140/400, voo=0, manut=3)↩ encomenda(id=1001, peso=60, coord=(120,-20), cria=10, saida=12, entrega=25)↩ > T 2↩ O novo tempo e' 41↩ > L↩ drone(cat=basico, id=1, cap=30, alc=40/300, voo=0, manut=1)↩ drone(cat=basico, id=2, cap=50, alc=140/400, voo=0, manut=1)↩ encomenda(id=1001, peso=60, coord=(120,-20), cria=10, saida=12, entrega=25)↩ > T 1↩ O novo tempo e' 42↩ > L↩ drone(cat=basico, id=1, cap=30, alc=300/300, voo=0, manut=0)↩ drone(cat=basico, id=2, cap=50, alc=400/400, voo=0, manut=0)↩ encomenda(id=1001, peso=60, coord=(120,-20), cria=10, saida=12, entrega=25)↩
Eis como a nota será calculada:
A apreciação da qualidade, inclui pelo menos estes elementos:
A prova de avaliação escrita sobre o trabalho incide sobre a primeira parte do trabalho. A duração desta prova vai ser 20 minutos.
A listagem tem obrigatoriamente de corresponder ao código duma submissão que esteja presente no Mooshak, e cada aluno precisa de indicar o número dessa submissão na folha das respostas. O papel das listagem não se entrega no final da prova. Para corrigir as respostas dos alunos, os professores irão consultar o código das submissões dentro do próprio Mooshak.
Apesar da avaliação escrita incidir sobre a primeira parte do trabalho, será permitido e perfeitamente normal um aluno levar o código duma submissão recente da 2ª fase. As respostas serão corrigidas tendo por referência o código dessa submissão, esquecendo quaisquer outros fatores.
Passado o prazo de entrega do trabalho, muitos grupos serão dispensados de ter uma discussão presencial. Será então divulgada a lista dos grupos que vão ter realmente a discussão presencial.
O arquivo zip que o seu grupo submete não precisa de conter a pasta "TADs", e mesmo que a contenha, o Mooshak ignora-a. O Mooshak usa a sua própria pasta "TADs". Uma boa maneira, mas não a única, de criar o zip é através deste comando do linux/wsl:
zip drones.zip *.[ch]
O Mooshak compila o seu programa usando o seguinte comando:
gcc -o main *.c TADs/*/*.c -Wall -lm
Na fase 1, o Mooshak valida o seu programa usando 12 testes. Na fase 1 não existem testes secretos. Serão usados apenas os 12 testes divulgados.
Na fase 2, o Mooshak valida o seu programa usando 10 testes públicos, mais 10 testes que serão secretos até ao prazo de entrega final.
Eis os testes públicos: tests1.zip, tests2.zip [basta clicar para fazer download].
#define MAX_INT 4 int ints[MAX_INT], extra; int n = sscanf(linha, "%d %d %d %d %d", &ints[0], &ints[1], &ints[2], &ints[3], &extra);
O melhor é tentar definir apenas um TAD. Na struct colocar um campo booleano a distinguir o tipo do drone. A maioria dos campos da struct fica partilhada pelos dois tipos de drone; mas poderão existir alguns campos que só são usados por um determinado tipo de drone.
Se definir apenas um TAD, é boa ideia escrever duas funções de criação diferentes: criaBasicoDrone e criaCompostoDrone. [A palavra "Drone" aparece no final dos nomes para seguir a nossa regra de nomeação das funções dos TADs.]
Bom trabalho! Esperamos que goste.