Como já perceberam, não tenho muita experiência com posts... Acabam saindo sempre muito grandes, mesmo eu tentando dividir em partes. Assim sendo, resolvi desistir da ideia de publicar uma seção por post, e vou começar a publicar um Exercício por post. Afinal de contas, menor que isso não pode ficar, né? Bem, aí vão o enunciado e a solução
Exercício 1.11
Uma função é definida com a regra f(n) = n, se n < 3, e f(n) = f(n-1) + 2f(n-2) + 3f(n-3), se n ≥ 3. Escreva um procedure que compute f por meio de um processo recursivo. Escreva um procedure que computa f por meio de um processo iterativo.
Solução: A solução que gera um processo recursivo é mera tradução da definição para a linguagem Scheme. O código é dado abaixo:
Agora, para a versão de f que gera um processo iterativo. Usando a regra, vemos que f(0) = 0, f(1) = 1, f(2) = 2, f(3) = 4, f(4) = 11, e assim sucessivamente. Vamos fazer uma definição análoga à definição iterativa para cálculo do número de Fibonacci. Se eu começar com
a = 0, b = 1 e c = 2, e executar as transformações a -> b, b -> c, e c-> c + 2b + 3a, n vezes, eu termino com a = f(n), b = f(n+1), e c = f(n+2). O código que faz isso é mostrado abaixo (com o cuidado de fazer f funcionar também para números negativos).
Nenhum comentário:
Postar um comentário