Aula_015_Relação de Recorrência

Prévia do material em texto

15.1
Módulo: Relação de Recorrência 
15.2Relação de recorrência
Objetivo:
Apresentar a técnica recursiva que permite reduzir 
um problema envolvendo n objetos a outro problema 
semelhante com n−1 objetos, que por sua vez é 
possível reduzir a outro problema do mesmo tipo 
com n−2 objetos, e assim pode-se ir reduzindo a 
problemas com menos elementos até obter um 
problema de simples resolução.
Muitos problemas de contagem são modelados e 
resolvidos usando relações de recorrência.
Importância:
15.3Relação de Recorrência
Aula 15
Introdução
Conteúdo:
Definição
Relação de Fibonacci
Torre de Hanoi
Método de substituição
15.4Relação de Recorrência
(a) O primeiro e o último termo da expressão é um
 dígito (0, 1, 2, ..., 9)
(b) Não podem estar juntos símbolos aritméticos (+,−,×,÷)
Determine o número de expressões válidas.
• Ilustração:
5×3−
6÷+2 } expressões não válidas
0187
1+99 } expressões válidas
Introdução:
Exemplo 1: 
Neste problema uma expressão é válida se verifica:
Considere expressões de 4 elementos formadas por 
dígitos ou por símbolos das operações aritméticas. 
N4 : número de expressões válidas de comprimento 4
Exemplo 1 (continuação): 
15.5Relação de Recorrência: Introdução
Resolução:
___ ___ ___ ___
DígitoPossibilidades
Caso I
(total N3)
Caso II
(total N2)
ou
expressão válida de
comprimento 2
Símbolo
aritmético
+
N3 : número de expressões válidas de comprimento 3
N2 : número de expressões válidas de comprimento 2
N1 : número de expressões válidas de comprimento 1
expressão válida de
comprimento 3
Logo, N4 = 10N3 + 40N2
Resolução (continuação): 
Caso I
Cálculo de N4 a partir de N3 e N2
15.6Relação de Recorrência: Introdução
___ ___ ___ ___
expressão
válida
0
1
9
…
dígito
 Número de possibilidades: N2 × 4 × 10
Caso II
___ ___ ___ ___
expressão
válida
símbolo dígito
+
−
×
÷
0
1
9
…
 Número de possibilidades: N3 × 10
15.7Relação de Recorrência: Introdução
N3 = 10N2 + 40N1 
Logo,
Cálculo de N3:
___ ___ ___ 
10
ou
expressão válida 
de extensão 2
(total N2)
expressão válida 
de extensão 1
(total N1)
+
símbolo
aritmético
Resolução (continuação): 
Portanto, pode-se calcular N4 a partir da relação 
encontrada N4 = 10N3 + 40N2
Portanto,
N2 = 10N1
 número de expressões válidas de 
 cumprimento 0
Como N0:
= 0
15.8Relação de Recorrência: Introdução
Observe que N1 = 10
podemos escrever
N2 = 10N1 + 40N0
Resolução (continuação): 
Cálculo de N2:
___ ___ 
10
expressão válida de 
extensão 1 (total N1)
15.9Relação de Recorrência: Introdução
(relação: Nk = 10Nk-1 + 40Nk-2 , k = 4, 3, 2)
Resolução (continuação): 
N3 = 10 × 100 + 40 × 10 = 1400
⇐
N0 = 0, N1 = 10
⇐N2 = 10 × 10 = 100
Resumo:
N4 = 10 × 1400 + 40 × 100 = 18000
Resposta: O número de expressões válidas é
• Nk: número de expressões válidas de extensão k, 
 k = 0, 1, 2, 3, 4 
• Objetivo do problema: Cálculo de N4.
• Relações obtidas: N4 = 10N3 + 40N2
N3 = 10N2 + 40N1
N2 = 10N1 + 40N0
relação de recorrência Nk = 10Nk-1 + 40Nk-2
15.10Relação de Recorrência
Definição:
Uma relação de recorrência é uma fórmula que
relaciona um número an a alguns dos seus
predecessores an-1, an-2, ... , ak, ... , a0 
• Ilustração:
No exemplo 1, n = 4, ak = Nk , k = 4, 3, 2, 1, 0 
Resolução: 
Sn = 1 + 2 + ... + (n − 1) + n
Sn-1
15.11Relação de Recorrência: Definição
A relação de recorrência é Sn = Sn-1 + n
Resposta:
Observação:
A relação de recorrência é também denominada
equação de diferenças.
Exemplo 2: 
Seja Sn a soma dos primeiros n números naturais. 
Determine a relação de recorrência em termos de Sn-1.
Nenhum coelho morre durante este processo.(c)
Determine o número de pares de coelhos ao final
de 12 meses sob as seguintes condições:
15.12Relação de Recorrência
(b) Todo mês cada par de coelhos com pelo menos 2
meses produz um novo par de coelhos de sexo oposto.
(a) Inicialmente tem-se um único par de coelhos,
um macho e uma fêmea recém nascidos.
Relação de Fibonacci:
O problema proposto por Leonardo de Pisa, conhecido 
como Fibonacci, em um livro publicado em 1202 é o 
seguinte: 
Resolução:
15.13Relação de Recorrência: Relação de Fibonacci
Fn : número de pares de coelhos no final do mês n (n ∈ )N
F1 = 1 {p0
p0
p0início
1
 
mês:
p0 p12 F2 = F1 + 1 {p1
{p0
p0 p2 p13 F3 = F2 + 1 {p2
F0 : número de pares no início do processo
Logo, a relação de recorrência é Fk = Fk-1 + Fk-2 (k = 2, 3, 4, ...)
e as condições iniciais são F0 = 1 e F1 = 1
F0 = 1 {p0
4 F4 = F3 + 1 + 1 = F3 + F2{p4
{p3
p0 p3 p2 p1 p4
5 F5 = F4 + F3p0 p5 p3 p2 p6 p1 p7 p4
Resposta: O número de pares de coelhos ao final de 12
meses é 233.
15.14Relação de Recorrência: Relação de Fibonacci
Observação: Os números de Fibonacci, Fn , aparecem
frequentemente em problemas combinatórios. 
Resolução (continuação):
Cálculo de F12:
Usamos Fk = Fk-1 + Fk-2 para k = 2, 3, ... , 12: 
F4 = F3 + F2 = 5 F5 = F4 + F3 = 8 F6 = F5 + F4 = 13
F7 = F6 + F5 = 21 F8 = F7 + F6 = 34 F9 = F8 + F7 = 55
F10 = F9 + F8 = 89 F11 = F10 + F9 = 144 F12 = F11 + F10 = 233
F1 = 1 F2 = F1 + F0 = 2 F3 = F2 + F1 = 3
1. Torre de Hanoi simplificada
Torre de Hanoi:
(b) Não é permitido colocar um disco maior em cima
 de um menor.
(a) Só é permitido mover um disco do topo para um
 outro eixo.
Determine o menor número de movimentos que são
necessários para passar 3 discos colocados em um eixo, 
em ordem crescente de tamanho (de cima para baixo), 
para um outro eixo. Pode ser usado de forma auxiliar 
um terceiro eixo. Devem ser respeitadas as seguintes
regras:
15.15Relação de Recorrência
Torre de Hanoi simplificada (continuação)
• Ilustração
figura
inicial
1
3
2
15.16Relação de Recorrência: Torre de Hanoi
número mínimo
de movimentos
figura
final
1
3
2
não é permitido
1
3
2
1
3
2
figura
inicial
1
3
2
figura
intermediáriapermitido
1
3
2
Torre de Hanoi simplificada (continuação):
Resolução:
figura inicial
15.17Relação de Recorrência: Torre de Hanoi
Resposta:
O menor número de movimentos para passar 3 discos
de um eixo a um outro seguindo as regras é 7.
1
3
2 1
3
2
1
1
3
2
2
1
3
2
3
1
3
2
4
1
3
2
6
1
3
2
5
figura final
1
3
2
7
Resolução (continuação):
Releitura do raciocínio:
Tk: número mínimo de movimentos necessários para 
 passar k discos de um eixo a outro nas condições do
 problema (k = 2, 3)
Cálculo de T3 (Algoritmo)
15.18Relação de Recorrência: Torre de Hanoi
Passo 1 - Mover os 2 primeiros discos (de cima para baixo)
 do primeiro para o terceiro eixo (k = 3 2 = k−1)
 movimentos
T2 = 3
1
3
21
3
2
{2
figura inicial figura final - passo 1
movimentos
1
1
3
21
3
2
figura final
 passo 1
figura final
 passo 2
Resolução (continuação):
15.19Relação de Recorrência: Torre de Hanoi
Passo 2 - Mover o disco maior do primeiro para o
 segundo eixo
Logo,
T3 = T2 + 1 + T2 = 2T2 + 1 = 7
1
3
21
3
2
figura final
 passo 2
figura final
movimentos
T2 = 3
15.20Relação de Recorrência: Torre de Hanoi
Resolução (continuação):
Passo 3 - Mover os 2 discos do terceiro eixo para o
 segundo eixo 
2. Caso geral
(b) Não é permitido colocar um disco maior em cima
 deum menor.
15.21Relação de Recorrência: Torre de Hanoi
Determine o menor número de movimentos que são
necessários para passar n discos colocados em um eixo, 
em ordem crescente de tamanho (de cima para baixo), 
para um outro eixo. Pode ser usado de forma auxiliar 
um terceiro eixo. Devem ser respeitadas as seguintes
regras:
(a) Só é permitido mover um disco do topo para um
 outro eixo.
Tk: número mínimo de movimentos necessários para passar k discos de 
 um eixo a outro nas condições do problema (k = 1, 2, ... , n)
Resolução (algoritmo recursivo):
15.22Relação de Recorrência: Torre de Hanoi
(é feito recursivamente em Tn-1 movimentos)
(precisa-se de 1 movimento)
(como no passo 1, é feito em Tn-1 movimentos)
Passo 1 - Mover os primeiros n−1 discos do topo do 
primeiro eixo para o terceiro eixo 
Passo 2 - Mover o disco maior do primeiro eixo para o
segundo eixo 
Passo 3 - Mover os n−1 discos do terceiro eixo para o
segundo eixo 
Resposta: A partir do algoritmo obtemos que o número 
de movimentos necessários para resolver a torre de 
Hanoi está dado pela relação de recorrência Tn = 2Tn-1 + 1 
com condição inicial T1 = 1.
15.23Relação de Recorrência: Torre de Hanoi
Exemplo 3: Aplicando o algoritmo recursivo, faça todos os movimentos 
correspondentes ao problema da torre de Hanoi com n = 4 (T4 = 2T3 + 1 = 15).
Resposta Voltar
(T3 = 7 movimentos)
Passo 1 - Mover os primeiros 3 discos do topo do eixo 1 para o 3
figura inicial
2 3 4 5 6
2
31 1
2
3 1
2
3 1
2
3 1
2
3
1
1
2
3 1
2
3
7
1
2
3
início passo 3 figura final
9
2
31
10 11 12 13 14 15
1
2
3 1
2
3 1
2
3 1 2
3 1
2
3 1
2
3
2
31
Passo 3 - Mover os discos do eixo 3 para o eixo 2 (T3 = 7 movimentos)
(1 movimento)
Passo 2 - Mover o disco maior do eixo 1 para o eixo 3
 início
passo 2
2
31
2
31
8
Precisamos calcular T2, T3, T4, ... até T64,
Dado histórico: 
Este problema foi inventado em 1883 pelo matemático
francês Edouard Lucas. O número de discos era 64. 
15.24Relação de Recorrência: Torre de Hanoi
demorado.
o que é bem
Observação: 
Podemos calcular T64 usando a relação de recorrência
Tk = 2Tk-1 + 1 e a condição inicial T1 = 1.
Pergunta: 
É possível encontrar uma fórmula fechada para Tn 
que nos permita calcular rapidamente o número de 
movimentos que são necessários para resolver o 
problema da Torre de Hanoi para um dado número 
de discos n?
Resposta:
Sim. A fórmula é obtida considerando a relação de
recorrência Tn = 2Tn-1 + 1 e um método de substituição.
15.25Relação de Recorrência: Torre de Hanoi
Método de Substituição:
Tn = 2Tn-1 + 1 (Tn-1 = 2Tn-2 + 1)
15.26Relação de Recorrência
(Tn-2 = 2Tn-3 + 1)
. . .
= 23Tn-3 + 2
2 + 2 + 1
= 2[ 2Tn-2 + 1 ] + 1
= 22Tn-2 + 2 + 1
(Tn-3 = 2Tn-4 + 1)
. . .
= 2kTn-k + 2
k-1 + 2k-2 + ... + 1
. . .
= 2n-1 + 2n-2 + 22 + 2 + 1
= 1 − 2
n
______
 1 − 2
= 2n − 1
(progressão geométrica)
(Tn-k = 2Tn-k-1 + 1)
= 2n-1T1 + 2
n-2 + ... + 22 + 2 + 1 =(k=n-1)
=1
15.27Relação de Recorrência: Método de Substituição
Voltar Prova
Propriedade Tn = 2
n − 1 para todo n ∈ 
N
• Ilustração: T64 = 2
64 − 1 > 18 × 1012 
Prova (princípio de indução matemática):
P(n): Tn = 2
n − 1 
Logo, P(k + 1) é verdadeira
(1) Base de indução: P(1) é verdadeira pois T1 = 1 = 2
1 − 1
(2) Hipótese de indução (HI): P(k): Tk = 2
k − 1 é verdadeira
(3) P(k) verdadeira P(k + 1): Tk+1 = 2
k+1 − 1 é verdadeira
⇐
N
Portanto, pelo princípio de indução matemática temos que 
P(n) é verdadeira para todo n ∈ .
Desenvolvendo
Pela relação de recorrência resulta
Tk+1 = 2Tk + 1
HI
= 2(2k − 1) + 1 = 2k+1 − 2 + 1 = 2k+1 − 1
Observação: 
O método de substituição usado para resolver algumas 
relações de recorrência também é denominado de
suposição e verificação.
(Tn = 2
n − 1)
15.28Relação de Recorrência: Método de Substituição
De fato:
Pela substituição obtém-se uma expressão fechada 
que é a suposição ou conjectura 
A verificação consiste em provar que a conjectura 
é verdadeira (a prova por indução completa de
Tn = 2
n − 1).
Exemplo 4: 
São desenhados no plano n ovais verificando as condições:
(a) dois ovais se interceptam em exatamente 2 pontos
(b) três ovais não se interceptam no mesmo ponto
Em quantas regiões esses ovais dividem o plano?
15.29Relação de Recorrência: Método de Substituição
• Ilustração:
•
•
•
•
•
•
•
•regiao
 2
regiao 1
n = 1 n = 3
1
2
3
4
7
6
5
8
•
•
•
•
•
•
1
2
3
4
n = 2
•
•
Exemplo 4 (continuação): 
Resolução: 
ak : número de regiões em que o plano é dividido 
 por k ovais (k = 1, 2, ... , n) 
Condição inicial
a1 = 2
15.30Relação de Recorrência: Método de Substituição
Relação de recorrência
ak = ak-1 + 2 (k − 1) k = n, n−1, ... , 2
= a1 + 2 [ 1 + 2 + ... (n − 1) ] 
k = n-1
Exemplo 4 (continuação): 
Obtenção de uma fórmula fechada 
(método de substituição)
. . .
= an-k + 2[ (n − k) + (n − k + 1) + ... + (n − 1) ]. . .
= 2 + (n − 1)n= 2 + 2 (n − 1)n_______
 2
15.31Relação de Recorrência: Método de Substituição
an = an-1 + 2(n − 1)
= an-2 + 2(n − 2) + 2(n − 1)
= an-3 + 2(n − 3) + 2(n − 2) + 2(n − 1)
15.32Relação de Recorrência: Método de Substituição
VoltarDesafio
Base de indução P(1): a1 = 2 + (1 − 1).1 é verdadeira pois a1 = 2
Passo da indução: Devemos provar que
De fato, assuma que P(k) é verdadeira (hipótese indutiva, HI), então pela
relação de recorrência temos que
ak+1 = ak + 2(k + 1 − 1)
= 2 + (k − 1)k + 2k = 2 + [ (k − 1) + 2 ]k
= 2 + (k + 1)k
HI
Logo, P(k + 1) é verdadeira
Pelo princípio de indução matemática resulta que
P(n): an = 2 + (n − 1)n é verdadeira para todo n ∈ N
P(k): ak = 2 + (k − 1)k é verdadeira P(k + 1): ak+1 = 2 + k(k + 1) é verdadeira
⇑
Exemplo 4 (continuação): 
Verificação: indução em n (desafio)
Conjectura
an = 2 + (n − 1)n para todo n ∈ N
15.33Relação de Recorrência: Método de Substituição
Desafio: 
Faça o desenho das 14 regiões determinadas pelos 
4 ovais.
• Ilustração
Se n = 4 então o plano fica dividido em a4 = 2 + 3.4 = 14
regiões.
Exemplo 4 (continuação): 
Resposta:
O número de regiões em que n ovais dividem o plano
é an = 2 + (n − 1)n
15.34Relação de Recorrência
Resumo:
Definição de relação de recorrência (ou equação de 
diferenças)
Relação de Fibonacci (1202) 
É uma fórmula que relaciona um número an a alguns
de seus predecessores an-1, an-2, ak, ...
Fn: número de pares de coelhos no final do mês n sob
 as condições do problema
Condições iniciais F0 = 1 , F1 = 1
Relação de recorrência Fn = Fn−1 + Fn−2
15.35Relação de Recorrência: Resumo
Torre de Hanoi (E. Lucas, 1883) 
Tn: número mínimo de movimentos necessários para
 passar n discos ordenados de um eixo a um outro 
 eixo segundo as condições do problema.
 
Condições iniciais T1 = 1
Relação de recorrência Tn = 2Tn-1 + 1
Fórmula fechada (resolução da relação de recorrência)
Tn = 2
n − 1
Método de substituição (ou de suposição e verificação) 
• Permite resolver algumas relações de recorrência a 
 partir da relação e de suas condições iniciais.
• Através de substituições sucessivas chega-se a uma
 conjectura (ou suposição) que precisa ser verificada.