ApostilaAlgoritmosII - ProfPauloEustaquio

Prévia do material em texto

1 
 
 
 
 
 
 
 
 
 
 
 
IME 04-06319 - ALGORITMOS 
 
 
 
 
 
 
 
 Paulo Eustáquio Duarte Pinto 
 
 Universidade Estadual do Rio de Janeiro 
 Instituto de Matemática 
 Departamento de Informática e Ciência da Computação 
 
 Rio de Janeiro, agosto de 2008 
 
 
 2 
CONTEÚDO 
 
 
0. INTRODUÇÃO 
 
1. RECURSÃO 
1.1 Conceitos básicos 
1.2 Problemas clássicos 
1.3 Análise da Recursão 
1.4 Exercícios Propostos 
 
2. BACKTRACKING 
2.1 Conceitos básicos 
2.2 Problemas clássicos 
2.3 Jogos 
2.4 Exercícios Propostos 
 
3. PROGRAMAÇÃO DINÂMICA 
3.1 Conceitos básicos 
3.2 Problemas clássicos 
3.3 Exercícios Propostos 
 
4. MÉTODO GULOSO 
4.1 Conceitos básicos 
4.2 Problemas clássicos 
4.3 Exercícios Propostos 
 
5. PROBLEMAS NP-COMPLETOS 
 
 
 
 3 
0. INTRODUÇÃO 
 
 A ênfase deste curso é no estudo de uma ampla variedade de 
Algoritmos: métodos de solução de problemas adequados para implementação 
em computadores. Serão mostrados os problemas clássicos de cada método 
estudado, bem como uma visão simplificada da complexidade desses algoritmos. 
Sempre que possível serão também abordados problemas propostos nas 
diversas maratonas de programação da ACM. 
 
0.1 Introdução à complexidade de Algoritmos - Notações O e ΩΩΩΩ 
 
 Duas características muito importantes dos algoritmos são o seu tempo 
de execução e a memória requerida. Quando se faz um algoritmo para resolver 
determinado problema, não basta que o algoritmo esteja correto. É importante 
que ele possa ser executado em um tempo razoável e dentro das restrições de 
memória existentes. Além disso, ele deve permanecer viável, à medida que o 
tempo passa, quando a quantidade de dados envolvida normalmente cresce. O 
estudo do comportamento dos algoritmos em termos do tempo de execução e 
memória, em função do crescimento dos dados envolvidos, denomina-se 
Complexidade de Algoritmos. Os parâmetros estudados normalmente são os 
seguintes: 
a) Complexidade de pior caso - caracterização do tempo de 
execuçãomáximo, para determinado tamanho da entrada, bem como 
das características da entrada que levam a esse tempo máximo. Este 
é o principal parâmetro para se avaliar um algoritmo. 
b) Complexidade de caso médio - caracterização do tempo de execução 
médio do algoritmo, para determinado tamanho da entrada, 
considerando a média de todas as possibilidades. Em muitas situações 
este parâmetro é útil. 
c) Complexidade de melhor caso - caracterização do tempo de 
execução mínimo, para determinado tamanho da entrada, bem como 
das características da entrada que levam a esse tempo mínimo. 
d) Memória requerida para se executar o algoritmo para determinado 
tamanho de entrada. 
 
A determinação da complexidade de pior caso teria que ser feita 
contando-se todas as instruções executadas e o tempo de execução de cada 
uma delas, considerando-se a pior entrada possível. Normalmente isso não é 
viável. O que se faz é determinar um limite superior para esse tempo, o mais 
próximo possível da realidade. Para tanto, fixa-se o estudo na instrução mais 
 4 
executada do algoritmo e determina-se uma função t(n), que dá a variação do 
tempo de execução em função de n, o tamanho da entrada. 
 
O limite superior descrito anteriormente é definido pela conceituação 
O(t(n)), definida da seguinte forma: 
Sejam f, h duas funções reais positivas de variável inteira n. Diz-se que 
f é O(h), escrevendo-se f = O(h), quando existir uma constante c > 0 e um valor 
inteiro n0, tal que 
 n > n0 => f(n) ≤ c.g(n) . 
 
Exs: 
 
f = n3 – 1 => f = O (n3) = O (n4) 
f = 5 + 10 log n + 3 log2 n => f = O (log2 n ) 
 
 Por convenção, os algoritmos que tenham complexidade de pior caso 
iguais ou inferiores a O(nk) são considerados eficientes. Algoritmos cuja 
complexidade sejam, por exemplo, O(2n) são considerados ineficientes. 
 
 Outro ponto importante é o seguinte: dado um problema, pode-se ter 
encontrado um algoritmo para resolvê-lo. Surge a pergunta se esse é o melhor 
algoritmo possível. Algumas vezes essa resposta pode ser obtida com a ajuda 
cos conceitos dados a seguir. 
 
 Def: Dadas as funções sobre variáveis inteiras f e g. Dizemos que 
f é ΩΩΩΩ (g) , se existirem uma constante c e um número n0 tal que 
 
 f(n) ≥ c.g(n) , para todo n > n0. 
 
Se P é um problema, então dizemos que o limite inferior para P é dado 
por uma função h tal que a complexidade de pior caso de qualquer algoritmo 
que resolva P é Ω (h). 
 
Desta forma, quando conseguimos determinar o limite inferior para um 
problema e, ao mesmo tempo, conseguimos um algoritmo cuja complexidade de 
pior caso seja igual a esse limite, então estamos diante de um algoritmo ótimo, 
pois não se pode conseguir algoritmo com complexidade mais baixa que o 
mesmo. 
 
 
 5 
 
 
0.2 Bibliografia recomendada 
 
 Esta apostila está fortemente baseada no primeiro livro indicado abaixo 
e não pretende substituir um livro texto, necessário para se complementar a 
compreensão de cada tema abordado. Os seguintes livros são indicados: 
 
Algorithms R. Sedgewick;Addison-Wesley, 1988 
Introduction To Algorithms T. H. Cormen et all; McGraw Hill, 1998 
Estrut. de Dados e Seus Algoritmos J.L.Szwarcfiter, LTC 1994 
 
Recomenda-se, também, o acesso aos seguintes sites que abordam 
problemas das maratonas de programação ACM e da Olimpíada de Informática: 
 http://icpc.baylor.edu 
 http://acm.uva.es 
 http://olympiads.win.tue.nl/ioi 
 http://olimpiada.ic.unicamp.br 
 
 
 6 
1. RECURSÃO 
 
1.1 Conceitos básicos 
Esta técnica de construção de algoritmos consiste basicamente em se 
subdividir um problema em problemas menores de mesma natureza que o 
problema original e obter a solução como uma composição das soluções dos 
problemas menores. Para a solução dos problemas menores adota-se a mesma 
estratégia de subdivisão, até o nível em que o subproblema seja muito simples, 
quando então sua solução é exibida, geralmente com poucos passos. 
A maneira de subdividir e de compor a solução pode ser diferente para 
cada caso. A seguir são mostrados dois exemplos clássicos de algoritmos 
recursivos: Fatorial e Fibonacci. 
O cálculo de fatorial tem a seguinte recursão: 
 
Fatorial (p): (A1.1) 
Início: 
 Se (p = 0) Então 
 Retornar 1 
 Senão 
 Retornar p.Fatorial(p-1); 
Fim; 
 
Nesta recursão o único problema resolvido diretamente é o de 0! . Os 
demais são resolvidos a partir da solução de cada problema imediatamente 
menor. 
Para a da série de Fibonacci, temos: 
 
Fibonacci(p): (A1.2) 
Início: 
 Se (p ≤ 1) Então 
 Retornar p 
 Senão 
 Retornar Fibonacci(p-1) + Fibonacci(p-2); 
Fim; 
 
 7 
Há quatro outras visões sobre a técnica de recursão, que certamente 
complementam essa visão inicial: 
a) A técnica pode ser vista como uma maneira de se resolver problemas 
de "trás para frente", isto é: a solução enfatiza os passos finais para a 
solução do problema, supondo problemas menores resolvidos. No caso Fatorial, 
para se obter Fatorial(n), a idéia é multiplicar Fatorial (n-1) por n . 
 
b) A técnica pode ser ainda imaginada como o equivalente matemático da 
indução finita, onde, para se demonstrar fatos matemáticos usam-se duas 
etapas: 
b.1.1) Mostra-se que a hipótese vale para valores particulares e pequenos 
de n (0, 1, etc). 
b.1.2) Supondo-se a hipótese verdadeira para todos os valores inferiores 
a n, demonstra-se que ela continua valendo para n. 
Na recursão, temos que: 
b.2.1) Exibe-se um algoritmo para resolver casos particulares e pequenos 
(0, 1, etc). Os problemas pequenos são chamados “problemas infantís”. 
b.2.2) Exibe-se um algoritmo para achar a solução do problema “grande” 
a partir da composição de problemas menores. 
 
c) A técnica é o equivalente procedural da formulação de recorrências 
(funções recursivas), onde, de forma análoga ao ítem b), uma função é definida 
em duas partes. Na primeira, é dada uma fórmula fechada para um ou mais 
valores de n. Na segunda, a definição da funçãopara n é feita a partir da 
mesma função aplicada a valores menores que n, para valores superiores aos da 
primeira parte. Outra relação de recursão com recorrência é que muitas 
propriedades de soluções recursivas são obtidas com o uso de recorrências. 
 
d) Os procedimentos recursivos são aqueles que "chamam a sí mesmo". 
É claro, então, que a chamada a sí mesmo sempre se dá no contexto de buscar 
a solução de problemas menores, para compor a solução do maior. Além disso 
todo procedimento recursivo tem que ter também uma chamada externa. 
 
Note que todo algoritmo recursivo tem uma solução não recursiva 
equivalente. Muitas vezes, entretanto, a expressão recursiva é mais natural e 
mais clara, como para os exemplos mostrados a seguir. 
 
 8 
1.2 Problemas clássicos 
 
Neste tópico são apresentados os seguintes algoritmos clássicos com 
solução recursiva: 
a) Torre de Hanói 
b) Quicksort 
c) Mínimo e Máximo 
d) Cálculo de Combinação 
e) Torneio 
 
1.2.1 Torre de Hanói 
O problema baseia-se em um jogo infantil, onde há n pratos de tamanhos 
diferentes, com um furo no meio e três varetas A, B e C, que possibilitam que 
esses pratos possam ser empilhados em cada uma delas. O empilhamento só 
pode ser feito colocando-se pratos menores em cima de maiores. Inicialmente 
todos os pratos estão na vareta A. O problema é levar esses pratos para a 
vareta C, podendo usar as três varetas como empilhamento temporário. 
 
 
 
 A B C 
 
Esse problema tem a seguinte solução recursiva: 
 
Hanoi(n, A, B, C); (A1.3) 
Início: 
 Se (n > 0) Então 
 Hanoi (n-1, A, C, B); 
 Mover topo de A para C; 
 Hanoi (n-1, B, A, C); 
Fim; 
 
Qualquer solução não recursiva para este problema é muito mais 
complicada que a mostrada acima. A complexidade desse algoritmo é O(2n), não 
sendo, portanto, um algoritmo eficiente. Entretanto isso é o melhor que pode 
ser feito, pois o problema é, em sí, exponencial (!). 
 
No exemplo, com os pratos numerados de 3 a 1, de baixo para cima, a 
solução seria: 
 
 
 9 
 Mover 1 de A p/ C; → Mover 2 de A p/ B; → Mover 1 de C para B; 
 (Resolvido o problema para 2 pratos em B); 
 Mover 3 de A para C; 
 (Resolver novamente o problema de 2 pratos, só que p/ C): 
 Mover 1 de B p/ A; → Mover 2 de B p/ C; → Mover 1 de A p/ C; 
 
 
1.2.2 Quicksort 
É considerado o melhor algoritmo de ordenação e foi um dos primeiros 
algoritmos recursivos propostos. A idéia é fazer, sucessivamente, partições em 
subvetores, de forma que a parte esquerda contenha sempre elementos 
menores ou iguais aos da direita. O problema simples é quando o tamanho de 
uma partição é 1. A partição baseia-se em escolher um elemento como um pivô, 
fazendo-se trocas para colocar maiores ou iguais de um lado e menores ou 
iguais do outro. 
 
Sort(E, D); (A1.4) 
Início: 
 Se (D > E) Então 
 Particao(E, D, I, J); 
 Sort(E, J); 
 Sort(I, D); 
Fim; 
 
Procedimento Particao (E, D, I, J) /* Baseada no elem. do meio */ 
 Início: 
 I ← E; J ← D; t ← A[ (E+D)/2 ]; 
 Enquanto (I ≤ J): 
 Enquanto (A[I] < t): I ← I + 1; Fe; 
 Enquanto (t < A[J]): J ← J - 1; Fe; 
 Se (I ≤ J) Então 
 Troca_Elem(I, J); I ← I + 1; J ← J - 1; 
 Fe; 
 Fim; 
 
A seguir é dado um exemplo, mostrando os elementos envolvidos em 
comparações e trocas(estas indicadas em vermelho). 
 
 
Passo 1 2 3 4 5 6 7 8 9 10 11 12 
 10 
 E X E M P L O F A C I L 
 E X E M P L O F A C I L Partição (1,12) 
1 E L E I C A F O L P M X (1,7) (8,12) 
 E L E I C A F Partição (1, 7) 
2 E F E A C I L (1,5) (6,7) 
 E F E A C Partição(1,5) 
3 C A E F E (1,2) (3,3) (4,5) 
 C A Partição (1,2) 
4 A C (1,1) (2,2) 
 F E Partição(4,5) 
5 E F (4,4) (5,5) 
 I L Partição(6,7) 
6 I L (6,6) (7,7) 
 O L P M X Partição(8,12) 
7 O L M P X (8,10) (11,12) 
 O L M Partição(8,10) 
8 L O M (8,8) (9,10) 
 O M Partição(9,10) 
9 M O (9,9) (10,10) 
 P X Partição(11,12) 
10 P X (11,11) (12,12) 
 A C E E F I L L M O P X Situação Final 
 
 a) Análise do Algoritmo 
 
 a.1) Complexidade: 
 Melhor caso = Vetor Ordenado; NC =~nlog2n = O(n log2n) 
 Pior caso = Há várias possibilidades. Vetor em “Zig Zag”, p. 
 Ex. NC =~ n2/2 = O(n2) 
 Caso Médio: NC =~ nlog2n = O(n log2n) 
 a.2) Estabilidade: Algoritmo não estável 
 a.3) Situações Especiais: Algoritmo de uso amplo, extremamente 
rápido. 
 a.4) Memória necessária: pilha de recursão (log2n). 
 
b) Observações: 
 
b.1) Número de comparações: 42 
 11 
 Número de trocas: 16 
b.2) Este é um dos mais antigos e estudados algoritmos na 
Informática, tendo sido desenvolvido inicialmente por Hoare, em 1962. 
 b.3) Notar o mecanismo de partição (1,5), (1,2) e (11,12). No 
primeiro caso, o subvetor é dividido em 3 partes (ao final J = 2, I = 4); no 
segundo caso, o vetor é subdividido em 2 partes (ao final J = 1, I = 2); no 
terceiro caso, o vetor também é subdvidido em 2 partes (mas ao final J = 10 
(!?) e I = 12). 
 
O algoritmo tem complexidade O(n2), pior que de alguns outros 
algoritmos de ordenação. Entretanto sua grande importância deriva do fato de 
o pior caso é algo raro de acontecer. A complexidade de caso médio é O(nlogn), 
e o algoritmo é muito rápido para o caso médio. 
 
1.2.3 Mínimo e Máximo 
O problema é determinar os valores mínimo e máximo de um conjunto de 
números S. Esse problema tem uma solução trivial que é se fazer dois “loops” 
para encontrar separadamente os valores mínimo e máximo, executando 
exatamente 2n-2 comparações. O seguinte algoritmo recursivo permite uma 
melhora desse resultado: 
 
MinMax (S); (A1.5) 
Início: 
 Seja S = [a1,..., an] 
 Se (|S| = 1) Então Retornar (a1, a1); 
 Senão Se (|S| = 2) Então 
 Se (a1 > a2) Então Retornar (a2 , a1); 
 Senão Retornar (a1, a2 ); 
 Senão 
 m ← Int(|S| /2); 
 (b1, c1 ) ← MinMax(S1 = [a1,..., am]); 
 (b2, c2 ) ← MinMax(S2 = [am+1 ,... an]); 
 Retornar (min{ b1, b2}, max{c1, c2 }); 
Fim; 
 
Esta solução recursiva necessita apenas de (3n/2 - 2) comparações, mas 
a prova desse resultado fica como exercício. Esse resultado permite, então 
formular um algoritmo não recursivo com igual número de comparações, que é o 
seguinte: criam-se dois vetores, um de mínimos e outro de máximos. Esses 
vetores são preenchidos a partir da comparação, dois a dois, dos elementos 
 12 
iniciais. O elemento perdedor vai para o vetor de mínimos e o vencedos, para o 
de máximos. Verifica-se, então, o menor dos mínimos e o maior dos máximos. O 
total de comparações, é então: 
n/2 + n/2 -1 + n/2 - 1 ≅ 3n/2 - 2. 
 
 
1.2.4 Cálculo de Combinação 
O cálculo de número de combinações é simples, mas envolve um grande 
número de operações de multiplicação e divisão. Dependendo da ordem em que 
as operações são realizadas e da linguagem de implementação, pode-se 
facilmente "estourar" a capacidade numérica do ambiente e obter resultados 
errados. Isso acontece, por exemplo, no cálculo de Comb(50,2), se for 
implementada diretamente a fórmula clássica. 
A recursão fornece uma alternativa para algumas situações, bastando-se 
observar que 
 
Comb(n,p) = Comb(n,p-1)*(n-p+1)/p, 
 
o que sugere imediatamente a implementação a seguir: 
 
Comb(n, p); (A1.6) 
Início: 
 Se (p = 1) Então 
 Retornar n; 
 Senão 
 Retornar Comb(n, p-1)*(n-p+1)/p; 
Fim; 
 
Com essa implementação, muitas situações que dariam erro usando-se a 
fórmula clássica, passam a funcionar corretamente, como no caso do exemplo 
mencionado. A complexidade do algoritmo é O(p). 
Outra possibilidade é considerar Comb(n,p) = Comb(n-1,p)*n/(n-p), o que 
sugere a seguinte versão alternativa, com complexidade O(n): 
 
Comb(n, p); (A1.7) 
Início: 
 Se (n = p) Então 
 Retornar 1; 
 Senão 
 Retornar Comb(n-1, p)*n/(n-p); 
 13 
Fim; 
 
 
1.2.5 Torneio 
Um problema de organização de torneioscom n competidores, onde 
todos competidores jogam entre sí, é planejar as rodadas de forma que haja o 
menor número delas. Quando n é par, queremos que haja (n - 1) rodadas, e em 
cada rodada todos os times jogam. Quando n é impar então há n rodadas, sendo 
que em cada rodada jogam (n - 1) times e um deles fica "bye". Neste último 
caso, pode-se considerar que exista mais um time no grupo, que será 
considerado o emparelhamento "bye", de forma que admitiremos que haja 
sempre um número n par de competidores. 
Uma solução para o problema pode ser construir uma matriz R, n x n, 
onde a primeira coluna da matriz contenha os times e as colunas 2 a n, indiquem 
as rodadas de 1 a (n - 1). Cada elemento R(i, j) da matriz indica que R(i, j) é o 
adversário do time i na rodada j - 1. Vejamos um exemplo para n = 4. 
 
r1 r2 r3 r4 
1 2 3 4 
2 1 4 3 
3 4 1 2 
4 3 2 1 
 
Uma matriz R desse tipo tem as seguintes propriedades: 
 
a) R[i,1] ← i 
b) Todas as linhas são permutações dos elementos 1,2...n 
c) Todas as colunas são permutações dos elementos 1, 2...n 
d) Se j > 1, R[i,j] = t ⇒⇒⇒⇒ R[t,j] = i 
 
A essência do emparelhamento é expressa pela propriedade d). 
 
 
Este problema tem uma solução interessante recursiva quando n é 
potência de 2. O quadro abaixo ilustra a solução para n = 8: 
 
 
r1 r2 r3 r4 r5 r6 r7 r8 
1 2 3 4 5 6 7 8 
 14 
2 1 4 3 6 5 8 7 
3 4 1 2 7 8 5 6 
4 3 2 1 8 7 6 5 
5 6 7 8 1 2 3 4 
6 5 8 7 2 1 4 3 
7 8 5 6 3 4 1 2 
8 7 6 5 4 3 2 1 
 
 
Pode-se observar a seguinte simetria nessa tabela: dividindo-a em 4 
seções iguais, vê-se que a seção esquerda superior é igual à direita inferior e 
que a esquerda inferior é igual à direita superior. Além disso, a seção esquerda 
inferior corresponde à esquerda superior, somando-se n/2 aos números 
respectivos. Pode-se verificar que essa simetria é recursiva, quando se 
substitui um quadro pela seção esquerda superior, agora com número de 
elementos dividido por 2. O Esquema abaixo ilustra a composição recursiva: 
 
 
 I III 
 II IV 
 
A recursão é a seguinte: 
A matriz é dividida em 4 quadrantes iguais. O quadrantes I é preendhido 
recursivamente. Os demais quadrantes são assim obtidos: 
a) O quadrante II é copiado do quadrante I, com o acréscimo de n/2 a 
cada elemento. 
b) O quadrante III é uma cópia do II. 
c) O quadrante IV é uma cópia do I. 
A recursão se encerra quando se chega ao tamanho 1. Então é preenchido com 
o número 1. 
Notar que essa solução preserva as propriedades necessárias à matriz. 
 
Isso sugere o algoritmo a seguir, que usa uma matriz R n x n. m indica o 
tamanho da submatriz, Evidentemente, a chamada externa é: Torneio (n). 
 
Torneio (m): (A1.8) 
Início: 
 15 
 Se (m = 1) Então 
R[1,1] ← 1; 
 Senão 
 p ← m/2; 
 Torneio(p); 
 Para i de 1 até p: 
 Para j de 1 até p: 
 R[i + p, j] ← R[i, j] + p; 
R[i, j + p] ← R[i + p, j]; 
 R[i + p, j + p] ← R[i, j]; 
 Fp; 
 Fp; 
 Fim; 
 
O algoritmo tem, evidentemente, complexidade O(n2). 
O argumento a seguir mostra que a recursão está correta, 
considerando-se que o problema esteja resolvido para o quadrante I. 
Realmente, a composição das soluções gera um conjunto de rodadas como o 
desejado, pois: 
a) nas n/2 rodadas finais, cada competidor da metade 1 compete com 
todos os competidores da metade 2 e vice-versa. 
b) em cada uma dessas rodadas participam todos os competidores, por 
construção da tabela. 
c) as atribuições dos jogos são coerentes, considerando-se as duas 
metades, também por construção simétrica da tabela. 
 
Para n potência de 2, este problema tem outra solução recursiva, 
levemente diferente da apresentada, que consiste do seguinte: 
a) preenche-se recursivamente o quadrante I. O problema elementar é 
como no caso anterior. 
b) O quadrante II é preenchido como no caso anterior. 
c) O quadrante III é preenchido com permutações circulares dos 
elementos do quadrante II. 
d) O quadrante IV é preenchido de forma forçada pelo preenchimento 
do quadranto III (ver a propriedade d necessária à matriz). A figura abaixo 
exemplifica a idéia. 
 
 
r1 r2 r3 r4 r5 r6 r7 r8 
1 2 3 4 5 6 7 8 
 16 
2 1 4 3 6 7 8 5 
3 4 1 2 7 8 5 6 
4 3 2 1 8 5 6 7 
5 6 7 8 1 4 3 2 
6 5 8 7 2 1 4 3 
7 8 5 6 3 2 1 4 
8 7 6 5 4 3 2 1 
 
Finalmente, uma solução recursiva pode ser estabelecida para qualquer 
número de elementos, a partir da idéia deste último algoritmo. O número de 
rodadas será (n - 1) quando n for par ou n quando ímpar. Neste último caso 
pode-se imaginar que há um competidor adicional "bye", que participa dos 
emparelhamentos, de forma que podemos considerar o número de 
competidores um número par. Não há maiores dificuldades na recursão quando 
n é da forma n = 4k, para algum inteiro k, pois a solução acima aplica-se 
diretamente. A situação problemática é para números da forma: n = 4k + 2, 
porque, neste caso, a primeira metade da tabela tem tamanho n/2 x (n/2+1), o 
que geraria uma solução contendo n rodadas, que não é o objetivo perseguido. 
Vamos verificar, entretanto, que há uma forma de contornar esse 
incoveniente, eliminando uma das colunas dos quadrantes III e IV. 
 
 17 
Torneio (m): (A1.8) 
Início: 
 Se (m = 1) Então R[1, 1] ← 1 
 Senão Se (m ímpar) Então 
Torneio (m+1); 
 Se (m = n) Então 
Considera o emparelhamento com (m+1) como “bye”; 
 Senão 
 p ← m/2; 
 Torneio (p); 
 Se (p ímpar) Então q ← p + 1 
 Senão q ← p; 
 Para i de 1 a p 
 Para j de 1 a q: 
 R[i + p, j] ← R[i, j] + p; 
 Se (R[i + p, j] = m) Então R[i + p, 0] ← j; 
 Fp; 
 Para j de 1 até p: 
R[i, j + q] ← p + 1 + (i + j – 2) mod p; 
 R[p + 1 + (i + j – 2) mod p, j + q] ← i; 
 Fp; 
 Fp; 
 Se (p ímpar) Então 
 Para i de 1 a ma: 
 R[i, R[i, 0] ] ← R[i, q + 1]; 
 Para j de (q + 1) a (q + p): 
 R[i, j] ← R[i, j+1]; 
 Fp; 
 Fp; 
 Fim; 
 
 
 
A recursão pode ser assim explicada: 
 
a) Se n for ímpar, resolve-se o problema para n+1 e, no final, abandona-
se a última linha e substitui-se o emparelhamento com o último 
número pelo emparelhamento “bye”. 
b) Resolve-se, recursivamente o problema para n/2. 
 18 
c) Preenche-se os quadrantes II, III e IV conforme a segunda solução 
mostrada anteriormente para potências de 2, ou seja: o quadrante II 
é uma cópia do quadrante I, adicionando-se n/2 a todos os elementos. 
Caso o elemento seja “bye”, o correspondente também é tornado 
“bye”. O quadrante III é preenchido com permutações circulares dos 
números n/2+1 a n. O quadrante IV é preenchido de maneira forçada. 
d) Quando n é da forma n = 4k+2, temos alguns emparelhamentos “bye” 
indesejados nos quadrantes I e II, conforme descrito. Além disso a 
solução contém n rodadas. Mas podemos eliminar a primeira coluna 
dos quadrantes III e IV. Podemos observar que esta coluna contém 
os números com a seguinte ordenação: n/2+1, n/2+2...n, 1, 2, ...n/2. 
Cada par (n/2+i, i), contendo um elemento do quadrante III e outro 
do quadrante IV, pode ser movido para a coluna do “bye” pois, pela 
simetria envolvida, essa coluna é a mesma para o par. Assim, 
consegue-se eliminar uma coluna e temos uma solução em n-1 rodadas, 
que era o objetivo inicial. 
 
Vejamos como se resolveria o problema para n = 5. 
Como 5 é ímpar, resolvemos o problema para n1 = 6. Para tanto, começa-
se fazendo a chamada recursiva para resolver o problema para n2 = 3. Como 3 é 
ímpar, resolve-se o problema para n3 = 4, que faz a chamada recursiva para 
n4 = 2, com chamada para n5 = 1 e depois obtendo: 
 
r1 r2 
1 2 
2 1 
 
A partir dessa solução, obtem-se sem dificuldade a solução para 
n3 = 4: 
r1 r2 r3 r4 
1 2 3 4 
2 1 4 3 
3 4 1 2 
4 3 2 1 
 
Como o bojetivo era a solução para n2 = 3, elimina-se a última linha e 
transforma-se o emparelhamento com 4 em emparelhamento “bye”, obtendo: 
 
 
r1 r2 r3 r4 
 19 
1 2 3 - 
2 1 - 3 
3 - 1 2 
 
 Agora volta-se ao problema para n1 = 6. Aplicando-se o procedimento 
mencionado,obtemos: 
 
r1 r2 r3 r4 r5 r6 r7 
1 2 3 - 4 5 6 
2 1 - 3 5 6 4 
3 - 1 2 6 4 5 
4 5 6 - 1 3 2 
5 4 - 6 2 1 3 
6 - 4 5 3 2 1 
 
Como 6 é um número da forma 4k+2, temos uma solução indesejada em 6 
rodadas. A seguir, move-se os pares (4, 1), (5, 2), (6, 3), da coluna r5 
para as colunas respectivas de “bye” e depois elimina-se essa coluna, 
redefinindo as colunas r6 e r7, finalizando a solução para n1 = 6. 
 
r1 r2 r3 r4 r5 r6 r7 
1 2 3 4 5 6 
2 1 5 3 6 4 
3 6 1 2 4 5 
4 5 6 1 3 2 
5 4 2 6 1 3 
6 3 4 5 2 1 
 
r1 r2 r3 r4 r5 r6 
1 2 3 4 5 6 
2 1 5 3 6 4 
3 6 1 2 4 5 
4 5 6 1 3 2 
5 4 2 6 1 3 
6 3 4 5 2 1 
 
 
 20 
 Para obter a solução final (n = 5), elimina-se a linha 6 e transforma-se os 
emparelhamentos com 6 para emparelhamentos “bye”, obtendo, então: 
 
 
r1 r2 r3 r4 r5 r6 
1 2 3 4 5 - 
2 1 5 3 - 4 
3 - 1 2 4 5 
4 5 - 1 3 2 
5 4 2 - 1 3 
 
 Um esboço do algoritmo é mostrado a seguir: 
Torneio (m); 
 Início: 
 Se (m = 1) Então R[1,1] ← 1; 
 Senão Se (m ímpar) Então 
 Torneio(m+1); 
 Transforma emparelhamento com (m+1) em “bye”; 
 Senão 
Torneio (m/2); 
Copia Quadrante I p/ Quadrante II, acrescentando m/2; 
 Gera permutação circular no quadrante III, para os elementos 
(m/2 + 1) a m; 
Preenche de maneira forçada o Quadrante IV; 
Se (m/2 ímpar) Então 
 Move os elementos da coluna m/2+2 para a coluna de “bye”; 
Move uma posição para a esquerda as colunas m/2+3 a m+1; 
 Fim; 
 
 
1.3 Análise da Recursão 
Serão apresentados três aspectos importantes para a análise do método 
de Recursão. O primeiro é o critério de balanceamento, que serve como 
orientação para se gerar bons programas recursivos, em geral. O segundo é 
uma ferramenta para análise da complexidade da recursão. O terceiro é uma 
ferramenta para evitar recursões ineficientes. 
 
 21 
1.3.1 Balanceamento 
 
Um critério importante na sudivisão de um problema em problemas 
menores é o do Balanceamento: os problemas devem ter tamanhos iguais ou 
bem próximos, sob pena de se obter soluções ineficientes. Vejamos dois 
algoritmos distintos de ordenação: Mergesort e Bubblesort. 
 
O algoritmo Mergesort pode ser expresso pela recursão a seguir: 
 
Mergesort(E, D); (A1.9) 
Início: 
 Se D > E Então 
 m ← (E+D)/2; 
 Mergesort(E, m); 
 Mergesort(m+1, D); 
 Merge (E, m, D); 
Fim; 
Chamada externa: Merge(1,n); 
 
No algoritmo Mergesort, cada problema de tamanho n foi dividido em 
dois subproblemas de tamanho aproximado n/2. A subdivisão é, pois, 
balanceada e a complexidade do algoritmo é O(nlogn). 
 
Já o algoritmo Bubblesort, pode ser expresso por: 
 
Bubblesort(m); (A1.10) 
Início: 
 Se (m > 1) Então 
 Para j de 1 a (m -1): 
 Se (Vet[j] > Vet[j+1]) Então 
 Troca(Vet[j], Vet[j+1]); 
 Fp; 
 Bubblesort(m -1); 
Fim; 
Chamada externa: Bubblesort(n); 
 
Neste caso, cada problema de tamanho n foi subdividido em dois 
problemas: um de tamanho 1 e outro de tamanho n-1. Para este algoritmo temos 
a complexidade O(n2), ilustrando o fato de que o critério de balanceamento é 
algo positivo na recursão. 
 22 
Quando um procedimento recursivo divide um problema grande em mais 
de um subproblema menor, a técnica costuma ser denominada Divisão e 
Conquista. 
 
1.3.2 Árvore de recursão 
 
A análise da complexidade de algoritmos recursivos fica em geral 
facilitada quando se constrói a árvore de recursão das chamadas. No caso do 
algoritmo Fatorial, a árvore de recursão tem o seguinte aspecto: 
 n 
 n-1 
 
 ... 
 1 
 
Como, em cada etapa da árvore é executada apenas uma instrução, a 
complexidade do algoritmo é equivalente ao número de nós da árvore 
(chamadas recursivas) que é O(n). 
Já no caso de Fibonacci, a árvore tem o seguinte aspecto: 
 
 n 
 
 n-1 n-2 
 
 n-2 n-3 n-3 n -4 
 ..................................................................... 
 0 1 ......................................... 0 1 
 
Como, em cada etapa da árvore é executada apenas uma instrução, a 
complexidade do algoritmo é igual ao número de nós da árvore que é O(2n), o 
que já torna este algoritmo inviável para valores de n bastante baixos (algo em 
torno de n = 30), qualquer que seja o computador utilizado! Para este algoritmo 
existe uma solução não recursiva trivial eficiente cuja complexidade é O(n). 
Basicamente o que está errado nessa solução é que o mesmo subproblema pode 
estar sendo resolvido milhares de vezes, à medida que se desce na árvore. 
 
A recorrência associada à série de Fibonacci é a seguinte: 
 
T(0) = 0 
T(1) = 1 
 23 
T(n) = T(n-1) + T(n-2) 
 
Podemos também criar uma recorrência que indica o número de 
chamadas recursivas da versão recursiva do algoritmo para Fibonacci: 
 
T(0) = 1 
T(1) = 1 
T(n) = 1 + T(n-1) + T(n-2) = 2*Fib(n+1) - 1. 
 
A solução dessa recorrência mostra que a complexidade do algoritmo é 
exponencial. 
 
 
1.3.3 Memoization 
 
Para problemas como o anterior, cuja recorrência leve a uma 
complexidade exponencial, pode-se muitas vezes evitar essa complexidade 
através de uma técnica que tabele os resultados de chamadas intermediárias , 
de tal forma que a recursão para essas chamadas só ocorrerá uma vez. Nas 
demais, será utilizado um resultado encontrado em uma tabela apropriada. 
Consideremos o problema Moedas, cujo objetivo é o de determinar o 
número de possibilidades diferentes de gerar um troco no Brasil, utilizando 
apenas os 6 tipos de moedas de centavos existentes: 1 (R$ 0,01), 5 (R$0,05), 
10 (R$0,10), 25 (R$0,25), 50 (R$0,50) e 100 (R$ 1). 
Expressaremos todos os valores em centavos, daquí por diante. Por 
exemplo, para dar um troco de 11 temos 4 possibilidades diferentes: 
10 + 1 ; 2 x 5 + 1; 5 + 6 x 1; 11 x 1. 
Esse problema tem uma formulação recursiva, que pode ser estabelecida 
da seguinte maneira: 
 
Seja T(m,n) o número de possibilidades distintas de se gerar um troco 
de valor n, usando os m tipos iniciais de moedas. Inicialmente, supondo n > 100, 
podemos escrever: 
 
T(m,n) = T(1, n - 1) + T(2, n - 5) + T(3, n - 10) + ...T(6, n - 100). 
 
O que pode ser assim entendido: A primeira parcela corresponde a se 
tomar as T(1, n - 1) maneiras distintas dar um troco para (n - 1) usando apenas 
a moeda de 1 centavo (neste caso T(1, n - 1) = 1, evidentemente). A segunda, 
T(2, n - 5) corresponde a se considerar os trocos possíveis para (n - 5) 
 24 
centavos fixando-se sempre a primeira moeda como uma moeda de 5 e 
utilizando a solução para (n-5) com moedas de 1 e 5. De forma análoga para os 
demais. A parcela T(6, n - 100) corresponde aos tipos de troco que sempre tem 
uma moeda de 100, agregada às diversas possibilidades para trocos de 
(n - 100) centavos usando todos os tipos de moedas possíveis. Para 
completarmos a idéia recursiva, temos que estabelecer: 
 
T(m, 0) = 1 (pois só há uma maneira de dar troco 0). 
T(m, n) = 0, quando n < 0, pois não há troco negativo. 
 
A recursão, então, pode ser assim apresentada, considerando-se um 
vetor V[1..m], contendo os valores dos m (=6) tipos de moedas, em ordem 
crescente: 
V[1] ← 1; V[2] ← 5; V[3] ← 10; V[4] ← 25; V[5] ← 50; V[6] ← 100; 
T(m,n) ← 0, se n < 0; 
T(m,n) ← 1, se n = 0; 
T(m,n) ← Σ T(i, n - V[i]), n > 0, 1 ≤ i ≤ m. 
 
Não é preciso analisar muito para se perceber que essa formulação leva 
a um algoritmo exponencial. Entretanto, se criarmos uma matriz T, m x n, onde 
elemento da matriz tem o significado da recursão acima, podemos estabelecer 
o algoritmo abaixo, que tabela os resultados necessários na matriz, de forma 
que a recursão para cada par de valores só será chamada uma vez. O algoritmo 
é o seguinte: 
 
 25 
Moedas (q, p); (A 1.11) 
Início: 
 Se (p < 0) Então k ← 0; 
 Senão Se (p = 0) Então k ← 1; 
 Senão Se (T[q, p] = 0) Então 
 k ← 0; 
 Para i de 1 a q: 
 k ← k + Moedas(i, p - V[i]); 
 Fp; 
 T[q, p] ← k; 
 Senão k ← T[q, p]; 
 Retornar(k); 
Fim; 
 
A tabela abaixo mostra quais subproblemas teriam que ser tabelados 
para n = 15; 
 
 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
2 1 2 3 
3 2 
4 
5 
6 6 
 
A tabela mostra que os seguintes subproblemas seriam tabelados: 
Todos os subproblemas T[1, i] para i < 15; 
Os subproblemas T[2, 0], T[2, 5], T[2, 10] 
O subproblema T[3, 5]; 
 
Desta forma, o algoritmo não é mais exponencial e passa a ser O(n2). 
 26 
1.4 Exercícios Propostos 
Escrever algoritmos recursivos para os problemas descritos a seguir. 
 
1.1 - (ALGOC) 
 Quer-se fazer a geração de constantes numéricas usando apenas as 
seguintes operações: 
 ONE - gera o número 1 
 MONE - gera o número -1 
 DUP - duplica o valor 
 ADD - soma 1 ao valor 
(Maratona ACM - 1998 - América do Sul) 
 
1.2 - (Nós mais distantes em uma árvore binária) 
 Encontrar os dois nós mais distantes em uma árvore binária. (Se houver 
mais de um par listar todos os pares). 
 
1.3 - (Algoritmo de Euclides) 
 Encontrar o máximo divisor comum de dois números inteiros, usando a 
idéia do algoritmo de Euclides. 
 
1.4 - (Seleção 2 menores) 
 Selecionar os dois menores elementos de um conjunto de n números. 
 
1.5 - (Busca por Faixa em Árvores Binárias de Busca) 
 Mostrar todas as chaves de uma ABB, cujos valores situem-se dentro de 
uma faixa [c, f] dada. 
 
1.6 - (Desenho de árvore binária) 
 Desenhar uma árvore binária, tal que a raiz apareça no centro da página, 
a raiz da subárvore esquerda no centro da metade esquerda da página, etc; 
 
1.7 - (Caminho externo de AB) 
 Calcular o tamanho do caminho externo de uma árvore binária. 
 
1.8 - (Radix Sort) 
 Ordenar um conjunto de elementos, de forma análoga ao Quicksort, 
usando como critério de partição o valor do bit de dada posição. 
 
1.9 - (Cálculo de Potências) 
 Calcular pn , onde n é um número inteiro. 
 27 
 
1.10 - (Desenho de aproximação de segmento) 
Desenhar uma aproximação do segmento de linha que une dois pontos de 
coordenadas (x1, x2) e (y1, y2) usando subsegmentos apenas de coordenadas 
inteiras. 
 
1.11 - (Pesquisa binária) 
 Buscar um elemento em um vetor ordenado usando o critério de pesquisa 
binária. 
 
1.12 - (Problema de Josephus) 
 Quer-se selecionar um elemento dentre n, numerados de 1 a n, que estão 
numa lista circular. A seleção é feita recebendo-se um inteiro p e fazendo-se a 
contagem circular de 1 a p eliminando-se, sucessivamente, da lista o elemento 
que recebeu a contagem p. Sempre que se elimina um elemento, a próxima 
contagem começa no elemento seguinte da lista. O selecionado é o último a sair. 
 
1.13 - (Fractais) 
 Pesquisar algoritmos para desenhos de fractais. (Ver "Algorithms + 
Data Structures = Programs", de N. Wirth, Prentice_Hall, 1976. 
 
1.14 - (Torneio) 
 Fazer um algoritmo alternativo para Torneio, quando n é um quadrado 
perfeito. 
 28 
2. BACKTRACKING 
 
2.1 Conceitos básicos 
É um método organizado de se testar exaustivamente as possibilidades 
de configuração de objetos ou situações, em geral com o objetivo de escolher 
configurações com propriedades dadas. Um exemplo clássico é o algoritmo para 
se gerar todas as combinações p a p de n elementos. 
Este método é também usado para a implementação de jogos por 
computador, onde, em cada situação, este tem que escolher a melhor jogada 
dentre as normalmente inúmeras possíveis, sendo que essa escolha deve 
resultar do aprofundamento do exame das possíveis respostas do oponente, 
combinadas a novas jogadas etc. 
Diz-se que essa técnica é um método organizado de teste exaustivo, 
porque ela deve ser tal que descubra, o mais cedo possível, configurações 
inviáveis, o que pode levar ao abandono do exame de inúmeras situações 
inviáveis derivadas. Isso quer dizer que o método nem sempre examina 
exaustivamente as possibilidades, mas o abandono de certas possibilidades 
inviáveis só aumenta a eficiência do processo. 
Pode-se apresentar um algoritmo recursivo geral para esta idéia, que 
será denominado Config, expresso da seguinte forma: 
 
Config(); (A2.1) 
Início: 
 Para cada elemento envolvido, efetuar: 
Se o elemento pode entrar na configuração, Então 
 Colocar o elemento na configuração; 
 Se a configuração tem a propriedade desejada Então 
 Imprimir a configuração; 
 Senão 
 Config(); 
 Retirar o elemento da configuração; 
Fim; 
 
Algumas observações sobre este modelo: 
 
1) Evidentemente há uma chamada externa ao procedimento, normalmente 
precedida do esvaziamento da configuração. 
 
2) O teste para descobrir se o elemento participa da configuração pode variar 
bastante de natureza, dependendo da situação. Quanto mais cedo se descobrir 
 29 
elementos inviáveis na configuração, melhor, pois menor aprofundamento é 
necessário. 
 
3) Grande parte das variáveis envolvidas pode ser de escopo global. 
 
4) Muitas vezes pode ser necessário o uso de parâmetros na chamada 
recursiva. 
 
Inicialmente apresentamos um algoritmo para gerar permutações dos 
números 1 a n. O algoritmo usa um vetor P, inicialmente vazio, acrescentando, 
sucessivamente e de todas as maneiras, os números 1 a n em P, sem repetir. 
 
Perm; (A2.2) 
Início: 
 Para i de 1 a n 
 Se (i ∉ P) Então: 
 P ← P + i; 
 Se (|P| = n) Então 
Imprimir P; 
Senão 
Perm(); 
 P ← P - i; 
 Fp; 
 Fim; 
 
Externamente deve ser feito: 
P ← ∅; 
Perm; 
 
Uma forma mais diretamente implementável para o algoritmo acima 
utiliza uma variável externa para controlar o tamanho do vetor P (np) e um 
vetor booleano auxiliar para controlar testar se i ∉ P. Obtemos: 
 
Externamente deve ser feito: 
Para j de 1 a n: S[j] ← False; Fp; 
 np ← 0; 
Perm; 
 30 
Perm; (A2.2) 
Início: 
 Para i de 1 a n 
 Se (not S[i] ) Então: 
 np ← np + 1; 
P[np] ← i; 
S[I] ← True; 
 Se (np = n) Então 
Imprimir P; 
Senão 
Perm; 
 np ← np - 1; 
S[I] ← False; 
 Fp; 
 Fim; 
 
 
Note a semelhança entre o algoritmo de Permutação e o modelo inicial 
apresentado para a técnica de Backtracking. Na verdade, o problema de gerar 
permutações é efetivamente um dos modelos básicos desta técnica, inclusive 
em termos de complexidade. Vê-se claramente que a complexidade deste 
algoritmo é O(n.n!), que não pode, entretanto, ser melhorada, já que o 
problema é, em sí, exponencial. 
Como esta técnica lança mão basicamente da recursão, temos também 
aquí a árvore de recursão de cada algoritmo. No caso do algoritmo de 
Permutação, se supusermos n = 5, ela tem a seguinte estrutura: 
 Perm 
 
 1 2 3 4 5 
 ..................................................... 
 2 3 4 5 
 ................................................. 
 3 4 5 
 ............................... 
4 5 
 5 
O número de folhas da árvore é 5! e cada caminho da raiz até uma das 
folhas obtem uma permutação diferente. 
De uma maneira geral, a árvore de recursão de backtracking tende a ser 
uma árvore do mesmo tipo da árvore de recursão de Permutação, onde o 
 31 
número de possibilidades é exponencial. Isto esclarece a observação feita 
inicialmente de que é importante evitar possibilidades inviáveis, o mais cedo 
possível. Em termos da árvore de recursão, isso significa "podar" todo um ramo 
da árvore, sempre que se descobre uma inviabilidade em uma configuração 
parcial, o que leva a uma maior eficiência do algoritmo. No ítem relativo aos 
Jogos, algumas técnicas de "poda" serão explicadas. 
 
2.2 Problemas clássicos 
Neste tópico são apresentados os seguintes algoritmos clássicos com 
solução por backtracking: 
a) Geração de combinações 
b) Damas pacíficas 
c) Torneio 
d) Geração de subconjuntos 
e) Soma de subconjuntos 
f) Partição aproximada 
 
 32 
2.2.1 Geração de combinações 
As combinações t a t dos n elementosde um conjunto podem ser 
apresentadas em ordem lexicográfica. Uma forma de fazer isso é modificar a 
solução dada para a geração de permutações, colocando-se a restrição de que 
cada novo elemento só entra na configuração, se for maior que o último que 
entrou. Outra forma é utilizar um parâmetro que indica o valor mínimo dos 
elementos que podem entrar na configuração. Esse algoritmo é o seguinte: 
 
Comb(j); (A2.3) 
Início: 
 Para i de j a n: 
 nc ← nc + 1; P[nc] ← i; 
 Se (nc = t) Então 
Imprimir P; 
Senão 
Comb(i+1); 
 nc ← nc - 1; 
 Fp; 
 Fim; 
 
Externamente deve ser feito: 
 nc ← 0; Comb(1); 
 
A complexidade do algoritmo acima, para valores baixos de p, é 
polinomial. Este algoritmo também ilustra o mecanismo de "poda" mencionado 
anteriormente. Se desenharmos a nova árvore de recursão e a compararmos 
com a anterior, para o caso de n = 5, temos várias podas a cada nível da árvore. 
 
 33 
2.2.2 Damas pacíficas 
Este é um quebra-cabeças que utiliza os conceitos e o tabuleiro do jogo 
de xadrez. O objetivo é colocar 8 damas no tabuleiro, de forma que elas não se 
"ataquem", segundo as regras desse jogo. O exemplo abaixo ilustra uma das 92 
possíveis soluções (das quais apenas 12 são soluções não simétricas): 
 
1 ℜ 
2 ℜ 
3 ℜ 
4 ℜ 
5 ℜ 
6 ℜ 
7 ℜ 
8 ℜ 
 1 2 3 4 5 6 7 8 
 
 O seguinte algoritmo resolve esse problema: 
Damas_pacificas; (A2.4) 
Início: 
 Para c de 1 até 8: 
 Se (Permite(l+1, c)) Então 
 l ← l + 1; 
 TAB[l] ← c; 
 Se (l = 8) Então 
 Imprimir TAB; 
 Senão 
 Damas_pacificas; 
 TAB[l] ← 0; 
 l ← l -1 ; 
 Fp; 
 Fim; 
 
 Externamente: 
 Zerar TAB; 
 l ← 0; 
 Damas_pacificas(); 
 
Foi usada a função Permite(l, c) que verifica se é possível se colocar mais 
uma dama na posição (l, c), linha l, coluna c, sem atacar as demais (l -1). Notar 
que tanto o vetor quanto a variável l são globais. O algoritmo obtem todas as 
 34 
92 soluções possíveis, mas poderia ser modificado para exibir apenas a 
primeira solução encontrada (!). Embora não seja dada a complexidade do 
algoritmo, ele também ilustra a explicação anterior sobre “poda” na árvore de 
recursão. 
 
2.2.3 Torneio 
Podemos retornar ao problema de organização de torneios com n 
competidores, discutido no ítem 1.2.5. O seguinte algoritmo resolve o 
problema: 
 
Torneio: (A2.5) 
Início: 
 jog ← menor jogador não emparelhado na rodada; 
 rod ← (NE+1)/n 
 Para i de (jog+1) até n: 
Se (Pode_emparelhar(jog, i, rod)) Então 
 NE ← NE+2; 
R[jog, rod] ← i; R[i, rod] ← jog; 
Se (NE = n2) Então 
 Imprime R; 
Senão 
 Torneio; 
R[jog, rod] ← 0; R[i, rod] ← 0; 
NE ← NE - 2; 
 Fp; 
 Fim; 
 
 Externamente: 
 R[*,*] ← 0; 
 Para j de 1 até n: R[j,1] ← j; Fp; 
 NE ← n; Torneio(); 
 
Neste algoritmo R tem o mesmo significado que anteriormente, tanto 
que inicialmente faz-se com que a coluna 1 contenha os números 1 a n. 
Pode_emparelhar verifica se os parâmetros são diferentes e se já não foram 
emparelhados anteriormente (pode ser usada outra matriz para essa função). 
NE indica o número de emparelhamentos já realizados. 
A figura seguinte mostra um dos milhares de emparelhamentos obtido 
para n = 8: 
 
 35 
c r1 r2 r3 r4 r5 r6 r7 
1 2 3 4 5 6 8 7 
2 1 4 3 8 7 5 6 
3 4 1 2 6 5 7 8 
4 3 2 1 7 8 6 5 
5 6 7 8 1 3 2 4 
6 5 8 7 3 1 4 2 
7 8 5 6 4 2 3 1 
8 7 6 5 2 4 1 3 
 
O algoritmo gera todas as configurações possíveis mas pode ser 
modificado para gerar apenas uma delas, ou configurações com determinadas 
propriedades. 
 
2.2.4 Geração de subconjuntos 
Muitos problemas envolvem a geração de alguns subconjuntos de dado 
conjunto. Vejamos inicialmente um modelo geral para a geração de 
subconjuntos de dado conjunto, mesmo sabendo que tal algoritmo tem 
complexidade exponencial, pois um conjunto com n elementos tem 2n 
subconjuntos distintos. 
A idéia é se colocar os elementos do conjunto em uma lista C e se tomar, 
a cada passo um desses elementos, combinando com o mesmo todos os demais 
elementos à sua direita na lista. 
Isso fornece o algoritmo a seguir, que usa uma variável global ns e um 
vetor S que guarda o índice dos elementos do subconjunto: 
 
 36 
Gera_subconjuntos (pi): (A2.6) 
 Início: 
Para i de pi a n: 
 ns ← ns + 1; S[ ns] ← i; 
 Imprimir SubConj; 
 Se (i < n) Então 
Gera_subconjuntos (i + 1); 
 ns ← ns - 1; 
 Fp; 
 Fim; 
 
 Externamente: 
 ns ← 0; Gera_subconjuntos(1); 
 
Notar que no Backtracking acima simplificou-se, ligeiramente, o modelo 
geral, pois cada solução parcial é uma solução final e, além disso, também pode 
ser uma subsolução de uma outra. A sequência de subconjuntos gerada para o 
conjunto {a, b, c, d} seria: 
{a}, {a, b}, {a, b, c}, {a, b, c, d}, {a, b, d}, {a, c}, {a, c, d}, {a, d}, {b}, {b, c}, 
{b, c, d}, {b, d}, {c}, {c, d}, {d}. 
 
2.2.5 Soma de subconjuntos 
Um problema interessante e que tem muitas variantes com aplicações 
práticas é o de, dado um conjunto C com n números inteiros, determinar se 
existe e quais combinações desses elementos têm soma igual a um valor s dado. 
Este problema é um caso particular de outro, muito famoso, denominado 
problema da Partição, que consiste em, dado um conjunto, determinar formas 
de particioná-lo em dois outros, tais que a soma dos elementos de cada 
partição seja a mesma. Ou seja, Soma de Subconjuntos é uma particularização 
de Partição, quando s não é a metade da soma dos elementos desse conjunto. 
Uma das possíveis soluções para soma de Subconjuntos é obtida da 
seguinte forma: ordenam-se os números e agrupam-se os mesmos de forma 
organizada, procurando obter o alvo s dado. Se, num dado ponto, a soma fica 
maior que s, o último elemento é abandonado, bem como todos aqueles maiores 
que o mesmo. O seguinte algoritmo resolve o problema: 
 
 37 
Soma_subconjuntos(j): (A2.7) 
Início: 
i ← j; 
 Enquanto (i ≤ n) e ((soma + C[i]) ≤ s): 
 nr ← nr + 1; soma ← soma + C[i]; subConj[nr] ← i; 
 Se (soma = s) Então 
 Imprimir subConj; 
 Senão 
 Soma_subconjuntos(i+1); 
 subConj[nr] ← 0; soma ← soma - C[i]; nr ← nr - 1; 
 i ← i+1; 
 Fe; 
 Fim; 
 
 Externamente: 
 soma ← 0; nr ← 0; 
 Ordena C; 
 Soma_subconjuntos(1); 
 
O vetor subConj guarda os índices dos elementos que participam da soma 
desejada. Notar que foi utilizado um parâmetro na recursão. Notar, também a 
"poda" colocada no "loop" que pode fazer o algoritmo funcionar bem para 
valores pequenos de s. No caso não são gerados todos os subconjuntos, mas 
apenas aqueles que possam levar à solução do problema. Muitas possibilidades 
podem ser abandonadas o mais cedo possível. 
 
2.2.6 Partição aproximada 
 
O problema mencionado anteriormente, Partição, nem sempre tem 
solução. Uma variante do mesmo, denominada Partição Aproximada, faz o 
particionamento do conjunto de forma a minimizar a diferença da soma entre 
as duas partições. Isso pode ser o melhor a se fazer em determinadas 
situações. 
O algoritmo a ser mostrado constitui-se um interessante paradigma de 
Backtracking onde a solução passa a ser buscada cada vez mais em 
subconjuntos restritos. O algoritmo a seguir é baseado no anterior, mas não se 
geram todos os subconjuntos. Apenas se examinam subconjuntos que tenham 
chance de melhorar uma solução prévia, caracterizada por dois parâmetros: dif 
= menor diferença entre partições já encontrada e msmp = maior soma da 
melhor partição já encontrada. A primeira solução considerada é uma partição 
 38 
contendo um dos conjuntos nulos e o outro todos os elementos. Gradualmente 
vai-se obtendo soluções cada vez melhores e cada melhoria é armazenada, em 
substituição à melhor solução anteriormente. A melhor partição guardada é a 
solução e ela é exibida. O algoritmo é mostrado a seguir. 
 
Part_aproximada(pi): (A2.8) 
Início: 
i ← pi; 
 Enquanto (i ≤ n) e ((soma + C[i] ) < msmp): 
 nr ← nr + 1; soma ← soma + C[i]; Part[nr] ← i;Se (abs(tot – 2*soma) < dif) Então 
 Guarda; dif ← abs(tot – 2*soma); 
msmp ← max(soma, tot - soma); 
 Part_aproximada(i + 1); 
 Part[nr] ← 0; soma ← soma - C[i]; nr ← nr - 1; 
 i ← i+1; 
 Fe; 
 Fim; 
 
 Externamente: 
 soma ← 0; nr ← 0; tot ← ΣC[i]; dif ← tot; msmp ← tot; 
Ordena C; Part_aproximada(1); 
 Imprime solução guardada; 
 
Neste algoritmo é chamado o procedimento Guarda, que armazena a 
melhor solução encontrada até o momento e atualiza o valor de dif. Se houver 
interesse em apenas uma solução, um mecanismo que pode parar a recursão é, 
quando a diferença (dif) atingir 0. 
 
Como exemplo, se tomarmos o conjunto {3, 4, 5, 7}, teremos a seguinte 
sequência de subconjuntos examinados e guardados: 
 
 Guardados msmp dif 
{} 19 19 
{3} {3} 16 13 
{3, 4} {3, 4} 12 5 
{3, 5} {3, 5} 11 3 
{3, 7} {3, 7} 10 1 
 39 
2.3 Jogos 
Uma das aplicações típicas da técnica de Backtracking é a programação 
de jogos, cujo desenvolvimento permitiu a utilização do método em vários 
outros tipos de problema. Considere jogos tais como xadrez, damas, jogo-da-
velha, onde há 2 jogadores. Os jogadores fazem jogadas alternadas e o estado 
do jogo pode ser representado pela posição do tabuleiro. 
 
2.3.1 Árvore de jogo 
Suponha que há um número finito de configurações de tabuleiro e que o 
jogo tem uma regra de parada. A esse tipo de jogo pode-se associar uma 
árvore chamada "árvore do jogo". Cada nó representa uma posição do tabuleiro. 
A raiz é a situação inicial e cada nível da árvore contém as possíveis jogadas de 
um dos jogadores, de forma alternada. 
A árvore a seguir representa uma situação de decisão no jogo-da-velha, 
onde o computador tem que jogar. Suas jogadas são marcadas com "x", e as do 
oponente com "o": 
 
 
 o o 
 x o (1) O computador joga 
 x x 
 
 A (1) B (-1) C (0) 
 
 D (0) E(-1) F (0) G (1) 
 
 
 H (0) I (0) J (1) 
 
As possibilidades de continuação do jogo são as seguintes: 
A e J - o computador joga na linha 3 e ganha; 
B - o computador joga na linha do meio e o jogo continua 
C - o computador joga na linha 1 e o jogo continua 
D - o oponente joga na linha 3 e o jogo continua 
E - o oponente joga na linha 1 e ganha 
F - o oponente joga na linha 3 e o jogo continua 
G - o oponente joga na linha do meio e o jogo continua 
H - o computador joga na última linha e é empate 
I - o computador joga na linha do meio e é empate 
 
 40 
Uma técnica para analisar o jogo consiste em atribuir às folhas 1 quando 
o computador ganha, 0 quando há empate ou -1 quando o oponente ganha. Esses 
valores podem ser propagados árvore acima, através do critério denominado 
MiniMax, que é o seguinte: cada nó pai recebe o valor máximo dos filhos quando 
é uma posição de jogada do computador, e o valor mínimo quando é uma posição 
de jogada do oponente. 
Esses números refletem a melhor estratégia para cada competidor. 
Quando for a vez do computador e o nó tiver valor 1, então há uma estratégia 
vencedora, dada por um caminho de valor 1 em todos os nós . 
Para jogos mais complicados, como o xadrez, por exemplo, a valoração 
dos nós assume uma gama mais ampla, podendo ir de –999 a 999, por exemplo, 
como será visto adiante. 
O algoritmo para o jogo consiste, portanto, em se construir a árvore, 
usando a ténica MiniMax e depois escolher a jogada usando a mesma. 
O cálculo dos valores dos nós pode ser feito pelo algoritmo seguinte, que 
basicamente é um percurso em pós-ordem na árvore de jogo, onde F 
representa um nó da árvore e Modo tem valor Min, quando o nó é de jogada do 
oponente ou Max, quando é de jogada do computador: 
 
Avalia_no (F, Modo); (A2.9) 
Início: 
 Se (F é folha) Então 
 Retornar (Calcula_valor(F)); 
 Senão 
 Se (Modo = Max) Então Valor ← -∞; 
 Senão Valor ← ∞; 
 Para cada filho w de F: 
 Se (Modo = Max) Então 
 Valor ← Max (Valor, Avalia_no(w, Min)); 
 Senão 
 Valor ← Min (Valor, Avalia_no(w, Max)); 
 Retornar Valor 
Fim; 
 
A função Calcula_valor avalia o valor da posição final do jogo. A 
constante Infinito representa o maior valor inteiro que pode ser representado. 
 
 41 
2.3.2 Poda Heurística 
Alguns jogos, entretanto, têm um número de alternativas absurdamente 
grande, o que inviabiliza a construção e exame de toda a árvore. As folhas 
muitas vezes representarão apenas configurações parciais do jogo. 
No caso do xadrez a ordem de grandeza do número de folhas é 35100. O 
que se faz, então é a introdução de Heurísticas para avaliação de posições do 
tabuleiro, somente aprofundando a análise de situações mais críticas e 
aplicando o método MiniMax para a árvore "podada" obtida e considerando, 
agora, que a valoração poderá variar numa gama mais ampla do que a vista para 
o jogo da velha, já que não se pode mais aplicar o critério absoluto de posição 
perdida/ganha/empatada, uma vez que a avaliação não parte dos nós finais. 
A perícia de um jogo para xadrez reside, portanto, na qualidade das 
heurísticas utilizadas. A avaliação heurística de uma configuração do tabuleiro 
é empírica, levando em conta o balanço ponderado das peças presentes e o 
valor de elementos estratégicos e táticos. O sucesso desse tipo de programa 
evidencia que existem boas heurísticas para a situação. Entretanto fica 
também evidente que nenhum programa é imbatível por um ser humano, visto 
que o programa não joga de forma exata. 
Quando se usa poda heurística, a cada jogada é construída uma nova 
árvore, que só é usada para a decisão do próximo lance. 
 
2.3.3 Poda alfa_beta 
Uma das melhorias que podem ser introduzidas no método MiniMax é 
denominada poda Alfa_beta, que permite abandonar o exame de trechos da 
árvore. Seja a situação abaixo da árvore de jogo: 
 
Max x 
 
Min f1 (120) f2(≤ 32) f3 
 
 
 h1 (32) 
 
Suponha que se acabou de determinar o valor do nó f1, depois de 
percorrer a sub-árvore correspondente. Quando se começa a examinar a sub-
árvore do nó irmão f2 e se descobre que o valor do primeiro filho é 32, pode-se 
abandonar todo o exame de f2, atribuindo a esse nó o valor aproximado 32, já 
que o mesmo não vai influenciar no cálculo de x, pois f2 tem o valor limitante 
32. 
 42 
De forma análoga à descrita, o exame de muitos trechos da árvore pode 
ser abandonado, tornando sua avaliação mais rápida. Na realidade, a construção 
da árvore pode ser simultânea à avaliação, o que significa que pode não ser 
necessária a construção de toda a árvore do jogo. 
Dessa forma a poda Alfa-beta pode tornar o jogo mais eficiente. 
 43 
2.4 Exercícios Propostos 
Escrever algoritmos para os problemas descritos a seguir, usando 
backtracking: 
 
2.1 – (Soma de Subconjuntos) 
 Dado um conjunto com n números, onde há repetições, e um valor s, 
listar, ordenadamente, as somas de elementos do conjunto cujo valor seja s, 
sem repetir configurações de soma. 
 
2.2 - (Percurso do cavalo) 
 Quer-se fazer um cavalo percorrer todas as casas de um tabuleiro de 
xadrez de forma a não repetir nenhuma posição pela qual já passou. Dica: 
tentar uma heurística para dar preferência para casas com menos 
possibilidades de saídas. 
 
2.3 - (Soma de Quadrados) 
 Escrever um algoritmo para, dado um inteiro positivo n, listar todas as 
combinações de somas de quadrados de inteiros menores que n, iguais ao 
quadrado de n. Observar que pode repetir quadrado. Exemplo: para n = 3, 
temos: 32 = 12+12+12+12+12+12+12+12+12 = 12+12+12+12+12+12 = 12 + 22 + 22. 
 
2.4 - (Vasos) 
 Dados 3 vasos contendo água, com capacidades (c1, c2, c3), situação 
inicial (s1, s2, s3), quer-se determinar qual o número mínimo de operações de 
transferência, para se atingir o objetivo (o1, o2, o3) dado. Cada transferência 
ou enche o vaso de destino ou esvazia o de origem e a quantidade de água é 
mantida no processo. Observar que pode não haver solução. (MaratonaACM - 
2000 - América do Sul) 
 
2.5 – (Expressão) 
 Fazer um algoritmo para, dados n+1 números inteiros positivos, verificar 
se é possível escrever o primeiro como uma combinação linear dos n restantes 
(usando somas e subtrações, apenas). 
Ex: para {13, 9, 5, 11, 20} é possível, pois 13 = 9 – 5 – 11 + 20; já para {3, 200, 
150, 8, 15} não é possível. 
 
 44 
2.6 - (Quadrado Mágico) 
 Apresentar um quadrado mágico para dado n. Um quadrado mágico é um 
quadrado de lado n, divido em n2 células, preenchido com os números 1 a n2, tal 
que a soma das linhas = soma das colunas = soma das diagonais principais. 
 
2.7 - (Quadrados latinos ortogonais) 
 Apresentar dois quadrados latinos ortogonais de lado n. Um quadrado 
latino de lado n é uma matriz (n x n) tal que, cada linha e cada coluna, são 
preenchidas com uma permutação dos números 1 a n. Dois quadrados latinos A 
e B são ortogonais se, para todo i e j, A[i,j] ≠ B[i, j]. 
 
2.8 - (Chumbo Ou Ouro) 
 A empresa ACM descobriu que pode-se transformar Chumbo em Ouro, 
submetendo o primeiro a uma mistura dos elementos A, B, C, que estejam numa 
proporção de p, q e r nessa mistura. Dadas n misturas dos elementos químicos 
A, B, C, em proporções dadas, determinar se pode ser criada uma nova mistura 
na proporção desejada. (Maratona ACM - 1998 - Final) 
 
2.9 - (Palavras cruzadas) 
 Dados dois números l e c, que indicam a quantidade de linhas e de colunas 
em um diagrama de palavras cruzadas e l "strings" de tamanho c cada um, 
sendo que cada "string" contém palavras e '*' . Cada "string" se encaixe 
exatamente em uma das linhas do retângulo, e o * corresponde a uma posição 
não usada do diagrama. Quer-se saber se esses "strings" podem ser 
encaixados no diagrama tal que se formem palavras válidas, contidas em um 
vetor. 
 
2.10 - (Retângulo de dominós) 
 O conjunto das peças do jogo de dominó é formado por 28 retângulos 
cada um com dois quadrados contendo números 0 a 6. Cada peça é uma 
combinação diferente das 7 possibilidades. Podemos dispor todas as peças de 
um jogo de dominó em um retângulo de 7x8, podendo algumas peças serem 
colocadas horizontalmente e outras verticalmente. Verificar se uma 
configuração dada em um retângulo 7 x 8 corresponde às 28 peças do jogo. 
(Maratona ACM - 1991 - Final). 
 
2.11 - (Jogo da velha) 
Implementar um programa para o Jogo da velha. 
 
 
 45 
2.12 - (Jogo da Último palito) 
Implementar um programa para o Jogo do Último palito, onde dois 
jogadores iniciam com uma pilha de 24 palitos e, alternadamente, cada um pode 
retirar 1 a 3 palitos, vencendo o último a retirar palitos. 
 
2.13 - (Resta 1) 
 Implementar um programa para o jogo do Resta 1. 
 
2.14 - (Quebra-cabeças) 
 Descrever um algoritmo para solucionar o quebra-cabeças que consiste 
de um tabuleiro de 4 x 4, com 15 peças contendo os números 1 a 15 e um uma 
posição nula. É dada uma configuração inicial e quer-se a chegar à configuração 
padrão onde os números estão ordenados no tabuleiro. 
 
2.15 - (Árvores de Jogo) 
 Desenhar árvores de Jogo para os seguintes jogos: 
a) Jogo de Palitos, semelhante a 2.12, só que iniciando com 5 palitos. 
b) Jogo da Multiplicação, onde é sorteado um número menor que 100. Começa-
se com o número 1 e, alternadamente, cada adversário multiplica esse número 
por outro que pode variar entre 2 e 5. Aquele que atingir ou superar o número 
escolhido é o vencedor. 
 
2.16 – (Permutações com repetições) 
 Dados n números, onde há repetições, listar as Permutações, sem 
repetir nenhuma configuração. 
 
2.17 - (Arranjos e Combinações com repetições) 
 Dados n números, onde há repetições, listar arranjos (A(n,p)) e 
combinações (Comb(n,p)), sem repetir nenhuma configuração. 
 
2.18 - (Contração de Inteiros) 
 Dada uma sequência de n números inteiros (n < 101), quer-se determinar 
a ordem de contrações a serem feitas, tal que o resultado final seja um 
número p dado. Cada contração toma dois elementos vizinhos da sequência, 
substitui o primeiro pela diferença entre ele e seguinte, e elimina o elemento 
seguinte. (Maratona ACM - 1998 - América do Sul) 
 
 
 
2.19 – (Permutações de Knuth) 
 46 
 Fazer um algoritmo para gerar permutações, obtendo as permutações 
para n elementos a partir daquelas para (n –1), colocando o n-ésimo elemento 
em todas as n posições possíveis de cada permutação gerada com (n -1) 
elementos. 
Ex. No caso de n = 3 a ordem de geração seria: 321, 231, 213, 312, 132, 123. 
 
2.20 – (Problemas em Grafos) 
 Fazer algoritmos para a solução dos seguintes problemas em grafos: 
a) Determinar um ciclo Hamiltoniano. 
b) Determinar a maior clique. 
c) Determinar o maior conjunto independente. 
d) Determinar uma coloração mínima de vértices. 
e) Determinar uma coloração mínima de arestas. 
 
 
 
 47 
3. PROGRAMAÇÃO DINÂMICA 
 
3.1 Conceitos básicos 
 
A aplicação da Divisão e Conquista na solução de problemas pode algumas 
vezes levar a algoritmos ineficientes, tal como os exemplos mostrados para o 
cálculo da sequência de Fibonacci e para o problema Moedas. Basicamente, o 
que pode dar errado é o mesmo subproblema estar sendo resolvido mais de 
uma vez, devido à formulação recursiva. Em alguns casos, milhares de vezes. 
A técnica de Programação Dinâmica pode ser compreendida como uma 
forma de evitar esse inconveniente, colocando resultados intermediários em 
"tabelas", para fugir à repetição da solução de um mesmo subproblema. 
Ela é usada tipicamente para problemas de otimização, onde se procura 
o mínimo ou o máximo de alguma propriedade para certas configurações. 
A solução de um problema usando esta técnica pode ser compreendida 
como tendo uma formulação recursiva, complementada pelo enfoque "bottom-
up" para a composição dos subproblemas em problemas maiores. No caso da 
sequência de Fibonacci, o problema é resolvido com um "loop" ascendente, 
guardando cada elemento da sequência calculado em uma posição de um vetor. 
Para ilustrar a técnica, consideraremos, inicialmente, o problema do 
cálculo de probabilidades de vitória em "matches" onde dois competidores, C1 e 
C2 disputam uma série de jogos em regime de "melhor de n". Isso que quer 
dizer que aquele que atingir primeiro n pontos vence o "match". Adotaremos as 
regras adicionais de que cada vitória vale 2 pontos, cada empate 1 e, se no final 
houver empate em n a n, tem que ser adotado um critério adicional tal como o 
sorteio do vencedor. Esta é a fórmula usada em muitos campeonatos de 
futebol, onde se usa n = 3 ou 5. Nos "matches" finais dos campeonatos 
mundiais de xadrez a fórmula é semelhante, só que cada vitória vale 1 ponto e 
os empates são descartados. 
 
Supondo que C1 e C2 tenham igual força, o problema será colocado como: 
 
"qual a chance do competidor C1 se sagrar campeão, dado que 
faltam i pontos para C1 alcançar a meta e j pontos para C2?" 
 
O problema pode ser formulado recursivamente, usando-se a seguinte 
recorrência: 
 
 48 
P(i, j) = 1, se (i = 0 e j > 0) (a) 
= 0, se (i > 0 e j = 0) (b) 
= (P(i-1, j-1) + P(i-2, j) + P(i, j-2))/3, se (i > 1 e j > 1) (c) 
= 1/2, se (i = 1 e j = 1) (d) 
= 2/3 + P(1,j-2), se (i = 1 e j > 1) (e) 
= P(i, j-2)/3, se (j = 1 e i > 1) (f) 
 
 As diversas condições dessa recorrência refletem as seguintes 
situações: 
 
 (a) - o competidor 1 já venceu. 
(b) - o competidor 2 já venceu. 
 (c) - a idéia central da recorrência: se houver empate, cai-se na situação 
de chances de P(i-1, j-1); se vitória, de P(i-2, j); se derrota, P(i, j-2). A chance 
de cada possibilidade é 1/3. 
 (d) - situação particular, P(1,1), obviamente = 1/2 
 (e) - situação particular, com i = 1, onde a vitória e empate bastam para 
o competidor 1. 
(f) - situação particular onde apenas a vitória serve para o competidor 1. 
 
Usando-se essa recorrência, constrói-se a tabela a seguir (n = 5), com 
complexidade O(2n). 
 
 5 0 1/18 4/27 14/54 31/81 1/2 
 4 0 1/9 2/9 10/27 1/2 50/81 
i 3 0 1/6 1/3 1/2 17/27 20/27 
 2 0 1/3 1/2 2/3 7/9 23/27 
 1 0 1/2 2/3 5/6 8/9 17/180 - 1 1 1 1 1 
 0 1 2 3 4 5 
 j 
 Podemos simplificar a recorrência anterior, introduzindo algumas 
condições artificiais, equivalentes a uma nova coluna e uma nova linha na tabela, 
correspondendo aos índices i = -1 e j = -1, além do valor P(0,0) = 1/2. Obtemos 
a seguinte recorrência, que engloba a anterior: 
 
 49 
P(i, j) = 1, se i ∈ {-1,0} e j > 0 (a) 
= 0, se i > 0 e j ∈ {-1,0} (b) 
= 1/2, se i = 0, j = 0 (c) 
= (P(i-1, j-1) + P(i-2, j) + P(i, j-2))/3, se i ≥ 1 e j ≥ 1 (d) 
 
Se os valores P(i,j) forem calculados em ordem não decrescente da soma 
(i+j), então pode ser feita uma implementação não recursiva do cálculo, 
segundo o esquema delineado abaixo: 
 
 
 i+j = 2 
 
 i i+j = 3 
 j 
 
Usando essa idéia, chega-se ao seguinte algoritmo, cuja complexidade é 
O(n2): 
Chance_em_Match(k) (A3.1) 
Início: 
 P(0,0) ← 1/2; 
 Para r de 1 até k: 
 P[-1,r] ← 1; P[0,r] ← 1; 
 P[r, -1] ← 0; P[r,0] ← 0; 
 Para s de 1 até (r-1): 
 P[s, r-s] ← (P[s, r-s-2] + P[s-1,r-s-1] + P[s-2, r-s])/3; 
 Fp; 
 Fp; 
 Fim; 
 
Externamente deve ser feita a chamada Chance_em_Match(i+j), para os 
valores i e j desejados. 
Note-se que o algoritmo preenche um triângulo de valores, podendo 
gerar mais valores que os necessários para determinada situação. Entretanto, 
basta fazer uma pequena alteração no algoritmo para que seja calculado apenas 
o "retângulo" desejado. Essa alteração fica como exercício. 
Esse algoritmo ilustra bem todos os pontos ditos acima sobre a técnica 
de programação dinâmica, pois a formulação recursiva permitiu chegar a um 
algoritmo não recursivo eficiente. 
 
 50 
Podemos, também, retomar o problema Moedas, do Capítulo 1, que 
consiste em se determinar o número de possibilidades de dar troco em moedas 
para um valor n, expresso em centavos. Para esse problema, formulamos a 
seguinte recursão: 
 
T(m, n) = número de possibilidades distintas de dar um troco de n 
centavos, usando os m tipos iniciais de moedas (no exemplo, foram usadas 
moedas de 1, 5, 10, 25, 50 e 100 centavos). E: 
T(m, n) = 0, se n < 0; 
T(m, n) = 1, se n = 0; 
T(m, n) = Σ T(i, m - MO[i]), se n > 0, 1 ≤ i ≤ m 
 
Se observarmos a ordem do cálculo dos valores T(m, n) na recursão, 
podemos verificar que uma matriz T, m x n, pode ser preenchida por linha, de 
forma crescente tal que sempre que se necessite calcular T(m, n) todos os 
valores necessários já estejam calculados e tabelados. Isto, então sugere um 
algoritmo simples, de complexidade O(m2.n), que preenche a matriz desejada. 
 
O algoritmo é o seguinte: 
Moedas(m, n); (A 3.2) 
Início: 
 Para i de 1 até m: T[i, 0] ← 1; Fp; 
Para i de 1 até m: 
Para j de 1 até n: 
 tot ← 0; 
Para k de 1 até i: 
 Se ((j - MO[k]) ≥ 0) Então tot ← tot + T[k, j - MO[k]]; 
 Fp; 
 T[i, j] ← tot; 
 Fp; 
Fp; 
Fim; 
 
 51 
Esse algoritmo preenche a tabela abaixo, por coluna, da esquerda para a 
direita: 
 
m\n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
2 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 
3 1 1 1 1 1 2 2 2 2 2 4 4 4 4 4 6 6 6 6 6 9 
4 1 1 1 1 1 2 2 2 2 2 4 4 4 4 4 6 6 6 6 6 9 
5 1 1 1 1 1 2 2 2 2 2 4 4 4 4 4 6 6 6 6 6 9 
6 1 1 1 1 1 2 2 2 2 2 4 4 4 4 4 6 6 6 6 6 9 
 
 
3.2 Problemas clássicos 
 
Neste tópico são apresentados os seguintes algoritmos clássicos com 
solução por Programação Dinâmica: 
a) Mochila (0/1) 
b) Produto de Matrizes 
c) Triangularização de Polígonos 
d)Árvore de Busca Ótima 
e) Distância de Edição 
 
3.2.1 Mochila (Versão 0/1 - básica) 
Este problema se apresenta em várias versões, a partir de uma idéia 
básica (não muito elogiável): um ladrão tem à sua disposição um conjuntos de t 
ítens que quer roubar. Sua mochila pode carregar um peso M e cada ítem i tem 
peso pi. A questão é saber se existe uma combinação de ítens que encham 
exatamente o peso da mochila e, neste caso, quais são esses ítens. Seja: 
K(q, n) = (x, y) = Solução quando se consideram apenas os q ítens iniciais 
 e um volume n; 
x = V ou F, indicando se existe a combinação desejada 
y =V ou F, indicando se o elemento m pertence ou não solução. 
Este problema pode ser formulado recursivamente da seguinte forma: 
 
K(q, n) = (V, F), se n = 0 
K(q, n) = (V, F), se K(q -1, n) = (V, ?), 0 ≤ n ≤ M, 1 ≤ q ≤ t; 
K(q, n) = (V, V), se K(q -1, n - pq) = (V, ?) , 0 ≤ n ≤ M, 1 ≤ q ≤ t; 
K(q, n) = (F, F), nos demais casos 
 
Um possível algoritmo para implementar essa solução seria: 
 52 
 
Mochila(q, n): (A3.3) 
Início: 
Se (n = 0) Então 
Retornar (V, F) 
Senão Se (q = 0) Então 
 Retornar (F, F) 
Senão: 
(x, y) ← Mochila (q - 1, n); 
Se (x) Então 
Retornar (V, F) 
Senão: 
(x, y) ← Mochila (q -1, n - pq ); 
Se (x) Então 
Retornar (V, V) 
Senão 
Retornar (F, F); 
 Fim; 
 
Externamente: 
 Mochila(t, M); 
 
 
Evidentemente, tal recursão leva a um algoritmo ineficiente. Mas aquí, 
também, uma solução pode ser obtida por Programação Dinâmica, através da 
composição bottom-up dos subproblemas, conforme o exemplo a seguir: 
 
Seja M = 20 e os seguintes ítens: 
 
 
 vol= 7 vol=3 vol=5 vol=9 vol=15 
 
 
 
Podemos construir uma solução considerando, sucessivamente, as 
combinações possíveis, quando se adiciona, passo a passo, um dos ítens como um 
possível ítem a ser usado: 
B A C D E 
 53 
 
 
Ítem/ 
vol 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
0 VF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF 
A (7) VF FF FF FF FF FF FF V
V 
FF FF FF FF FF FF FF FF FF FF FF FF FF 
B (3) VF FF FF V
V 
FF FF FF VF FF FF V
V 
FF FF FF FF FF FF FF FF FF FF 
C (5) VF FF FF VF FF V
V 
FF VF V
V 
FF VF FF V
V 
FF FF V
V 
FF FF FF FF FF 
D (9) VF FF FF VF FF VF FF VF VF V
V 
VF FF VF FF V
V 
VF V
V 
V
V 
FF V
V 
FF 
E (15) VF FF FF VF FF VF FF VF VF VF VF FF VF FF VF VF VF VF V
V 
VF V
V 
 
Nesta tabela, foram colocadas, artificialmente, a linha para o ítem 
0 e a coluna para o volume 0. Isto facilita a escrita do algoritmo de 
Programação Dinâmica a seguir. Note que a célula K[E, 20] = (V, V), 
indica que o problema tem solucão e que o ítem E faz parte da mesma. O 
peso dos itens é guardado no vetor P. 
 
Algoritmo: 
Mochila: (A3.4) 
Início: 
K[0, 0].x ← V; K[0, 0].y ← F 
Para j de 1 a M: 
 K[0, j].x ← F; K[0, j].y ← F; 
Fp; 
Para i de 1 a t: 
Para j de 0 a M: 
Se (K[i - 1, j].x) Então 
K[i, j].x ← V; K[i, j].y ← F; 
 Senão 
Se (j ≥ V[i]) e (K[i - 1, j - P[i]].x) Então 
 K[i, j].x ← V; K[i, j].y ← V; 
 Senão 
 K[i, j].x ← F; K[i, j].y ← F; 
 Fp; 
 Fp; 
 Fim; 
 
 54 
Pode-se verificar que o preenchimento dessa tabelas obedece 
exatamente à idéia da recursão mostrada anteriormente. E esta nova 
solução para o problema tem complexidade O(t.M). 
Uma variante imediata do problema é encontrar a solução mais 
próxima do objetivo procurado, que também é resolvida com a mesma 
tabela e verificando, na última linha, o valor mais próximo do procurado. 
 
Para apresentar os itens que fazem parte da solução, pode-se usar o 
seguinte algoritmo: 
 
Solução: 
Início: 
 j ← M; i ← t; 
 Enquanto (j ≠ 0): 
 Enquanto (K[i, j].y ≠ ‘V’): 
i ← i - 1; 
Fe; 
 Escrever V[i]; j ← j – V[i]; i ← i - 1; 
 Fe; 
Fim; 
 
A apresentação de todas as soluções possíveis requer um algoritmo de 
Backtracking, cuja elaboração fica como exercício. 
 
3.2.1.1 Mochila (Matriz com apenas um valor) 
 
Uma primeira mudança que pode ser feito no algoritmo anterior é 
guardar apenas um valor em cada célula da matriz. Esse valor pode ser o índice 
do item. No exemplo mostrado, a matriz poderia ser a seguinte, onde as células 
não preenchidas podem ter o valor -1: 
 
Ítem/ 
vol 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
0 0 
A (7) 0 1B (3) 0 2 1 2 
C (5) 0 2 3 1 3 2 3 3 
D (9) 0 2 3 1 3 4 2 3 4 3 4 4 4 
E (15) 0 2 3 1 3 4 2 3 4 3 4 4 5 4 5 
 
3.2.1.2 Mochila em vetor 
 
 55 
Na verdade basta usar um vetor, ao invés de uma matriz, para a busca 
da solução para a Mochila. Esse vetor equivale à última linha da matriz. Seu 
preenchimento tem uma sutileza, que é a de percorrer o vetor da direita para 
a esquerda. Inicialmente o vetor é preenchido com -1. O algoritmo é o seguinte: 
 
MochilaVetor; 
Início 
K[0] ← 0; 
Para j de 1 a M: K[j] ← -1; Fp; 
Para i de 1 a t: 
 Para j de M-P[i] descendo a 0: 
 Se (K[j+P[i]] = -1) e (K[j] ≥ 0) Então K[j+P[i]] ← i; 
 Fp; 
Fp; 
 Fim; 
 
Outra alternativa, ainda, é, na versão que usa matriz, fazer com que 
cada linha da matriz indique a quantidade de itens na solução. Assim, a primeira 
linha apresentaria as soluções com 1 elemento; a segunda, com dois elementos e 
assim sucessivamente. 
 
3.2.1.3 Mochila com peso e valor 
 
Outra versão ainda do problema Mochila consiste em atribuir a cada 
item não apenas um peso, mas também um valor. Neste caso, o objetivo passa a 
ser o preenchimento da mochila para obter o valor máximo. O algoritmo pode 
ser o seguinte, onde, em cada posição do vetor guardamos dois dados: o índice 
do item (me) e o valor máximo obtido (vm). Usa-se a mesma inicialização do 
algoritmo anterior e temos a mesma sutileza a considerar. 
 
MochilaPesoValor; 
Início: 
K[0].me ← 0; K[0].vm ← 0; 
Para j de 1 a M: K[j].me ← -1; K[j].vm ← 0; Fp; 
Para i de 1 a t: 
 Para j de M-P[i] descendo a 0: 
 Se (K[j].me ≥ 0) e (K[j+P[i]].vm < (K[j].vm+V[i]) Então 
 K[j+P[i]].me ← i; K[j+P[i]].vm ← K[j].vm+V[i]; 
 Fp; 
Fp; 
 56 
 Fim; 
 
 Voltando ao exemplo inicial, consideremos a seguinte conjunto de pares 
de valores, onde o primeiro valor do par é o peso do item e o segundo, seu 
valor: S = {(7, 10) , (3, 6), (5, 11), (9, 12), (15, 15)}. Obteríamos o seguinte 
vetor: 
 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
0 
0 
-1 
0 
-1 
0 
2 
6 
-1 
0 
3 
11 
-1 
0 
1 
10 
3 
17 
4 
12 
2 
16 
-1 
0 
3 
21 
-1 
0 
4 
23 
3 
27 
4 
22 
4 
29 
5 
21 
4 
28 
5 
26 
 
3.2.1.4 Mochila (Versão múltiplos ítens) 
 
A última variante para o problema de itens com peso e valor é imaginar 
que o número de ítens de cada tipo é ilimitado. Neste caso, a variante torna-se 
um problema de maximização: maximizar o valor total de ítens de t tipos 
colocados numa mochila, cada tipo com peso pi e valor vi, associados, de forma 
que não seja ultrapassado o peso máximo M. A quantidade disponível de ítens 
de cada tipo é suposta ilimitada. 
 
Uma solução recursiva para o problema seria: 
 
Mochila(k): (A3.5) 
Início: 
Se (k = 0) Então Retornar 0 
Senão 
MaxVal ← 0; Maxi ← 0 
Para i de 1 a n: 
 MaxAux ← vi + Mochila(k - pi) 
 Se (MaxVal < MaxAux) Então 
 MaxVal ← MaxAux; 
 Maxi ← i; 
 Marca Maxi; 
 Mochila(k - pMaxi); 
 Fim; 
 Externamente: 
 Mochila(M); 
 
Esta solução tem complexidade O(2n). Entretanto, quando todas as 
variáveis envolvidas são inteiros positivos, há uma solução eficiente por 
programação dinâmica, que consiste em se determinar qual o ítem final que 
 57 
otimiza o problema, para cada peso ≤ M, iniciando com um tipo de ítem e 
considerando, gradativamente, cada novo tipo. No exemplo abaixo, 
consideramos 3 tipos: 
 
 peso = 5 peso = 8 peso = 11 
 
 valor = 6 valor = 7 valor = 13 
 
Considerando apenas o tipo A, a melhor solução para todo peso acima de 
5 usar somente esse tipo: 
 
Peso 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2
0 
21 2
2 
2
3 
2
4 
TMel A A A A A A A A A A A A A A A A A A A A 
VMax 6 6 6 6 6 12 12 12 12 12 18 18 18 18 18 2
4 
2
4 
2
4 
2
4 
2
4 
 
Considerando os tipos A e B, a melhor solução para os diversos pesos é: 
 
Peso 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 
TMel A A A B B A A A A A A A A A A A A A A A 
VMax 6 6 6 7 7 12 12 12 13 13 18 18 18 19 19 24 24 24 25 25 
 
Considerando finalmente A, B e C, a melhor solução muda para: 
 
Peso 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 
TMel A A A B B A C C A A A A A A B A A C C A 
VMax 6 6 6 7 7 12 13 13 13 13 18 19 19 19 20 24 25 26 26 26 
 
Para o preenchimento da tabela, considerando os tipos de ítens 1 a k, o 
que se faz é, para cada peso, verificar qual dos k ítens gera o máximo VMax, 
através da computação (vi + Vmax[Peso- pi], esta última parcela obtida 
anteriormente, para (k -1) ítens. 
Usam-se, portanto, 2 vetores: TMel que indica o último melhor tipo para 
um peso e VMax, que indica o valor máximo total, considerando a escolha de 
TMel. 
Pode-se verificar que o preenchimento dessas tabelas obedece 
exatamente à idéia da recursão mostrada anteriormente. E esta nova solução 
para o problema tem complexidade O(nM). 
 
B A C 
 58 
O seguinte algoritmo implementa esse processo : 
 
Mochila(t, M); (A3.6) 
Início: 
 Para j de 0 até M: 
 VMax[j] ← 0; 
 Para i de 1 até n: 
 Se ((j - pi) ≥ 0) e (VMax[j] < (vi +Vmax[j- pi] ) Então 
 TMel[j] ← i; 
 VMax[j] ← vi +Vmax[j- pi]; 
 Fp; 
 Fp; 
Fim; 
 
 59 
3.2.3 Produto de Matrizes 
Este é um problema que surge em processamentos matriciais pesados, 
tais como na área de avaliação de reservas petrolíferas, onde são necessários 
até mesmo processadores matriciais, tal a intensidade de cálculos. O problema 
está ligado à minimização do número de operações a serem realizadas, quando 
se fazem multiplicações sequenciais de várias matrizes. Suponhamos, por 
exemplo, que tenhamos que multiplicar as seguintes matrizes: 
 
M1 (5 x 20), M2 (20 x 50), M3 (50 x 5), M4 (5 x 100), na ordem dada. 
 
Como a operação é associativa, podemos efetuar o cálculo de várias 
formas, dentre as quais: 
a) (M1 x M2) x (M3 x M4 ), com um total de operações de: 
 5 x 20 x 50 (M1 x M2) 
 + 50 x 5 x 100 (M3 x M4) 
 + 5 x 50 x 100 (produto dos produtos) 
 = 55.000 
b) (M1 x ((M2 x M3) x M4)), com um total de operações de: 
 = 20 x 50 x 5 (M2 x M3) 
 + 20 x 5 x 100 (produto anterior x M4) 
 + 5 x 20 x 100 (M1 x produto anteior) 
 = 25.000 
 
Esses números ilustram que pode haver uma variação significativa no 
número de operações, dependendo da ordem da multiplicação usada. O 
problema é encontrar a ordem de multiplicação que leve ao número mínimo de 
operações. 
Há, evidentemente, a solução ineficiente de backtracking que tenta 
todas as ordens possíveis e escolhe aquela com menos operações. 
 
Para chegarmos à formulação mais eficiente para a multiplicação das 
matrizes M1, M2, .... Mn, onde cada matriz Mi tem ri-1 linhas e ri colunas, 
devemos perceber que as dimensões das matrizes podem ser representadas 
pela sequência: r0 r1 ...ri ...rn, onde o número de colunas de uma matriz é o 
número de linhas da seguinte. 
Dada uma sequência de matrizes, Mi....Mj, se conhecermos a maneira 
otimizada (quantidade de operações minimizada) de nultiplicar cada partição 
dessa sequência, podemos descobri a maneira otimizada para toda a sequência, 
co mostrado a seguir. 
 60 
Seja mi,j o total de operações mínimo para o produto Mi....Mj. 
Considerando k o índice que identifica a última operação que minimizou mi,j, 
devemos ter: 
 
mi,j = mi,k + mk+1.j + ri-1 x rk x rj 
mi,i = 0 
 
E, portanto, mi,j deve ser tal que 
mi,j = Min (mi,k + mk+1.j + ri-1 x rk x rj ), para i ≤ k < j 
mi,i = 0, para i = j. 
 
Para se conseguir uma solução eficiente para o problema, basta que os 
subproblemas sejam calculados e tabelados em ordem não decrescente de 
tamanhos de subsequências. 
 
 
O seguinte algoritmo faz isso. Ele utiliza duas matrizes m e mk. Na 
matriz m guarda-se o valor minimizado das operações de i a j e na matriz mk 
guarda-se o valor de k relativo à última operação. 
 
Produto_Matrizes(); (A3.7) 
Início: 
 Para k de 1 a n: m[k,k] ← 0; Fp; 
 Para d de 1 a (n - 1): 
Para i de 1 a (n - d): 
 j ← i + d; 
 m[i, j]