Mooshak #03 - Listas Pilhas e Filas
(semana de 22/11 a 26/11)
Nota Inicial
Os exercício do Mooshak desta aula não contam para nota e são completamente opcionais (a vossa prioridade deve ser primeiro completar os exercícios base das aulas práticas). Os exercícios aqui colocados destinam-se a quem quer ir mais além do que requisitos mínimos e quiser ter uma camada de submissão com avaliação automática, sendo que todas as semanas iremos colocar disponíveis novos problemas.
Para tornar tudo um pouco mais interessante, eu (Pedro Ribeiro) deixo desde já prometido que irei pagar uma refeição na minha companhia (uma francesinha no Capa Negra II) a três estudantes desta UC:
Os 2 estudantes com mais problemas corretamente submetidos no final do semestre (sob um código de conduta de não tentarem simplesmente "copiar código").
Um outro estudante que se tenha destacado nesta componente, segundo a minha avaliação (ex: resolveu os problemas mais difíceis, teve o código mais criativo, etc).
Espero para ver os vosses "dotes" algorítmicos ao longo destas semanas! :)
Problemas para submissão
Nesta unidade curricular vamos usar o sistema Mooshak como uma maneira opcional e adicional para avaliar automaticamente código.
Nesta aula foram disponibilizados os seguintes problemas:
Pode ler a frase usando por exemplo a função getline para ler uma linha inteira(não se esqueça de "escapar" o resto da linha anterior).
Para saber quantas palavras tem a linha pode por exemplo usar a função strtok ou criar uma stringstream com a linha lida para depois ler as palavras correspondentes (ou pode até contar os espaços, pois existe um único espaço entre palavras).
Agora é só simular o jogo a acontecer, e dados os limites baixos pode mesmo simulá-lo de forma naive. Entre várias maneiras sugerimos a seguinte:
Crie uma list<string> para conter os nomes das crianças
Para cada palavra que "contar" pode fazer a lista "avançar" retirando o primeiro nome e adicionando-o novamente no final.
Por exemplo, Paulo Raquel Carlos ficaria Raquel Carlos Paulo
Isto mantém na primeira posição da lista o nome "atual"
Depois contar o número correto de passos, retire o primeiro nome e volte a repetir o mesmo processo até a lista ficar com tamanho 1
No final é só verificar se a última criança é ou não o Carlos :)
Exercício 2) Um problema com pilhas
O segundo problema é semelhante ao que foi explicado nas aulas téoricas e pede para implementarem um pequeno interpretador de RPN - Reverse Polish Notation)
Literalmente o algoritmo para resolver é dado no enunciado :)
Para ler uma linha pode usar a função getline, como no problema anterior, e depois processar passo a passo usando por exemplo uma stringstream
Pode usar a implementação de pilhas do próprio C++ e usar por exemplo uma stack<int>
Para converter a string lida num inteiro a ser armazenado na stack pode usar por exemplo a função stoi
Não se esqueça de validar sempre o estado da pilha, quer durante (para uma operação ser aplicada é preciso que existam dois valores), quer após (no final é suposto só existir um número na pilha)
Exercício 3) Um problema com filas um "pouco" mais complicado (mas não muito)
Pode por exemplo criar uma classe ou estrutura para guardar cada avião: o nome, o minuto de chegada e o seu atraso (para depois poder imprimir)
Pode simular o processo e em cada passo seguir o que pede o enunciado
Tenha cuidado com a maneira como o tempo avança na sua simulação: se avançar apenas de 1 em 1 minuto poderá exceder o limite de tempo; note como como o número de aviões em si (máximo de 100 a levantar e 100 a aterrar) é baixo em relação aos seus tempos de chegada (que podem chegar ao limite do int); a ideia é que avance sempre para o próximo evento a considerar: se estiver em tempo=42 minutos e não acontecer nada até ao tempo 108, não vale a pena avançar de 1 em 1 minuto, certo? :)
Exercício de Desafio
Para esta semana o desafio tem a ver com a eficiência algorítmica. Deve tentar resolver o seguinte problema, que está disponível para submissão no Mooshak (enunciado em inglês):
Este problema é semelhante ao [AED 09] Pim, Pam, Pum, mas com uma grande diferença que o torna (muito) mais complicado: o tamanho do círculo com pessoas a eliminar chega a 10 milhões, pelo que uma solução "bruta", que simule todos os passos, não irá ser suficientemente eficiente (passaria nos testes "pequenos", mas excederia o limite de tempo nos testes "grandes").
Para este problema, vou apenas dizer que este estilo de "eliminação" é conhecida como Josephus problem. Se precisarem de mais dicas avisem. Fico à espera de ver os vossos programas :)
