Divisão e Conquista na Programação

Prévia do material em texto

Introdução as Técnicas Avançadas de Programação 
 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 81 
 
 
 
Sumário: 
6.1- Conceitos 
6.2- Exemplos 
6.3- Eliminação da Recursão 
6.4- Recomendações Bibliogáficas 
6.5- Exercícios 
6.6- Projectos de Programação 
 
 
 
 
 
 
 
6 
 
 
 
 
“A nossa experiência mostra que a 
legibilidade é o único e o melhor 
critério para a qualidade de um 
programa: se um programa é fácil de 
ler ele é provávelmente um bom 
programa; se ele é difícil de ler, 
provavelmente ele não é bom.” 
 
 - Kernighan e Plauger - 
 
 
 
 
 
 
 
 
Divisão e 
Conquista 
Introdução as Técnicas Avançadas de Programação 
 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 82 
 
6.1- Conceitos 
 
A estratégia de Divisão e Conquista ou Recursão em Árvore foi inventado 
por Napoleão Bonaparte na batalha de Austerliz en 1805. Nessa batalha, o 
exercícito francês estava em inferioridade numérica e, necessitava de derrotar 
os exércitos russos e autríacos que estavam concentarados no campo de 
batalha como se fossem um único exército. Napoleão mandou o seu exércíto 
atacar no centro, dividindo desse modo o exército inimigo e combatê-lo de 
forma separada. 
 
Este paradigma de programação caracteriza-se pela execução de duas ou 
mais chamadas recursivas para reduzir o problema em problemas mais 
simples. Essa redução é normalmente feita pela divisão da instância de dados 
ao meio e termina quando chegarmos uma instância unitária de fácil resolução. 
A solução da instância original consiste em alguns casos na combinação das 
soluções das instâncias parceais. 
 se o problema for trivial então 
 Resolver directamente; 
 senão 
 inicio 
 Fraqmentar o problema em dois ou mais problemas iguais; 
 Aplicar o método à cada um dos problemas; 
 Combinar as soluções parceias para resolver o problema original; 
 fim; 
 
 
 
6.2- Exemplos 
 
6.2.1- Números de Fibonacci 
 
Um exemplo da aplicação deste método é a sequência de Fibonacci. Essa 
sequência foi descoberta pelo matemático italiano Leonardo Fibonacci (1170-
1250), também conhecido como Leonardo de Pisa, quanto estudava o 
crescimento de uma população de coelhos. 
 
O problema consistia em saber quantos casais de coelhos poderão ser obtidos 
na n-ésina geração, se em cada mês, cada casal reproduzir um novo casal, 
que se torna fértil a partir do 2º mês. Vamos considerer que não ocorrerão 
mortes e temos um único casal de coelhos. 
 
Fibonacci descobriu que esse crescimento era descrito pela seguinte 
sequência: 
 
 0,1,1,2,3,5,8,13,21,… 
que mais tarde recebeu o seu nome em sua homenagem. 
 
Introdução as Técnicas Avançadas de Programação 
 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 83 
 
Pela composição da sequência, facilmente se constacta que o caso base 
acontece quando n = 0 e n = 1. Para esses casos temos: 
 
 Fibo (0) = 0 e Fibo (1) = 1; 
 
Vamos determinar o passo recursivo com a definição de uma fórmula 
recorrênte que exprime um número de Fibonacci como combinação de 
números de Fibonacci anteriores. Sabemos que: 
 n = 2 Fibo (2) = 1 
 = 1 + 0 
 = Fibo(0) + Fibo(1) 
 
 n = 3 Fibo (3) = 2 
 = 1 + 1 
 = Fibo(2) + Fibo(1) 
 
 n = 4 Fibo (4) = 3 
 = 2 + 1 
 = Fibo(3) + Fibo(2) 
 
Logo podemos concluir que para n > 1 
 Fibo(n) = Fibo(n-1) + Fibo(n-2) 
Estamos em condições de aplicar o esquema visto anteriormente para 
implementar uma função recursiva que calcula está sequência. 
/*------------------------------------------------------------------------------------------------------- 
Objectivo: Calcular o número de Finocacci 
Parâmetro Entrada: Um número natural 
Retorno da Função: Correspondente número de Fibonacci 
--------------------------------------------------------------------------------------------------------*/ 
int Fibo (int n) 
{ 
 if ( n <= 1 ) 
 return n; 
 return Fibo (n-1) + Fibo (n-2); 
} 
 
Para valores de n muito pequenos, esta função devolve o número de Fibonacci 
num intervalo de tempo aceitável, mas para valores muito grandes o tempo de 
processamento não é aceitável. 
 
A diminuição da eficiência do algoritmo deve-se a dupla chamada recursiva, 
que efectua muitas de chamadas e, como consequência, vai diminuindo a 
velocidade de processamento a medida que o programa vai sendo executado. 
 
Introdução as Técnicas Avançadas de Programação 
 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 84 
 
Vamos mostrar em seguida o funcionamento desta função. Para tornar a 
simulação mais perceptível, vamos declarar uma variável auxiliar que irá 
receber o número de Fibonacci e inserir algumas mensagens no código-fonte. 
 
int Fibo (int n) 
{ 
 int F; 
 printf(" Entrar em Fibo(%d) \n ", n); 
 
 if ( n <= 1 ) 
 F = n; 
 else 
 F = Fibo (n-1) + Fibo (n-2); 
 
 printf( " Sair de Fibo(%d), Retorna = %d \n ",n,F); 
 return F; 
} 
 
Suponhamos, sem perda da generalidade que n = 4. A função imprime as 
seguintes mensagens: 
 
 Entrar em Fibo (4) 
 Entrar em Fibo (3) 
 Entrar em Fibo (2) 
 Entrar em Fibo(1) 
 Sair de Fibo (1), Retorna = 1 
 Entrar em Fibo (0) 
 Sair de Fibo (0), Retorna = 0 
 Sair de Fibo (2), Retorna = 1 
 Entrar em Fibo (1) 
 Sair de Fibo (1), Retorna = 1 
 Sair de Fibo (3), Retorna = 2 
 Entrar em Fibo (2) 
 Entrar em Fibo (1) 
 Sair de Fibo (1), Retorno = 1 
 Entrar em Fibo (0) 
 Sair de Fibo (0) , Retorno = 0 
 Sair de Fibo (2) , Retorno = 1 
 Sair de Fibo (4) , Retorno = 3 
 
Ao contrário do processo recursivo linear visto no capítulo anterior, estamos 
perante a existência de múltiplas fases de expansão e de contracção, que são 
originadas pela dupla recursão existente na função fibo(). 
 
A título ilustractivo, mostramos a árvore de recursão gerada por este processo 
para n = 4. 
 
 
 
 
Introdução as Técnicas Avançadas de Programação 
 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 85 
 
 fibo(4) 
 / \ 
 fibo(3) fibo(2) 
 / \ / \ 
 fibo(2) fibo(1) fibo(1) fibo(0) 
 / \ | | | 
 fibo(1) fibo(0) 1 1 0 
 | | 
 1 0 
 
 
6.2.2 – Impressão dos Elementos de um Vector 
 
Seja T = (t0,t1,…,tultPos) um conjunto de elementos armazenados num vector T, 
tal que ultPos < dimensão do vector. A resolução do problema consiste em 
dividir o conjunto T em dois subconjuntos com comprimentos aproximadamente 
iguais: 
 
 T1= (t0,t1,…..,tk) e T2=(tk+1,tk+2,….,tultPos) onde k = ultPos/2 
 
Resolvemos o problema de forma separada para os subconjuntos T1 e T2, 
imprimindo desse modo todos os seus elementos. Então o nosso problemaconsiste em saber imprimir os elementos de casa subconjunto. Se aplicarmos o 
método de dividir cada subconjunto ao meio até chegarmos a um conjunto 
unitário temos uma parte do problema resolvido. A outra parte que 
necessitamos de resolver é trivial, basta imprimir o conteudo do conjunto 
unitário. Então a solução do problema original está resolvida. Ela é a união da 
impressão de todos os subconjuntos unitários gerados pelo processo recursivo. 
 
/*-------------------------------------------------------------------------------------------------------- 
Objectivo: imprimir todos os elementos de um um vector 
Parâmetro Entrada: Vector, posição do primeiro e último elemento 
--------------------------------------------------------------------------------------------------------*/ 
void imprimirElementos (float A[ ], int i, int f ) 
{ 
 if ( i == f ) 
 printf ( " %f", A[i] ); 
 else 
 { 
 k = (i+f)/2; 
 imprimirElementos (A,i,k); 
 imprimirElementos (A,k+1,f); 
 } 
} 
 
 
6.2.3 – Número de Elementos de um Vector 
 
Seja T = (t0,t1,…,tultPos) um conjunto de elementos armazenados num vector T, 
tal que ultPos < dimensão do vector. A resolução do problema consiste em 
Introdução as Técnicas Avançadas de Programação 
 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 86 
 
dividir o conjunto T em dois subconjuntos com comprimentos aproximadamente 
iguais: 
 
 T1= (t0,t1,…..,tk) e T2=(tk+1,tk+2,….,tultPos) onde k = ultPos/2 
 
Resolvemos o problema de forma separada para os subconjuntos T1 e T2, 
obtendo, desse modo, os totais de elementos de cada subconjunto. A solução 
original consiste na soma das soluções parciais. 
 
/*-------------------------------------------------------------------------------------------------------- 
Objectivo: Calcular o número de elementos de um vector 
Parâmetro Entrada: Vector, Primeiro e último elemento de um vector 
Retorno da Função: Quantidade de elemento do vector 
--------------------------------------------------------------------------------------------------------*/ 
int totalElementos (float A[ ], int i, int f ) 
{ 
 int total1, total2, k; 
 if ( i == f ) return 1; 
 k = (i+f)/2; 
 total1= totalElementos (A,i,k); 
 total2= totalElementos (A,k+1,f); 
 return total1 + total2; 
} 
 
Optimizando este algoritmo, temos: 
 
/*-------------------------------------------------------------------------------------------------------- 
Objectivo: Calcular o número de elementos de um vector 
Parâmetro Entrada: Vector, posição do primeiro e último elemento 
Retorno da Função: Quantidade de elemento do vector 
--------------------------------------------------------------------------------------------------------*/ 
int totalElementos ( float A[ ], int i, int f ) 
{ 
 int k; 
 if ( i == f ) return 1; 
 k = (i+f)/2; 
 return totalElementos (A,i,k) + totalElementos (A,k+1,f); 
} 
 
 
6.2.4 – Elemento Máximo de um Vector 
 
Seja T = (t0,t1,…,tultPos) um conjunto de elementos armazenados num vector T, 
tal que ultPos < dimensão do vector. A resolução do problema consiste em 
dividir o conjunto T em dois subconjuntos com comprimentos aproximadamente 
iguais: 
 
 T1= (t0,t1,…..,tk) e T2=(tk+1,tk+2,….,tultPos) onde k = ultPos/2 
 
Introdução as Técnicas Avançadas de Programação 
 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 87 
 
Resolvemos o problema de forma separada para os subconjuntos T1 e T2, 
obtendo, desse modo, os elementos máximos de cada subconjunto. max1 e 
max2. A solução original consiste na comparação dos elementos máximos das 
soluções parciais. 
 
/*------------------------------------------------------------------------------------------------------- 
Objectivo: Calcular o elemento máximo de um vector 
Parâmetro Entrada: Vector, posição do primeiro e do último elemento 
Retorno da Função: O maior elemento do vector 
--------------------------------------------------------------------------------------------------------*/ 
int maiorElemento (float A[ ], int i, int f ) 
{ 
 int max1, max2,k; 
 if ( i == f ) return A[I]; 
 k = (i+f)/2; 
 max1 = maximo (i, k, lista); 
 max2 = maximo (k+1, f, lista); 
 return DevolveMaior (max1,max2); 
} 
 
O paradigma de Divisão e Conquista produz algoritmos mais elegantes e mais 
eficiêntes do que os algoritmos iterativos (força Bruta). Contudo esses 
algoritmos não são eficiêntes porque baseam-se em soluções recursivas e, 
como consequência, gastam mais recursos de memória para serem 
executados. 
 
 
6.3 – Eliminação da Recursão 
 
6.3.1- Números de Fibonacci 
 
Observe que, para o cálculo do Fibonacci de 4, repetimos duas vezes o cálculo 
do Fibonacci de 2, três vezes o cálculo do Fibonacci de 1 e duas vezes o 
cálculo do Fibonacci de 0. 
 
Para evitar essa repetição e melhorar a eficiência da função, podemos adoptar 
a seguinte estratégia: Calcular os valores de baixo para cima e utilizar um 
vector para armazenar os valores já calculados. 
 
Este método foi proposto pelo matemático Richard Bellman em 1957 e é 
conhecido como o paradigma da programação dinâmica. A programação 
dinâmica reduz o tempo de cálculo da função, mais aumenta os recursos de 
memória necessários para correr o programa. 
 
A solução, para este caso, baseia-se em armazenar os dois primeiros números 
de Fibonacci num vector e utilizar essa posição para calcular os restantes. 
 
 
 
Introdução as Técnicas Avançadas de Programação 
 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 88 
 
int FiboDinamico(int n) 
{ 
 int i, fib[50] = {0,1}; 
 if (n <= 1) return n; 
 for ( i = 2; i <= n ; i++) 
 fib[i] = fib[i-1] + fib[i-2]; 
 return fib[n]; 
} 
 
Contudo, para calcular o Fibonacci de n, necessitamos de conhecer apenas o 
valor do Fibonacci de n-1 e n-2. Então, podemos gerar essa sequência 
utilizando três variáveis auxiliares do tipo inteiro. Uma, denominada por anterior 
que armazena o valor do Fibonacci de n-2, outra que denominados por actual 
que armazena o Fibonacci de n-1 e uma terceira que denominados por próximo 
que guardará o Fibonacci de n. Apresentamos em seguida, uma versão que 
implementa essa estratégia: 
 
int FiboIterativo(int n) 
{ 
 int i, anterior = 0, actual = 1, proximo; 
 if (n <= 1) return n; 
 for (i = 2; i <= n ; i++) 
 { 
 proximo = actual + anterior; 
 anterior = actual; 
 actual = proximo; 
 } 
 return proximo; 
} 
 
 
6.3.2- Coeficientes Binomiais 
 
O Coeficiente Binomial C(n,k) que representa o números de combinações de n 
k a k elementos é descrito pela fórmula: 
 
 C(n,k) = 
𝑛!
(𝑛−𝑘)! 𝑥 𝑘!
 
 
Mesmo com valores que possam ser representados por variáveis do tipo 
inteiro, em muitos casos, os valores parcelares podem ficar corrompidos, 
devido ao estoiro da capacidade de representação dessas variáveis. Uma 
forma de resolver esse problema passa pela eliminação do cálculo do factorial, 
através de uma fórmula recorrênte descoberta pelo Matemático Francês, Baise 
Pascal (1623 a 1662) que é conhecido como triângulo de Pascal. 
 
 c(n,k) = 0 se k > n 
 c(n,k) = 1 se k = 0 
 c(n,k)= 1 se n = 0 
 c(n,k) = c(n-1,k-1) + c(n-1,k) se n > 0 e k > 0 
Introdução as Técnicas Avançadas de Programação 
 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 89 
 
 
 
A condição k > n serve para evitar que a função entre num processo recursivo 
anormal e a sua solução é trivial. Se k = 0 ou n = 0 a solução também é trivial. 
Para k > 0 e n > 0 a resolução passa pela separação do problema em dois 
subproblemas de menor complexidade, o cálculo de C(n-1,k-1) e cáculo de 
C(n-1,k). A solução do problema original consiste na soma das soluções dos 
problemas parciais. Então, este problema recursiva pode ser modelado por: 
 
 - Caso Base: 0 se k > n ou 1 se n = 0 ou k = 0 
 - Caso Recursivo: c(n-1,k-1) + c(n-1,k) 
 
que é implementada pela seguinte função: 
 
int combinacoesRecursivas (int n, int k) 
{ 
 if ( k > n ) return 0; 
 if ( k = 0 || n = 0 ) return 1; 
 return combinacoesRecursivas (n-1,k-1) + combinacoesRecursivas (n-1,k); 
} 
 
Esta implementação não é aconselhável porque a função repete o cálculo de 
algumas combinações se os números inteiros n e k forem muito grandes. Mas 
a grande deficiência do algoritmo, resida na dupla chamada recursiva, que 
provoca o crescimento muito rápido de chamadas, diminuindo desse modo a 
velocidade de processamento a medida que o programa vai sendo executado. 
 
A solução dinâmica que apresentamos em seguida exige a utilização de uma 
matriz para armazenar os coeficientes binomiais. 
 
int CombinacoesDinamico ( int n, int k) 
{ 
 int i, j, min, bicoef[30][30]; 
 if ( k > n ) return 0; 
 if ( k == 0 || n == 0 ) return 1; 
 for ( i = 0; i <= n ; i ++ ) 
 { 
 min = minimo (i,k); 
 for ( j = 0; j <= min; j++ ) 
 if ( j == 0 || j == i ) 
 bicoef[i][j] = 1; 
 else 
 bicoef[i][j] = bicoef[i-1][j-1] +bicoef[i-1][j]; 
 } 
 return bicoef[n][k]; 
} 
 
 
 
 
Introdução as Técnicas Avançadas de Programação 
 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 90 
 
6.4 – Recomendações Bibliográficas 
 
Para o leitor aprofundar este assunto, recomendamos o livro de Sedgewick R.;- 
Algorithms in C Parts 1-4, Addison-Wesley, 1998, ou o livro de Roberts E.S.;- 
Programming Abstractions in C: a Second Couse in Computer Science, 
Addison-Weles, 1998. 
Na língua portuguesa recomendamos o livro de Rocha A. A.;- Análise da 
Complexidade de Algoritmos, Editora FCA, Portugal, 2014, ou o livro de Ziviani 
N.;- Projeto de Algoritmos com Implementações em Pascal e C, Pioneira 
Pioneira Thomson Learning, 2ª. edição, Brasil, 2004. 
 
6.5 – Exercícios 
 
6.5.1- Desenvolva uma função que recebe como parâmetro um número inteiro 
não negativo n e devolve a sequencia de Lucas descrita pela fórmula 
recorrênte: 
 
 Lucas(n) = 2 Se n = 0 
 Lucas(n) = 1 Se n = 1 
 Lucas (n) = Lucas(n-1) + Lucas(n-2) Se n > 2 
 
6.5.2- Desenvolva uma função que recebe como parâmetro um número inteiro 
não negativo n e devolve a potência desse número, descrita pela seguinte 
fórmula recorrênte: 
 
 an = 1 Se n = 0 
 an = ( an/2)2 Se n é par 
 an = a x ( an/2)2 Se n é impar 
 
6.5.3- Dada a fórmula recorrênte. 
 
 G(n) = 2 Se n = 0 
 G(n) =1 Se n = 1 
 G(n) =3 Se n = 2 
 G(n)= G(n-1) + 5G(n-2) + 3G(n-3) Se n > 3 
 
Desenvolva uma função que recebe como parâmetro um número inteiro não 
negativo n e devolve como retorno da função o valor de G(n) utilizando o 
paradigma da programação dinâmica. 
 
6.5.4- Desenvolva uma função eficiente para calcular o número de Tribonacci. 
A sequência de Tribonacci pode ser definida pela seguinte relação de 
recorrência. 
 
 Tribonacci(n) = 0 Se n = 0 
 Tribonacci(n) = 1 Se n = 1ou n = 2 
Introdução as Técnicas Avançadas de Programação 
 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 91 
 
 Tribonacci(n) = tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3) Se n > 3 
 
Desenvolva uma função recursiva e outra com a programação dinâmica. 
 
6.5.5- Desenvolva uma função que entre outros parâmetros recebe um vector 
com números inteiros e um determinado valor. Determinar o elemento do 
vector que mais se aproxima desse valor. 
 
6.5.6-Desenvolva uma função que entre outros parâmetros recebe dois 
vectores do mesmo tipo e com a mesma dimensão. Verificar se esses vectores 
são iguais. 
 
6.5.5-Desenvolva uma função que entre outros parâmetros recebe um vector 
do tipo carácter um determinado valor. Contar o número de vezes que esse 
valor está contido nesse vector. 
 
6.5.7-Desenvolva uma função que entre outros parâmetros recebe dois 
vectores ordenados em ordem decrescente. Intercalar esses vectores num 
terceiro vector sem repetir os seus elementos. 
 
6.5.8-Desenvolva uma função que entre outros parâmetros recebe um vector e 
uma determinada posição k. Separar o vector em dois de tal forma que os 
elementos que se encontram nas posições de 0 à k, vão para o primeiro vector 
e os restantes para o segundo. 
 
6.5.9-Desenvolva uma função que entre outros parâmetros recebe um vector e 
uma determinada chave. Verificar se essa chave encontra-se no vector e 
devolver False se a chave não for encontrada ou True no caso contrário. 
 
6.5.10-Desenvolva uma função que entre outros parâmetros recebe um vector. 
Contar o número de zeros existentes nesse vector. 
 
6.5.11-Desenvolva uma função que entre outros parâmetros recebe um vector. 
Contar o número de elementos pares e o número de elementos ímpares. 
 
6.5.12-Desenvolva uma função que entre outros parâmetros recebe um vector. 
Determinar o valor máximo e o valor mínimo. 
6.5.13-Um camionista pretende sair de Luanda para Benguela pela estrada 
nacional. O tanque de combustível do seu camião está cheio e, contém 
gasóleo suficiente para n quilômetros. O Googlemaps instalado no seu camião 
fornece as distâncias entre os postos de gasolina existentes nessa estrada. O 
motorista deseja fazer o mínimo possível de paradas para abastecimento ao 
longo do caminho. Desenvolva um algoritmo eficiente para que o motorista 
possa determinar em quais postos de gasolina deve parar. 
 
 
 
 
 
Introdução as Técnicas Avançadas de Programação 
 
Para uso exclusivo dos alunos da Faculdade de Engenharia de Universidade Católica de Angola Prof. Manuel Menezes 92 
 
6.6 – Projectos de Programação 
 
 
6.6.1-Desenvolva um programa que utilize o paradigma de divisão e conquista 
para multiplicar duas matrizes de ordem nxn. Utilize obrigatóriamento o 
algoritmo de Strassen. 
 
6.6.2- Implemente um programa que dado dois números inteiro muito grandes 
A e B (da ordem de 100 dígitos decimais) calcular o produto de A e B. 
a) Utilize a estratégia de força bruta (multiplicação tradicional). 
b) Utilize a estratégia de divisão e conquista baseada no algoritmo de 
Karatsuba.