1. Introdução
O autor encontrou tal pergunta na competição de algoritmos na universidade. Agora vou compartilhar com você: existem oito moedas de prata abcdefgh, e uma delas é conhecida por ser uma moeda falsificada, que é diferente da moeda real, mas não sei se é mais leve ou mais pesada. Como usar o saldo para decidir qual moeda é uma moeda falsificada com o número mínimo de comparações, e também sei que a moeda falsificada é mais leve ou mais pesada que a moeda real.
2. Análise
Se essa pergunta é apenas para resolver qual moeda falsificada é muito simples, o problema não é muito complicado e você só precisa voltar e voltar para obter o resultado. Precisamos usar as menores etapas para lidar com as dificuldades do problema! ! !
Comparado com os problemas anteriores da estrutura de dados, há recursão e retrocesso. Hoje, podemos ter que entrar em contato com um novo conceito chamado uma árvore. Como o nome sugere, a estrutura numérica significa que nosso diagrama de análise é como uma árvore, com várias informações, como nós de ramificação. A estrutura da árvore é um capítulo maior na estrutura de dados, não em nossa discussão. Nesta pergunta, introduziremos uma pequena molécula da árvore, a árvore de decisão.
Vamos primeiro construir um modelo matemático para resolver oito moedas de prata. Uma situação simples é assim. Nomeamos as moedas de prata abcdefg, etc. Por sua vez, comparamos A+B+C e D+E+F. Se for igual, a moeda falsificada deve ser g ou h. Primeiro comparamos qual é mais pesado, g ou h. Se G for mais pesado, compare com A (A é a moeda real). Se G é igual a A, G é a moeda real, então H é a moeda falsa. Como H é mais leve que G e G é a moeda real, o peso da moeda falsificada é mais leve que a moeda real.
E se não for igual? Qual é o caso? Compararemos as filiais, por sua vez, até obtermos a resposta final!
3. Diagrama de amostra
Com base na análise acima, podemos ter um diagrama de árvore de decisão completa:
4. Código
Public Class Coins {private int [] moedas; public Coins () {Coins = new int [8]; para (int i = 0; i <8; i ++) moedas [i] = 10; } public void setFake (int peso) {moedas [(int) (Math.random () * 7)] = peso; } public void falso () {if (moedas [0]+moedas [1]+moedas [2] == moedas [3]+moedas [4]+moedas [5]) {if (moedas [6]> moedas [7]) Compare (6, 7, 0); caso contrário, compare (7, 6, 0); } else if (moedas [0]+moedas [1]+moedas [2]> moedas [3]+moedas [4]+moedas [5]) {if (moedas [0]+moedas [3] == moedas [1]+moedas [4]) comparam (2, 5, 0); caso contrário, if (moedas [0]+moedas [3]> moedas [1]+moedas [4]) compare (0, 4, 1); if (moedas [0]+moedas [3] <moedas [1]+moedas [4]) Compare (1, 3, 0); } else if (moedas [0]+moedas [1]+moedas [2] <moedas [3]+moedas [4]+moedas [5]) {if (moedas [0]+moedas [3] == moedas [1]+moedas [4]) comparam (5, 2, 0); caso contrário, if (moedas [0]+moedas [3]> moedas [1]+moedas [4]) Compare (3, 1, 0); if (moedas [0]+moedas [3] <moedas [1]+moedas [4]) compare (4, 0, 1); }} void protegido compare (int i, int j, int k) {if (moedas [i]> moedas [k]) System.out.print ("/nfake moedas" + (i + 1) + "mais pesado"); else system.out.print ("/n moeda falsa" + (j + 1) + "mais leve"); } public static void main (string [] args) {if (args.length == 0) {System.out.println ("Entrada Peso da moeda falsa (maior ou menor que 10)"); System.out.println ("Ex. Java Coins 5"); retornar; } Moedas oitocoins = novas moedas (); oitocoins.setFake (Integer.parseint (args [0])); oitocoins.fake (); }}resultado:
Digite o peso da moeda falsificada (maior ou menor que 10)
ex. Java Coins 5
Aqui está um método geral de solução de problemas. Você pode considerar cuidadosamente o código. Para este código, a análise acima é suficiente. Todo mundo precisa pensar sobre isso e aprender o resto sozinho, para que possam entendê -lo profundamente.
Resumir
O exposto acima é todo o conteúdo deste artigo sobre como resolver os oito códigos de moedas de prata para a implementação de programação Java. Espero que seja útil para todos. Amigos interessados podem continuar se referindo a outros tópicos relacionados neste site. Se houver alguma falha, deixe uma mensagem para apontá -la. Obrigado amigos pelo seu apoio para este site!