Seja
uma lista, como na Definição 3.3. Defina uma função numérica
como se segue.
B. Se
, um único elemento, então
.
R. Se
,
para alguma lista
, então
.
(a) Mostre as etapas de um cálculo “descendente”, como no Exemplo 3.28, para encontrar o valor de
veni, vidi, vici
.
(b) O que o valor de
the diz a respeito da lista
, em geral?
(c) Demonstre a sua afirmação da parte (b), usando indução.
B. Se
R. Se
(a) Mostre as etapas de um cálculo “descendente”, como no Exemplo 3.28, para encontrar o valor de
(b) O que o valor de
(c) Demonstre a sua afirmação da parte (b), usando indução.
Passo 1
O enunciado define recursivamente uma função numérica
sobre listas
:
– Base (B): se tem um único elemento, então
– Base (B): se
– Recursão ®: se
(isto é,
é obtida de
acrescentando-se o elemento
), então
Precisamos de (a) calcular
por descida, (b) interpretar o que
revela sobre
em geral e (c) provar essa interpretação por indução.
Passo 2
Para
fazemos descida:
Passo 3
Note que a cada elemento extraído após o primeiro somos obrigados a concatenar os dígitos
. Se
, o número de dígitos de
é
Logo a partir de
(que é um inteiro formado só por uns) podemos recuperar
via
Passo 4
Prova por indução em
.
Base (
)
Se então
tem
dígito, conforme desejado.
Se
Passo 5
Passo indutivo
Suponha que para toda lista com
vale “
tem
dígitos”. Seja agora
com
. Então
Suponha que para toda lista
e o número de dígitos de
é
Assim a propriedade vale para
e, por indução, para todo
.
Resposta
(a)
\n
(b) é um inteiro formado exclusivamente por dígitos
, de comprimento
, de modo que
.\n
(c) Demonstrado por indução nos passos 4 e 5.
(b)
(c) Demonstrado por indução nos passos 4 e 5.