Algoritmos matemáticos básicos que todo cara da computação deveria saber_versao1

Prévia do material em texto

Algoritmos matemáticos básicos que todo cara da computação deveria 
saber 
 
Algoritmo 1 : Conversão da base 10 para a base b 
Primeiramente, vamos começar com o algoritmo de mudança de base numérica. Para 
converter um número da base 10 para uma base b qualquer podemos efetuar 
sucessivas divisões do número pela base b; o resto das divisões serão os dígitos do 
número da nova base só que na ordem inversa. 
 
 
 
 
Calcular número de dígitos d de número n na base b 
 
d = log b n = 
 
void base(int n, int b, int novo[], int * tam){ 
 int k; 
 k = *tam = floor( log(n)/log(b) + 0.5) + 1; 
 while( n > 0){ 
 k--; 
 novo[k] = n % b; 
 n = n / b; 
 } 
} 
 
Complexidade O(logbn) 
 
Algoritmo 2: Conversão de um número da base b para a base 10 
 
Podemos converter um número da base b para a base 10 através desta 
expressão: 
 
N = an.b
n + .... + a2.b
2 + a1.b
1 + a0.b
0 
 
 
 
 
 
Vamos reescrever essa expressão da seguinte maneira: 
 
N =b( an.b
n-1 + .... + a2.b
1 + a1.b
0 ) + a0.b
0
 
N =b( b( an.b
n-2 + .... + a2.b
0 )+ a1.b
0 ) + a0.b
0
 
N =b( b( an.b
n-2 + .... + a2.b
0 )+ a1.b
0 ) + a0.b
0
 
N =b(...b(b(an ) + an-1)...) + a0.b
0 
 
Agora, podemos calcular o número na base b realizando n multiplicações. 
N = 100112 
A[0] = 1 
A[1] = 0 
A[2] = 0 
A[3]= 1 
A[4] = 1 
 
X[0] = A[0] 
X[i] = X[i-1]*B + A[i] 
 
N = X[4] 
 
X[0] = 1 
X[1] = 2 + 0 = 2 
X[2] = 4 + 0 = 4 
X[3] = 8 + 1 = 9 
X[4] = 18 +1 = 19 
 
int base(int b, int novo[] , int tam){ 
 int n,i; 
 n = novo[0]; 
 for(i=1;i<tam;i++){ 
 n = n*b; 
 n = n + novo[i]; 
 } 
 return n; 
} 
 
 
 Complexidade O(n) multiplicações e soma 
 
 
Máximo divisor Comum de a e b 
 
Encontrar o maior número d que divide a e b simultaneamente. 
Sabemos que se d divide a e d divide b então d < a e d < b; 
 
Algoritmo 1: Força bruta 
 
int mdc1(int a,int b){ 
 
 int i,d; 
 
 d = a < b ? a : b; 
 
 for(i=d;i>=1;i--){ 
 if(a%i==0 && b%i==0) return i; 
 } 
 
} 
 
Complexidade O( min(a,b) ) 
 
 
Algoritmo 2: Busca Binária 
int mdc2(int a,int b){ 
 int i,f,meio,d; 
 d = a < b ? a : b; 
 i = 1; 
 f = d; 
 while( i < f ){ 
 meio = (i + f) / 2; 
 if( a%meio ==0 && b%meio==0) i = meio; 
 else f = meio-1; 
 } 
 return i; 
} 
 
Complexidade O( lg min(a,b) ) 
 
 
 
 
 
 
 
Algoritmo 3: Algoritmo de Euclides: 
 
 
 
 
int mdc3(int a,int b){ 
 if(b==0) return a; 
 else return mdc3(b,a%b); 
} 
 
 
O número de chamadas deste algoritmo é proporcional ao número de 
Fibonacci pelo seguinte teorema: 
 
Teorema: 
Se a > b >= 0 e euclides(a,b) executa k >= 1 chamadas recursivas então a 
>= Fk+2 e b >= Fk+1. 
Suponha que a e b são dois números de Fibonacci consecutivos então 
O número de chamadas recursivas de EUCLIDES(Fk+2,Fk+1) é igual ao 
número de chamadas recursivas EUCLIDES(Fk+1, Fk+2 mod Fk+1) + 1. 
Temos que Fk+2 = Fk+1 + Fk mod Fk+1 = Fk. . Logo, EUCLIDES(Fk+1, Fk+2 mod 
Fk+1) = EUCLIDES(Fk+1, Fk) com k -1 chamadas recursivas. 
O número de chamadas recursivas de EUCLIDES(Fk+2,Fk+1) é k-1 +1. 
 
Este teorema pode ser utilizado para estimar um limite superior para o 
número de chamadas recursivas do algoritmo. 
 
Complexidade O(k) , b >= Fk+1 
 
Algoritmo 4: Mdc Binário 
 
int gcd(int u, int v){ 
 if( u == v ) return u; 
 if( u == 0 ) return v; 
 if( v == 0 ) return u; 
 
 if(u%2 == 0){ // se u é par 
 if(v%2 == 0) // u and v são pares 
 return (2*gcd(u/2, v/2)); 
 else // u é par and v é impar 
 return gcd(u/2, v); 
 } 
 else if(v%2 == 0) // u é impar e v é par 
 return gcd(u, v/2); 
 else{ // ambos são impares 
 if(u>=v) 
 return gcd((u-v)/2, v); 
 else 
 return gcd((v-u)/2, u); 
 } 
} 
 
Usando operações com bits: 
 
int gcd(int u, int v){ 
 if( u == v ) return u; 
 if( u == 0 ) return v; 
 if( v == 0 ) return u; 
 
 if(u & 1==0){ // se u é par 
 if( v & 1 == 0) // u and v são pares 
 return (gcd(u >> 1, v >> 1) << 1); 
 else // u é par and v é impar 
 return gcd(u >> 1, v); 
 } 
 else if(v & 1 ==0) // u é impar e v é par 
 return gcd(u, v >> 1); 
 else{ // ambos são impares 
 if(u>=v) 
 return gcd((u-v) >> 1, v); 
 else 
 return gcd((v-u) >> 1, u); 
 } 
} 
 
Algoritmo : Calcular ab 
 
Podemos definir o algoritmo ab diretamente da seguinte definição 
recursiva: 
 
 
 
 
def exp(a,b): 
 if b==0: return 1 
 else: return a*exp(a,b-1) 
 
O número de multiplicações é definido pela seguinte relação de 
recorrência: 
T(n) = T(n-1) +1 
T(0) = 0 
Aplicando o método da substituição, temos: 
T(n) = T(n-1) + 1 
T(n-1) = T(n-2)+1 
... 
T(n-(k-1))=T(n-k)+1 
Simplificando as equações, temos: 
T(n) = T(n-1) + 1 
T(n-1) = T(n-2)+1 
... 
T(n-(k-1))=T(n-k)+1 
T(n)=T(n-k)+k 
Tome n-k=0 isso implica que k=n. 
T(n) = T(0)+n 
T(n) = n 
 
Podemos reduzir o número de multiplicações, alterando a definição 
recursiva para a seguinte maneira: 
 
 
 
def fastexp(a,b): 
 if b==0 : return 1 
 else: 
 if b%2==0: 
 x = fastexp(a,b/2) 
 return x*x 
 else: 
 return a*fastexp(a,b-1) 
 
O número de multiplicações é definido pela seguinte relação de 
recorrência supondo que n é uma potência de 2: 
T(n) = T(n/2) +1 
T(1) = 1 
Aplicando o método da substituição, temos: 
T(n) = T(n/2) + 1 
T(n/2) = T(n/4)+1 
... 
T(n/2k-1)=T(n/2k)+1 
Simplificando as equações, temos: 
T(n) = T(n/2) + 1 
T(n/2) = T(n/4)+1 
... 
T(n/2k-1)=T(n/2k)+1 
T(n)=T(n/2k)+k 
Tome n/2k=1 isso implica que k=log 2n. 
T(n) = T(1)+ log 2n 
T(n) = log 2n + 1 
 
Algoritmo: Número de Fibonacci 
 
A definição recursiva do algoritmo fibonacci é a seguinte: 
 
 
O algoritmo iterativo pode ser definido da seguinte maneira: 
 
 
 
 
 
 
 
def fibo_iterativo(n): 
 if n <= 2: return 1 
 else: 
 ant = 1 
 atual = 1 
 i = 2 
 while i < n: 
 prox = ant+atual 
 ant = atual 
 atual = prox 
 i = i+1 
 return prox 
 
Complexidade O(n) 
 
Podemos calcular o número de fibonacci a partir da 
seguinte equação matricial: 
 
 
 
Utilizando a exponenciação rápida para realizar a 
multiplicação matricial podemos obter o seguinte 
algoritmo: 
 
def fastfibo(n): 
 [a,b,c,d] = matriz_exp(1,1,1,0,n) 
 return b 
 
def matriz_exp(a,b,c,d,n): 
 
 if n==1: 
 return [a,b,c,d] 
 if n==0: 
 return [1,0,0,1] 
 
 if(n%2==1): 
 [a1,b1,c1,d1] = matriz_exp(a,b,c,d,n-1) 
 return [a*a1+b*c1,a*b1+b*d1,a1*c+d*c1,c*b1+d1*d] 
 else: 
 [a1,b1,c1,d1] = matriz_exp(a,b,c,d,n/2) 
 return [a1*a1+b1*c1,a1*b1+b1*d1,a1*c1+d1*c1,c1*b1+d1*d1] 
 
Complexidade O(log2n)