Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como encontrar a moeda falsa de um saco com 8 moedas usando uma balança de pratos?

0 votos
868 visitas
perguntada Abr 14, 2015 em Ciência da Computação por danielcajueiro (5,376 pontos)  

Supõe-se que a moeda falsa é mais leve e deseja-se saber o menor número necessário de pesagens usando a balança de pratos.

Compartilhe

1 Resposta

+1 voto
respondida Abr 16, 2015 por Henrique Souza (626 pontos)  

Acredito que o método mais eficiente é a divisão binária.
Primeiro se divide as moedas em dois grupos de quatro moedas cada, e se compara o peso dos dois grupos.
Depois, retira-se duas moedas de cada grupo. Se o peso continuar desequilibrado, a moeda falsa está entre as 4 restantes, e se a balança se equilibrar, a moeda falsa está entre as 4 retiradas, e nesse caso substitui-se as moedas da balança pelas retiradas.
Em seguida, se retira uma moeda de cada grupo. Se o peso continuar desequilibrado, encontramos a moeda falsa, se a balança se equilibrar, uma das duas moedas retiradas é a falsa, e basta mais uma pesagem entre ambas para descobrir qual é a mais leve.
No melhor caso, três pesagens são necessárias, e no pior caso, quatro pesagens.

obs: Uma forma igualmente eficiente de fazer essa divisão é, ao invés de retirar metade de cada grupo por pesagem, retirar uma moeda de cada grupo. É mais simples de executar e para 8 moedas a eficiência é a mesma. Mas para mais moedas, a divisão binária é mais eficiente (ex. 10 moedas no saco).

comentou Abr 16, 2015 por danielcajueiro (5,376 pontos)  
Sua solução é bem interessante e, pelo que entendi, ela é válida quando você não sabe que a moeda falsa é mais leve. Se você usar a informação que a moeda falsa é mais leve, você pode propor duas soluções melhores.
comentou Abr 20, 2015 por Henrique Souza (626 pontos)  
Outra solução demorou pra vir a minha cabeça, mas com 2 pesagens é possível determinar qual é a moeda falsa.
Na primeira pesagem coloco 3 moedas de cada lado. Se a balança se equilibrar, eu sei que a moeda falsa é uma das duas que não foram escolhidas, e basta apenas uma pesagem entre as duas para determinar qual é.
Se a balança se desequilibrar, a moeda falsa está entre o grupo mais leve. Das 3 moedas desse grupo, escolho duas para pesar e verifico o resultado. Se uma for mais leve, a balança irá se desequilibrar e essa será a moeda falsa. Se as duas tiverem o mesmo peso, a terceira moeda que não foi pesada é a moeda falsa.
comentou Abr 20, 2015 por danielcajueiro (5,376 pontos)  
Fantastico! Vc usou toda informação disponível! Essa é a melhor solução que eu conheço!
...