Atividade - Semana 6 Resolvida-2022 1

1 Atividade - Semana 6 1. Considere um vetor desconhecido v de tamanho N, sendo N ´ımpar. Todos os elementos do vetor s˜ao distintos assumindo valores entre 1 e N com r´otulos entre 1 e N. A ´unica maneira de comparar os elementos do vetor ´e atrav´es da func¸˜ao med3(a, b, c) que recebe o r´otulo de 3 elementos do vetor e devolve o r´otulo do elemento que est´a no meio, ou seja: min{v[a], v[b], v[c]} < v[med3(a, b, c)] < max{v[a], v[b], v[c]} Al´em da func¸˜ao med3, temos a func¸˜ao GetN sem argumentos devolve o tamanho do vetor v. Considere o seguinte vetor: R´otulo 1 2 3 4 5 Elemento 2 5 4 3 1 Podemos encontrar a mediana do vetor realizando as seguintes perguntas: 1. GetN devolve 5. 2. Med3(1,2,3) devolve 3. Como v[3] est´a entre v[1] e v[2], podemos concluir que os elementos est˜ao ordenados de duas maneiras: • v[1],v[3],v[2] • v[2],v[3],v[1] Note que nas duas ordens poss´ıveis, v[1] e v[3] est˜ao do mesmo lado com relac¸˜ao a v[2]. 3. Med3(3,4,1) devolve 4. Como v[4] est´a entre v[1] e v[3], podemos concluir que os elementos est˜ao ordenados de duas maneiras: • v[1],v[4],v[3],v[2] • v[2],v[3],v[4],v[1] 4. Med3(4,2,5) devolve 4. Como v[4] est´a entre v[2] e v[5], v[2] e v[5] est˜ao em lados contr´arios com relac¸˜ao a v[4]. Logo, v[1] e v[5] aparecem de um lado de v[4] e v[2] e v[3] aparecem do outro lado. Logo, v[4] ´e a mediana. a) Proponha um algoritmo que devolve os r´otulos do maior e do menor do elemento vetor realizando N − 2 chamadas da func¸˜ao med3 em qualquer ordem. (Pense inicialmente em um vetor de tamanho 3). b) Proponha um algoritmo que encontra a mediana do vetor removendo repetidamente o maior e o menor do vetor. 2 c) Quando realizamos uma chamada da func¸˜ao med3(a, b, c) ̸= c, sabemos que a e b est˜ao no mesmo lado, ou seja, a chamada da func¸˜ao med3(a,b,c) ordena a e b com relac¸˜ao a c. No exemplo acima, med3(1,2,3) = 3, ent˜ao sabemos que os elementos 1 e 3 est˜ao no mesmo lado com relac¸˜ao ao elemento na posic¸˜ao 2. Proponha um algoritmo capaz de ordenar o vetor em uma ordem qualquer (crescente ou decrescente) usando essa id´eia acima. Quest˜oes (a) void minMaxFunc(){ int min = 1, med = 2, max = 3; for (int i = getN -2 ; i > 0; i--){ if(min > max){ int temp = min; min = max; max = temp; } int index = med3(min, med, max); if(min == index){ min = med; if(med < max) med = max; } else if(max == index){ int temp = max; max = med; if(med < temp) med = temp; } med++; } if(v[min] > v[max]){ temp = min; min = max; max = temp; } printf("%d %d\n",v[min], v[max]); return; } 1 (b) void tiraMinMax(int min, int max){ int tmin = 0; int tmax = 0; for(int i = N-1; i >= 0; i--){ if(v[i] != -1){ if(v[i] == v[max] && !tmax){ v[i] = -1; tmax = 1; // true } else if(v[i] == v[min] && !tmin){ v[i] = -1; tmin = 1; // true } else{ if(!tmin){ int temp = v[i]; v[i] = -1; v[min] = temp; tmin = 1; // true } else if(!tmax){ int temp = v[i]; v[i] = -1; v[max] = temp; tmax = 1; //true; } } } if(tmin && tmax) break; } N = N-2; return; } void medFunc(){ if(N == 3){ int min = 0, max = 0; minMaxFunc(&min, &max); tiraMinMax(min, max); } for (i = getN - 3; i > 0; i--){ int min =0, max = 0; minMaxFunc(&min,&max); tiraMinMax(min,max); } printf("%d\n", v[0]); 2 } Visto que n˜ao foi especificado em que linguagem deveria ser feito o al- goritmo, optei por fazer em C. Al´em disso, considerei que o vetor e seu tamanho eram vari´aveis globais, por isso as fun¸c˜oes n˜ao recebem parˆametros. OBS: A fun¸c˜ao minMaxFunc com parˆametros usa ponteiros para atribuir `a duas vari´aveis os ´ındices dos valores de m´ınimo e m´aximo do vetor, en- quanto que o tiraMinMax coloca as vari´aveis no fim do vetor fazendo um swap entre valores que s˜ao relevantes. Infelizmente n˜ao pude fazer a quest˜ao 3, porque me falta tempo. 3