1. Introduction
The author encountered such a question in the algorithm competition at university. Now I will share it with you: There are eight silver coins abcdefgh, and one of them is known to be a counterfeit currency, which is different from the real currency, but I don’t know if it is lighter or heavier. How to use the balance to decide which coin is a counterfeit currency with the minimum number of comparisons, and I also know that the counterfeit currency is lighter or heavier than the real currency.
2. Analysis
If this question is just to solve which counterfeit currency is very simple, the problem is not very complicated, and you only need to go back and recurse to get the result. We need to use the least steps to deal with the difficulties of the problem! ! !
Compared with the previous data structure problems, there are recursion and backtracking. Today we may have to come into contact with a new concept called a tree. As the name suggests, the number structure means that our analysis diagram is like a tree, with various information such as branch nodes. Tree structure is a larger chapter in the data structure, not in our discussion. In this question, we will introduce a small molecule of the tree, the decision tree.
Let’s first build a mathematical model for solving eight silver coins. A simple situation is like this. We name the silver coins abcdefg, etc. in turn, we compare a+b+c and d+e+f. If it is equal, the counterfeit currency must be g or h. We first compare which one is heavier, g or h. If g is heavier, then compare with a (a is the real currency). If g is equal to a, g is the real currency, then h is the fake currency. Since h is lighter than g and g is the real currency, the weight of the counterfeit currency is lighter than the real currency.
What if it is not equal? What's the case? We will compare the branches in turn until we get the final answer!
3. Sample diagram
Based on the above analysis, we can have a complete decision tree diagram:
4. Code
public class Coins { private int[] coins; public Coins() { coins = new int[8]; for(int i = 0; i < 8; i++) coins[i] = 10; } public void setFake(int weight) { coins[(int) (Math.random() * 7)] = weight; } public void fake() { if(coins[0]+coins[1]+coins[2] == coins[3]+coins[4]+coins[5]) { if(coins[6] > coins[7]) compare(6, 7, 0); else compare(7, 6, 0); } else if(coins[0]+coins[1]+coins[2] > coins[3]+coins[4]+coins[5]) { if(coins[0]+coins[3] == coins[1]+coins[4]) compare(2, 5, 0); else if(coins[0]+coins[3] > coins[1]+coins[4]) compare(0, 4, 1); if(coins[0]+coins[3] < coins[1]+coins[4]) compare(1, 3, 0); } else if(coins[0]+coins[1]+coins[2] < coins[3]+coins[4]+coins[5]) { if(coins[0]+coins[3] == coins[1]+coins[4]) compare(5, 2, 0); else if(coins[0]+coins[3] > coins[1]+coins[4]) compare(3, 1, 0); if(coins[0]+coins[3] < coins[1]+coins[4]) compare(4, 0, 1); } } protected void compare(int i, int j, int k) { if(coins[i] > coins[k]) System.out.print("/nFake Coins" + (i+1) + " heavier"); else System.out.print("/n fake currency" + (j+1) + " lighter"); } public static void main(String[] args) { if(args.length == 0) { System.out.println("Input fake currency weight (larger or smaller than 10)"); System.out.println("ex. java Coins 5"); return; } Coins eightCoins = new Coins(); eightCoins.setFake(Integer.parseInt(args[0])); eightCoins.fake(); } }result:
Enter the counterfeit currency weight (larger or smaller than 10)
ex. java Coins 5
Here is a general problem-solving method. You can carefully consider the code. For this code, the above analysis is enough. Everyone needs to think about it and learn the rest by themselves, so that they can understand it deeply.
Summarize
The above is all the content of this article about solving the eight silver coins codes for Java programming implementation. I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!