UNIVERSIDADE FEDERAL DE UBERLÂNDIA
Faculdade de Computação
Disciplina : Matemática para Ciência da Computação – 2º Semestre 2009
Professora : Sandra Aparecida de Amo
Lista de Exercícios nº 10
1.
a) Encontre uma relação de recorrência para o número de cadeias de bits de
extensão n onde os 0s aparecem em pares E os 1s aparecem aos pares.
b) Quais são as condições iniciais?
2.
a) Encontre uma relação de recorrência para o número de cadeias de bits de
extensão n onde os 0s aparecem em pares OU os 1s aparecem aos pares.
b) Quais são as condições iniciais?
3.
a) Encontre uma relação de recorrência para o número de maneiras de subir n
degraus se a pessoa que estiver subindo as escadas pode subir um, dois ou três
degraus por vez?
b) Quais são as condições iniciais?
4. Uma máquina de vender selos só aceita moedas de 1 real, notas de 2 reais e 5
reais.
a) Encontre uma relação de recorrência para o número de maneiras de
pagar uma quantia de n reais na máquina ? (a ordem em que as moedas ou
notas são inseridas na máquina é relevante).
b) Quais as condições iniciais ?
5. Uma cadeia que contém apenas 0s, 1s e 2s é chamada de cadeia ternária.
a) Encontre uma relação de recorrência para o número de cadeias ternárias
que não contenham dois zeros consecutivos.
b) Quais as condições iniciais ?