DCC003: Algoritmos e Estruturas de Dados I
2013/1

Exercícios 8: Picos em Matrizes

Exercício 1. Considere o algoritmo a seguir para encontrar um pico numa matriz M de L linhas e C colunas.

1. Se L for 1 e se C for 1, retorne o único elemento como pico. Caso contrário continue no passo 2.
2. Seja i = L/2 e j = C/2 (os números da linha e da coluna no meio da matriz). Note que a linha e a coluna no meio da matriz formam uma cruz e dividem a matriz original em quatro sub-matrizes com um quarto do tamanho original.
3. Encontre o máximo global entre os elementos da linha i e da coluna j (o elemento máximo na cruz).
4. Se o máximo global encontrado no passo 3 for um pico na matriz original, retorne-o como pico. Caso contrário execute o passo 5.
5. Se o máximo global encontrado no passo 3 não for um pico na matriz original, então ele tem um vizinho maior que ele. Chame o algoritmo recursivamente na sub-matriz com o elemento maior que o máximo encontrado no passo 3. Note que o algoritmo recursivo irá operar apenas em um quarto da matriz original.

O algorítmo acima não funciona. (a) Explique qual o problema com o algoritmo acima e mostre um exemplo de matriz para o qual ele retorna a resposta errada (isto é, uma matriz onde o elemento retornado não é um pico). (b) Implemente uma versão correta do algoritmo e teste-o na matriz que você mostrou na letra (a).