1. Introduction
L'auteur a rencontré une telle question dans le concours d'algorithme à l'université. Maintenant, je vais le partager avec vous: il y a huit pièces d'argent ABCDEFGH, et l'un d'eux est connu pour être une monnaie contrefaite, qui est différente de la devise réelle, mais je ne sais pas si elle est plus légère ou plus lourde. Comment utiliser l'équilibre pour décider quelle pièce est une monnaie contrefaite avec le nombre minimum de comparaisons, et je sais également que la monnaie contrefaite est plus légère ou plus lourde que la monnaie réelle.
2. Analyse
Si cette question est juste de résoudre quelle monnaie contrefaite est très simple, le problème n'est pas très compliqué, et il vous suffit de revenir en arrière pour obtenir le résultat. Nous devons utiliser le moins d'étapes pour faire face aux difficultés du problème! ! !
Par rapport aux problèmes de structure de données précédents, il y a une récursivité et un retour en arrière. Aujourd'hui, nous devrons peut-être entrer en contact avec un nouveau concept appelé un arbre. Comme son nom l'indique, la structure du nombre signifie que notre diagramme d'analyse est comme un arbre, avec diverses informations telles que les nœuds de branche. La structure des arbres est un chapitre plus large de la structure des données, et non dans notre discussion. Dans cette question, nous présenterons une petite molécule de l'arbre, l'arbre de décision.
Créons d'abord un modèle mathématique pour résoudre huit pièces d'argent. Une situation simple est comme ça. Nous nommons les pièces d'argent ABCDEFG, etc. À notre tour, nous comparons A + B + C et D + E + F. S'il est égal, la monnaie contrefaite doit être g ou h. Nous comparons d'abord lequel est plus lourd, g ou h. Si G est plus lourd, comparez avec A (A est la devise réelle). Si G est égal à A, G est la devise réelle, alors H est la fausse monnaie. Étant donné que H est plus léger que G et G est la monnaie réelle, le poids de la monnaie contrefaite est plus léger que la monnaie réelle.
Et s'il n'est pas égal? Quel est le cas? Nous comparerons les succursales à leur tour jusqu'à ce que nous obtenions la réponse finale!
3. Diagramme d'échantillon
Sur la base de l'analyse ci-dessus, nous pouvons avoir un diagramme d'arbre de décision complet:
4. Code
pièces de classe publique {pièces privées int []; Public Coins () {Coins = new int [8]; pour (int i = 0; i <8; i ++) pièces [i] = 10; } public void setfake (int Weight) {Coins [(int) (math.random () * 7)] = poids; } public void faux () {if (pièces [0] + pièces [1] + pièces [2] == pièces [3] + pièces [4] + pièces [5]) {if (pièces [6]> pièces [7]) comparent (6, 7, 0); Sinon Comparez (7, 6, 0); } else if (pièces [0] + pièces [1] + pièces [2]> pièces [3] + pièces [4] + pièces [5]) {if (pièces [0] + pièces [3] == pièces [1] + pièces [4]) comparent (2, 5, 0); else if (pièces [0] + pièces [3]> pièces [1] + pièces [4]) comparer (0, 4, 1); if (pièces [0] + pièces [3] <pièces [1] + pièces [4]) Comparez (1, 3, 0); } else if (pièces [0] + pièces [1] + pièces [2] <pièces [3] + pièces [4] + pièces [5]) {if (pièces [0] + pièces [3] == pièces [1] + pièces [4]) comparent (5, 2, 0); else if (pièces [0] + pièces [3]> pièces [1] + pièces [4]) comparer (3, 1, 0); if (pièces [0] + pièces [3] <pièces [1] + pièces [4]) comparent (4, 0, 1); }} Protected void compare (int i, int j, int k) {if (coins [i]> coins [k]) System.out.print ("/ nfake coins" + (i + 1) + "lourde"); else System.out.print ("/ n faux devise" + (J + 1) + "Light"); } public static void main (String [] args) {if (args.length == 0) {System.out.println ("Fake de la monnaie d'entrée (plus grand ou inférieur à 10)"); System.out.println ("Ex. Java Coins 5"); retour; } Coins huitcoins = new Coins (); huitcoins.setfake (Integer.ParseInt (args [0])); huitcoins.fake (); }}résultat:
Entrez le poids de la devise contrefait (plus grand ou inférieur à 10)
ex. Java Coins 5
Voici une méthode générale de résolution de problèmes. Vous pouvez soigneusement considérer le code. Pour ce code, l'analyse ci-dessus est suffisante. Tout le monde doit y penser et apprendre le reste par eux-mêmes, afin qu'ils puissent le comprendre profondément.
Résumer
Ce qui précède est tout le contenu de cet article sur la résolution des huit codes de pièces d'argent pour la mise en œuvre de la programmation Java. J'espère que ce sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à d'autres sujets connexes sur ce site. S'il y a des lacunes, veuillez laisser un message pour le signaler. Merci vos amis pour votre soutien pour ce site!