Defina uma função max: R 3 R R por
máx(a, b)=l a se a>b b se b >= a
(a) Use essa função para escrever uma função recursiva LMax(L) que retorne o maior valor em L, em que L é uma lista de números.
(b) Demonstre que a sua função LMax funciona. Em outras palavras, demonstre que LMax (L) retorna o maior valor na lista L.

Passo 1

O enunciado define a função
max(a,b)= a &se a>b, b &se b>= a,
e pede (a) uma definição recursiva de LMax(L) que retorne o maior elemento de uma lista L de números, e (b) uma demonstração de que essa função de fato devolve o máximo de L. Vamos usar indução sobre o comprimento de L.

Passo 2

Definimos o caso base, em que a lista tem exatamente um elemento. Se
L=[a],
então não há outra escolha senão
LMax([a]) = a

Passo 3

Definimos o caso recursivo. Se a lista L tem pelo menos dois elementos, escrevemos
L = a ;::; L',
onde a é o primeiro elemento e L' é o restante da lista. Então definimos
LMax(a::L') = maxl(a,;LMax(L')r)

Passo 4

Para provar que LMax(L) realmente retorna o maior elemento de L, enunciamos a propriedade P(n):
“Para toda lista L de comprimento n>=1, LMax(L) é o maior elemento de L.”

Passo 5

Verificação de P(1) (base da indução). Se L=[a], então por definição LMax([a])=a, e a é claramente o maior (único) elemento de L. Logo P(1) vale.

Passo 6

Passo indutivo: suponha
Por definição de e todos os elementos de , ou seja, o maior de . Assim vale, completando a indução.

Resposta

(a) Para qualquer lista não vazia L,
LMax([a]) = a,
LMax(a::L') = maxl(a,;LMax(L')r)
(b) A prova por indução sobre o comprimento de L mostra que esse algoritmo devolve sempre o maior elemento da lista.

Exercícios de Livros Relacionados