1.
Escreva em Scheme um procedimento denominado comb, com dois
argumentos (n e k), para calcular as combinações de
n elementos k a k.
Sabe-se que comb(n,k) = comb(n-1,k-1) + comb(n-1,k), quando
0<k<n, e que comb(n,k)=1
quando k=0 ou k=n.
(define comb
(lambda (n k)
(if (or (= k 0) (= k n))
1
(+ (comb (sub1 n) (sub1 k))
(comb (sub1 n) k)))))
2.
Considere o seguinte procedimento recursivo em Scheme:
(define misterio
(lambda (n)
(if (< n 10)
n
(* (remainder n 10)
(misterio (quotient n 10))))))
a) Qual é o resultado de (misterio 23)?
Em geral, qual é o resultado produzido pelo procedimento
misterio?
Suponha sempre n > 0.
(misterio 23) dá 6
(misterio n) dá o produto dos dígitos de n (na base 10)
b) Classifique o procedimento misterio quanto à ordem de crescimento espacial e temporal.
Ordem de crescimento temporal: O(número de digitos de n)
Ordem de crescimento espacial: O(número de digitos de n), porque gera
um processo recursivo
c) O processo gerado por este procedimento é recursivo. Modifique o procedimento por forma a gerar um processo iterativo.
(define misterio-iter
(lambda (n)
(misterio-aux n 1)))
(define misterio-aux
(lambda (n prod)
(if (< n 10)
(* n prod)
(misterio-aux (quotient n 10)
(* (remainder n 10) prod)))))