Mínimo e Máximo
2 pág.

Mínimo e Máximo


DisciplinaPreparação para Maratona de Programação I17 materiais19 seguidores
Pré-visualização1 página
Mínimo e Máximo 
O problema é determinar os valores mínimos e máximos de um conjunto de números S. O algoritmo trivial seria esse: 
 
#include <stdio.h> 
#define MAX 100 
int v[MAX]; 
int main(){ 
 int n,min,max,comp,i; 
 while(1){ 
 scanf(&quot;%d&quot;,&n); 
 scanf(&quot;%d&quot;,&v[0]); 
 min = v[0]; 
 max = v[0]; 
 
 comp = 0; 
 for(i=1;i<n;i++){ 
 scanf(&quot;%d&quot;,&v[i]); 
 if(v[i] < min){ 
 min = v[i]; 
 } 
 if(v[i] > max){ 
 max = v[i]; 
 } 
 comp += 2; 
 } 
 printf(&quot;min: %d\n&quot;,min); 
 printf(&quot;max: %d\n&quot;,max); 
 printf(&quot;comparacoes: %d\n&quot;,comp); 
 } 
} 
O número de comparações executados por esse algoritmo é 2n-2. Será que podemos melhorar o número de 
comparações deste algoritmo. 
Considere o seguinte algoritmo: 
#include <stdio.h> 
#define MAX 100 
int v[MAX]; 
int min_max(int *v, int i, int f,int *min , int *max){ 
 int m,comp,min1,min2,max1,max2; 
 if(i==f){ *min = v[i]; *max = v[i];return 0; 
 }else if(i==f-1){ 
 if(v[i] < v[f]){*min = v[i]; *max = v[f]; 
 }else{*min = v[i];*max = v[f];} return 1; 
 }else{ 
 comp = 0;m = (i+f)/2; 
 comp += min_max(v,i,m,&min1,&max1); 
 comp += min_max(v,m+1,f,&min2,&max2); 
 if (min1<min2){*min = min1;}else{*min = min2;} 
 if (max1>max2){*max = max1;}else{*max = max2;} 
 comp += 2;return comp; 
 } 
} 
 
int main(){ 
 int n,min,max,comp,i; 
 while(1){ 
 scanf(&quot;%d&quot;,&n); 
 for(i=0;i<n;i++){ 
 scanf(&quot;%d&quot;,&v[i]); 
 } 
 comp = min_max(v,0,n-1,&min,&max); 
 printf(&quot;min: %d\n&quot;,min); 
 printf(&quot;max: %d\n&quot;,max); 
 printf(&quot;comparacoes: %d\n&quot;,comp); 
 } 
} 
O número de comparações deste algoritmo é 3n/2 \u2013 2. A idéia do algoritmo é a construção de dois vetores : um vetor 
dos valores máximos e um outro vetor de valores mínimos. Estes vetores são construídos durante a fase de comparações 
dois a dois do vetor inicial. O elemento perdedor vai para o vetor do mínimo e o elemento vencedor vai para o vetor de 
máximos. Depois podemos percorrer os dois vetores procurando o máximo do vetor máximo e o mínimo do vetor 
máximo. 
Número de comparações para a construção dos dois vetores de máximo e de mínimo \u2248 n/2 comparações 
Tamanho do vetor máximo e do vetor mínimo \u2248 n/2 
Número de comparações para encontrar o máximo do vetor máximo \u2248 n/2 -1 
Número de comparações para encontrar o mínimo do vetor mínimo \u2248 n/2 -1 
Total \u2248 n/2 + n/2 -1+ n/2 -1 \u2248 3n/2 -2 
Vamos mostrar este resultado usando a recorrência definida por esse algoritmo: 
C(n) = 2 C(n/2) + 2 
C(2) = 1 
 
 C(n) = 2 C(n/2) + 2 
2C(n/2) = 2 C(n/4) + 4 
2k-1C(n/2k-1) = 2k C(n/2k) + 2k 
---------------------------------------- 
C(n) = 2k C(n/2k) + 2 + 4 + \u2026 + 2k 
C(n) = 2k C(n/2k) + 2k-1 - 2 
 Faça n/2k = 2 => k = log2 n \u2013 1 
C(n) = 2k C(n/2k) + 2k-1 \u2013 2 => n/2 + n \u2013 2 = 3n/2 -2