Um amigo lhe diz que é capaz de ordenar qualquer conjunto de 6 números com no máximo 8 comparações. O seu amigo está falando a verdade ou mentindo? Justifique.
Passo 1
Então, o exercício diz que um amigo afirma que consegue ordenar qualquer conjunto de 6 números usando no máximo 8 comparações. A gente vai usar conceitos de ordenação e teoria das comparações para descobrir se ele está falando a verdade ou se está mentindo.
Passo 2
Primeiro, vamos entender o que significa ordenar números com comparações. Em algoritmos de ordenação, como o famoso “bubble sort” ou “quick sort”, a gente compara pares de números para decidir qual vem antes. Mas tem um limite mínimo de comparações necessárias para garantir que qualquer conjunto de números seja ordenado.
Passo 3
Esse limite mínimo pode ser encontrado calculando o logaritmo de base 2 do fatorial do número de elementos a serem ordenados. Matemática básica nos diz que para ordenar
elementos, a gente precisa de pelo menos
comparações no pior caso.
Passo 4
No caso desse exercício, temos
. Então, vamos calcular
e depois
:
Isso significa que precisamos de, no mínimo, cerca de 9.49 comparações. Como não dá para fazer uma parte de comparação, arredondamos para cima, resultando em 10 comparações necessárias.
Passo 5
Como o amigo está dizendo que consegue ordenar com no máximo 8 comparações, e vimos que são necessárias pelo menos 10 comparações, isso mostra que a afirmação dele é impossível de acordo com a teoria das comparações em ordenação.
Resposta
O amigo está mentindo. É necessário, no mínimo, 10 comparações para ordenar qualquer conjunto de 6 números.
Exercícios relacionados
Faça um código em
para gerar 10 números aleatórios (entre 1 e 50 ) e armazenar em um vetor. Apresente os números gerados na tela e depois organize o vetor com o método de ordenação BubbleSort. Ao final, apresente o vetor ordenado.
Faça um código para gerar 25 números aleatórios (entre 10 e 40 ) e armazenar em um vetor. Apresente os números gerados na tela e depois organize o vetor com o método de ordenação InsertionSort. Ao final, apresente o vetor ordenado.
Faça um programa em C para gerar apostas na Mega Sena com N dezenas (informada pelo usuário). Armazene os números gerados aleatórios no intervalo de 1 a 60 em um vetor. Lembre se que os N números precisam ser diferentes entre si, não podendo repetir o número adicionado no vetor.