É encorajado que vão falando com os docentes e outros colegas se tiverem dificuldades. No entanto, qualquer ajuda mais direta que tenham recebido de outros colegas deve ser reconhecida nos comentário do programa que submetem. Depois do prazo os problemas continuarão disponíveis no Mooshak, mas as submissões não contarão para a sua nota.
Cada aula vale 10% da nota desta componente. Como existem 12 aulas com submissões, pode ter pontuação máxima mesmo sem ter feito tudo.
Para um problema contar tem acertar todos os testes (ou seja, ter accepted). Mesmo que resolva todos os problemas, o máximo numa aula é de 100%.
Para ter 100% bastará sempre resolver os exercícios do guião principal.
Aula de Revisões/Preparação para o 1º Teste Prático
Depois de 3 semanas a prepararem e fazerem exames, chegou a hora de regressar às aulas do 2º semestre. Para tornar mais "leve" o vosso regresso a Estruturas de Dados, esta aula prática é essencialmente de revisões e preparação para o 1º teste prático (podem também relembrar as regras de avaliação desta unidade curricular). Cobre matéria já dada e versa problemas usados no ano anterior como exercícios de avaliação.
Exercício 1) Ciclos e epidemiologia
O primeiro problema aqui proposto foi usado o ano passado como exercício de submissão das aulas e é essencialmente sobre a primeira parte da matéria, de fundamentos de Java. Para o resolver basta no fundo saber usar ciclos.
Basta fazer um simples ciclo onde \(i\) vai tomando à vez todas as posições (exceto a primeira) e em cada passo obter \(valor[i] - valor[i-1]\).
Depois basta guardar o mínimo e máximo de desses incrementos e no final imprimir
Comece por fazer um ciclo como a da flag anterior para calcular a subida percentual em cada dia. Tenha cuidado com a divisão (se dividir dois inteiros vai obter apenas uma divisão inteira: pode fazer um cast para ober um valor com casas decimais, por exemplo)
O problema é resolúvel sem necessitar de variáveis auxiliares, mas se desejar pode por exemplo guardar as subidas num novo array de \(doubles\); chamemos a esse array \(subidas[]\)
Um período de baixa propagação começa numa posição \(i\) se \(subidas[i] \leq 5\%\) e \(subidas[i-1] \gt 5\%\) (ou se \(i=0\), ou seja se \(i\) for a primeira posição do array)
Um período de baixa propagação termina numa posição \(j\) se \(subidas[j] \leq 5\%\) e \(subidas[j+1] \gt 5\%\) (ou se \(j\) for última posição do array)
Se um período de baixa propagação começa na posição \(i\) e termina na posição \(j\), então o seu tamanho é igual a \(j-i+1\)
Cada vez que terminar um período de baixa propagação, incremente uma variável que conta quantos períodos existem e compare com a maior até agora (para que no final tenha o tamanho máximo)
Pode optar por imprimir logo ou criar uma variável (matriz de caracteres) para conter o resultado e só depois imprimir
A altura (nº linhas) do output é igual ao maior valor a dividir por 100
Depois é preciso percorrer todas as linhas e em cada linha percorrer as respetivas colunas (como saber se a j-ésima coluna da i-ésima linha tem um '.' ou um '#'?)
Exercício 2) Gollum e listas ligadas
O segundo problema aqui proposto foi também usado o ano passado como exercício de submissão das aulas e implica fazer alguns métodos de listas ligadas simples.
Note que não pode modificar a lista original, ou seja, não pode remover os seus elementos (ou se o fizer tem de voltar a colocá-los na lista, pela mesma ordem)
Existem várias maneiras de inverter, mas a mais fácil passar por ir percorrendo os nós um a um da lista original (do primeiro para o último, usando um simples ciclo) e ir inserindo os valores deles numa nova lista na ordem correcta (para ficar invertido, cada valor deve ser inserido... no início (com que método pode fazer isso?) Assim, o último valor inserido, será o primeiro da nova lista (e por aí adiante...)
Primeiro deve fazer um ciclo pela lista para contar o número de ocorrências, para criar um array com o tamanho respetivo (que será no final devolvido como retorno do método)
Se o número de ocorrências for zero, pode devolver \(null\)
Faça um segundo ciclo pela lista onde mantém também o índice da posição atual e se um valor de um nó for igual ao desejado (comparar com equals), então basta adicionar a posição atual ao array de posições que criou
Existem várias maneiras de fazer e aqui estão descritas duas hipóteses
Hipótese 1) fazer um método para retirar todas as cópias de um valor (é o ED193, se já o fez!); percorrer a lista \(toRemove\) e chamar o método criado anteriormente para cada um deles
Hipótese 2) percorrer a lista original e para cada um dos seus valores verificar se está contido em \(toRemove\) (e nesse caso remover)
Exercícios extra para consolidação de conhecimentos
Para ter ainda mais problemas se quiser treinar, ficam aqui os problemas usados no equivalente ao 1º teste prático no ano letivo anterior.
[ED237] Round-Robin(uso de API de listas, filas e pilhas) - disponível no "Volume 4 (Pilhas e Filas)"
Exercício de Desafio
Para esta semana disponibilizo um problema não muito complicado que foi usado como o 4º problema (o de valorização) no equivalente ao 1º teste prático do ano passado (para distinguir na gama cimeira das notas).