Testando várias maneiras de calcular o máximo.
Faça download do código dado nas aulas para calcular o máximo de um intervalo dado de um array. Compile, teste e verifique que percebe exactamente como o código está a funcionar. Sugestão: no início de cada função recursiva imprima o valor de start e end se quiser ver como as chamadas recursivas estão a ser feitas (conselho válido para todas as funções recursivas)
TestMax - 3 versões para descobrir o máximo de um intervalo de um array (uma iterativa e duas recursivas)
Calculando recursivamente a soma de um array.
Usando como base o código do máximo, implemente e teste duas versões recursivas de um método para calcular a soma do elementos entre start e end do array v[]:
static int sumRec1(int v[], int start, int end) - divide o array entre o primeiro elemento e o resto do array
static int sumRec2(int v[], int start, int end) - divide o array entre metade esquerda e metade direita
Fica tudo igual excepto a operação de combinar os resultados. Ao invés de ficar com o máximo... basta somar!
Exercício 2) Capicuas
[ver slide 10]
Testando código de inverter um array.
Faça download do código dado nas aulas para inverter um array de forma recursiva. Compile, teste e verifique que percebe exactamente como o código está a funcionar.
TestReverse - invertendo um array (versão recursiva)
Capicuas.
Usando como base o código da inversão, implemente e teste um método recursivo para saber se o array representa uma capicua(uma capicua é um número que é igual quando lido da direita para esquerda ou da esquerda para a direita).
static boolean capicua(int v[], int start, int end) - devolve true se v é capicua ou false caso contrário
Exemplos:
capicua([1,2,3,2,1], 0, 4) deve devolver true
capicua([5,8,8,5], 0, 3) deve devolver true
capicua([1,2,3,1], 0, 3) deve devolver false
capicua([5,8,7,5], 0, 3) deve devolver false
Fica tudo muito parecido, mas agora é preciso trabalhar com valores booleanos
Para ser capicua é preciso que o primeiro seja igual ao último E que o resto seja capicua (como fazer um E lógico em Java?).
No caso base (palavra de tamanho inferior a 2) qual é agora o resultado?
Exercício 3) Flood Fill
[ver slides 11 a 14]
Testando código de flood fill.
Faça download do código dado nas aulas para fazer "flood fill" de forma recursiva. Compile, teste e verifique que percebe exactamente como o código está a funcionar. Note que precisa de dar input ao programa (um exemplo é fornecido na página com o código). Se o ficheiro com input se chamasse floodfill.txt, uma maneira de executar o programa seria: java TestFloodFill < floodfill.txt.
Resolvendo um problema.
Usando como base o código anterior, resolva e submeta o problema [ED200] Contagem de Células, disponível no Mooshak de EDados no "Volume 5 (Complexidade e Recursividade)".
O tipo de input é quase igual pelo que o código é aplicável quase directamente
Cuidado com a noção de vizinhança. Para o problema [ED200], as células também são adjacentes diagonalmente. O que precisa de mudar no código na função recursiva?
Para descobrir o micróbio de tamanho máximo, basta contar a "mancha" de cada posição possível da matriz e guardar o máximo.
Para cada nova matriz, o que é preciso "reinicializar"? Qual o estado da matriz visited[][] depois de verificada a matriz anterior? Como deve esta antes de iniciar um novo flood fill?
Exercício 4) Subconjuntos
[ver slides 15 a 17]
Testando código de subconjuntos.
Faça download do código dado nas aulas para gerar todos os subconjuntos de um dado array.
Resolvendo um problema.
Usando como base o código anterior, resolva e submeta o problema [ED201] PlayList, disponível no Mooshak de EDados no "Volume 5 (Complexidade e Recursividade)".
A que equivale tentar exaustivamente todas as possíveis playlists? No fundo queremos todos os subconjuntos!
Para testar uma playlist, ao invés de imprimir um subconjunto, queremos somar a duração das músicas desse conjunto
De todos os subconjuntos, guardamos o melhor (o que tiver maior soma e for menor que D)
Nota: esta solução de pesquisa exaustiva gerando todos os subconjuntos é exponencial - em cadeiras como DAA vai aprender como poderia ter resolvido este problema de forma polinomial usando programação dinâmica
Exercício 5) Permutações
[ver slides 18 e 19]
Testando código de permutações.
Faça download do código dado nas aulas para gerar todas as permutações de um dado array.
Resolvendo um problema.
Usando como base o código anterior, resolva e submeta o problema [ED202] Procurando Pokemons, disponível no Mooshak de EDados no "Volume 5 (Complexidade e Recursividade)".
A que equivale tentar exaustivamente todos possiveis caminhos? No fundo queremos todos as permutações dos sitios, pois um caminho fica completamente definido pela ordem em que visitamos os locais.
Para testar uma permutação, ao invés de imprimir, queremos somar as distâncias percorridas
De todas as permutações, guardamos a melhor (a que tiver menor soma)
Nota: este problema corresponde na sua essência a uma versão euclideana do Traveling Salesman Problem, que é um problema complicado e sem ser conhecida uma maneira polinomial (no tempo) de encontrar uma solução ótima.
Exercícios extra para consolidação de conhecimentos
Implemente um programa para resolver recursivamente o puzzle das 8 raínhas, imprimindo todas as soluções possíveis. O puzzle implica descobrir todas as maneiras em que é possível colocar 8 raínhas num tabuleiro de xadrez de tal modo que nenhuma raínha possa atacar outra raínha, ou seja, não existem duas raínhas na mesma linha, coluna ou diagonal. Um exemplo de solução seria:
Tal como explicado na parte final de uma aula teórica, Uma maneira de representar as posições pode ser por exemplo... uma permutação de 8 números, representando as linhas das raínhas. Por exemplo, (5,3,1,7,2,8,6,4) representa a imagem anterior. Ao gerar as permutações, pode logo cortar os casos onde já sabe que nunca obterá solução (verificando se a nova raínha colocada não "ataca" nenhuma das raínhas já colocadas.
Compile e teste o código exemplo do MergeSort, procurando perceber tudo o que está a ser feito.
Usando como guia o código do MergeSort, implemente uma versão recursiva do QuickSort. Escolha em cada iteração um pivot aleatório (pode usar por exemplo a classe Random)
Implemente um programa recursivo para gerar todos os possíveis quadrados mágicos de um dado tamanho n: um quadrado de n por n preenchido com todos os inteiros de 1 a n2 de tal modo que cada célula contenha um número diferente, e que cada linha, coluna ou diagonal dê a mesma soma.
Exercício de Desafio
O exercicio de desafio desta semana está pensado para poder ser usado com recursividade e está disponível para submissão no Mooshak, no volume de Desafios:
A solução óbvia com dois ciclos é Θ(n2) e não passa no tempo, pelo que é preciso algo melhor. A ideia é usar como "esqueleto" o Merge Sort e ao mesmo tempo que ordenamos... contamos as inversões - tudo isto em Θ(n log n).
Não vou dizer mais para não tirar a piada a fazerem o exercício, mas se precisarem de mais dicas, digam :)
