Exercício 1.9
Cada um dos dois procedures a seguir define um método para adicionar dois inteiros positivos, em termos dos procedures inc, que incrementa seu argumento em 1 unidade, e dec, que decrementa seu argumento de 1.
Usando o modelo da substituição, ilustre o processo gerado por cada procedure na avaliação de
(+ 4 5)
. Esses processos são iterativos ou recursivos?Solução:Primeiramente, vamos ver o processo de avaliação para
(+ 4 5)
, utilizando a primeira definição apresentada:Ora, vimos que, para a primeira definição, processo primeiro expande as expressões, depois calcula os resultados. O processo é, portanto, recursivo. Mais especificamente, é linearmente recursivo em a.
Agora, vejamos a avaliação de
(+ 4 5)
, usando o segundo procedure mostrado:Vimos, portanto, que a segunda definição de + apresentada desenvolve um processo iterativo.
Dica: quem quiser testar no DrScheme, deve definir
inc
e dec
em termos de -
. Como você estará redefinindo +
, definir inc
em termos do +
redefinido vai causar uma recursão infinita (pense e descobrirá). As definições de inc
e dec
devem ser:No exercício, é mais fácil considerar
inc
e dec
como primitivas...Exercício 1.10
O procedure abaixo computa uma função matemática denominada função de Ackerman.
Quais os valores das seguintes expressões?
(A 1 10)
(A 2 4)
(A 3 3)
Considere os seguintes procedures, em que A é o procedure definido acima:
(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))
(define (k n) (* 5 n n))
Dê expressões matemáticas concisas para as funções computadas pelos procedures f, g e h para valores positivos de n. Por exemplo,
(k n)
computa 5n^2.Solução: A maneira mais fácil de saber o valor das expressões
(A 1 10)
, (A 2 4)
e (A 3 3)
é definir a função A no DrScheme e calcular seus valores pela janela de interações... Mas creio que não seja esse o objetivo do exercício. Vou resolver as perguntas finais, sobre f, g e h, e depois faço a resolução das expressões manualmente.Expressão para
(f n) = (A 0 n)
Hipótese:
(f n) = 2*n
.Prova: Muito simples. O enunciado fala em valores positivos de n (portanto 0 estaria fora), mas vamos fazer com valores não-negativos. Vamos fazer uma avaliação parcial de A, substituindo x por 0 e y por n. Temos, então, que
(f n)
é equivalente a:Repare que nem inseri a expressão correspondente ao else, pois como a segunda cláusula do cond sempre avaliará para
#t
, a cláusula do else é inacessível. De qualquer forma, para n = 0
, temos (f n) = 0
(ou seja, 2*0), e para n diferente de zero, a segunda cláusula do cond avalia para #t
e o resultado da expressão é (* 2 n)
. Ou seja, de qualquer forma, temos (f n) = (* 2 n)
.Expressão para
(g n) = (A 1 n)
Analogamente ao anterior:
Considerando valores positivos de n, vemos que
(g n)
as duas primeiras cláusulas do cond
sempre avaliarão para #f
, de modo que o resultado sempre será equivalente à expressão abaixo.Mas a expressão do corpo de g ainda pode ser simplificada, notando que
(A 0 n) = (f n) = (* 2 n)
, e (A 1 (- n 1)) = (g (- n 1))
. Temos, portanto:Daí, fica fácil ver por indução que, de fato,
(g n) 2^n
.Expressão para
(h n) = (A 2 n)
Podemos fazer da mesma maneira que fizemos para g. Vamos pular os passos semelhantes e chegar direto em:
Novamente, podemos notar que
(A 1 n) = 2^n
e (A 2 (- n 1)) = (h (- n 1))
, ou seja:Também por indução, dá pra ver que a fórmula é
(2^ (2^ (2^...)))
, em que o número de 2 que aparece é exatamente n. Assim, para (h 1) = 2
,(h 2) = (2^ 2)
e (h 3) = (2^ (2^ 2)) = 16
.Agora, vamos à avaliação das expressões que o enunciado pede.
Avaliação de
(A 1 10)
Avaliação de
(A 2 4)
Avaliação de
(A 3 3)
Olá Reginaldo
ResponderExcluirEstou estudando SICP também, e estava empacada na 1.10... obrigada pela excelente resolução! É uma boa maneira de resolver e me ajudou a entender a questão, valeu! :)
@MiWi: Legal... já faz um tempo que não atualizava o blog e nem sabia se ainda era útil pra alguém... é bom saber. vou voltar a resolver e postar novas soluções... Obrigado :)
ResponderExcluirFala Reginaldo,
ResponderExcluirLembrei dos tempos do Mokarzel, quando eu não tinha safado o que a função de Ackerman para x=2 era. Fiquei umas 2 horas pra chegar no f(x)= 2^(f(x-1)) mas saiu.
Grande abraço