*10. Uma de quatro moedas pode ser falsa. Se ela for falsa, pode ser mais leve ou mais pesada do que as outras. Quantas pesagens são necessárias, usando uma balança de pratos, para determinar se existe uma moeda falsa e, se existir, se ela é mais leve ou mais pesada do que as outras? Descreva um algoritmo para encontrar a moeda falsa e determinar se ela é mais leve ou mais pesada do que as outras usando este número de pesagens.
11. Encontre o número mínimo de comparações necessárias para ordenar quatro elementos e desenvolva um algoritmo que ordene esses elementos usando este número de comparações.
*12. Encontre o número mínimo de comparações necessárias para ordenar cinco elementos e desenvolva um algoritmo que ordene esses elementos usando este número de comparações.
11. Encontre o número mínimo de comparações necessárias para ordenar quatro elementos e desenvolva um algoritmo que ordene esses elementos usando este número de comparações.
*12. Encontre o número mínimo de comparações necessárias para ordenar cinco elementos e desenvolva um algoritmo que ordene esses elementos usando este número de comparações.
Passo 1
No exercício sobre a moeda falsa, temos quatro moedas e uma balança de pratos. Pode não haver moeda falsa ou, caso exista, ela é exatamente uma e pode ser mais leve ou mais pesada que as outras. O conteúdo usado será argumentação de informação (número de casos possíveis) e estratégia de pesagens em árvore de decisão.
Passo 2
Contamos todas as possibilidades que precisamos distinguir: ou não há moeda falsa (1 caso) ou há uma das quatro moedas falsa e ela é leve ou pesada (
casos). No total são
situações distintas.
Passo 3
Cada pesagem numa balança de pratos tem três resultados possíveis (esquerdo mais leve, direito mais leve ou equilíbrio), logo
pesagens distinguem até
resultados. Para cobrir 9 casos precisamos de
pois
. Portanto, são necessárias 2 pesagens.
Passo 4
Algoritmo em dois níveis de pesagem:
- Primeira pesagem: compare moeda 1 contra moeda 2.
- Se empata, nem 1 nem 2 são falsas; a falsa está em {3,4} ou não existe.
- Se não empata, uma de 1 ou 2 é falsa; 3 e 4 são boas.
- Segunda pesagem:
- Se primeiro empate:
- Pese 3 contra 4. Se empatar, não há moeda falsa; se não, a mais leve ou mais pesada é a falsa, conforme o lado que subir ou descer.
- Se primeiro desequilíbrio (suponha 1 pesa menos que 2):
- Pese 1 contra 3 (sabendo que 3 é boa). Se 1 empatar com 3, então a falsa é a 2 e é mais pesada. Se 1 continuar mais leve, 1 é falsa e é mais leve.
Este esquema de dois níveis resolve todos os 9 casos.
Passo 5
No exercício de ordenar quatro elementos
, contamos as permutações possíveis, que são
. Cada comparação binária dá dois ramos, então precisamos de
comparações com
Logo o mínimo é 5 comparações.
Passo 6
Algoritmo em 5 comparações:
- Compare
e . Guarde menor em , maior em . - Compare
e . Guarde menor em , maior em . - Compare
e . O maior é o máximo global; o outro é um candidato intermediário alto. - Compare
e . O menor é o mínimo global; o outro é um candidato intermediário baixo. - Compare os dois candidatos intermediários para definir a ordem entre eles.
No fim reunimos, da esquerda para a direita, o mínimo, o menor intermediário, o maior intermediário e o máximo.
Passo 7
No exercício de ordenar cinco elementos
, há
permutações. Cada comparação produz 2 ramos, logo precisamos de
tal que
pois
e
. Portanto o mínimo é 7 comparações.
Passo 8
Usamos primeiro o algoritmo de 5 comparações para ordenar
(como na questão anterior). Obtemos em 5 comparações uma lista totalmente ordenada de quatro elementos, digamos
.
Passo 9
Em até 2 comparações inserimos
na lista de quatro já ordenada por busca binária:
- Compare
com . - Se
, compare com ; caso contrário, compare com .
Dependendo do resultado, colocamosna posição correta entre .
No pior caso essa inserção exige 2 comparações, totalizando
.
Resposta
O número mínimo de comparações é 7.