Matématica discreta: Recusão

Aula 14 – Matemática Discreta 2 - 1º semestre/2014 – Trabalho em sala - Valor: 4 pontos

1) Os números de Fibonacci constituem uma sequência de números na qual os dois primeiros elementos são 0 e 1 e os demais, a soma dos dois elementos imediatamente anteriores na sequencia. Como exemplo, a sequência formada pelos 10 primeiros números de Fibonacci é: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. Mais precisamente, é possível definir os números de Fibonacci pela seguinte relação de recorrência:

FIBO (1) = 0.
FIBO (2) = 1.
FIBO (n) = FIBO (n-1) + FIBO (n-2), para n>2.

Considerando que o programa utilize uma função recursiva para gerar um determinado número de Fibonacci, quantas chamadas são feitas à função FIBO para computar FIBO(5)?

A) 09 B) 12 C) 15 D) 24 E) 25

2) Para a seguinte relação de recorrência, quais são os cinco primeiros valores da seqüência?

M(1) = 1 M(2) = 2 M(n) = M(n-1) + M (n-2) para n >=2

A) 1, 2, 4, 6, 10
B) 1, 2, 6, 10, 16
C) 1, 2, 3, 10, 14
D) 1, 2, 3, 5, 8
E) 1, 2, 6, 14, 34

3) Escreva a relação de recorrência para o seguinte problema:

Membros antigos da sociedade de Pitágoras definiram números figurados como sendo o número de pontos em uma certa configuração geométrica. Os primeiros números triangulares são 1, 3, 6 e 10 e são semelhantes ao diagrama da figura abaixo:

* * * * * * * * * *
* * * * * * * * * *
1 3 6 10

4) Dada a seguinte relação de recorrência, escreva os cinco primeiros valores da série. M(1) = 2 M(2) = 3 M(n) = 2 . M(n-1) + 2. M(n-2) para n >=3

5) A população de uma cidade é de 6000 habitantes. Sabe-se que a cada ano nascem 5% de crianças em relação à população do ano anterior (nessa cidade