Java programming to solve the code sharing of eight silver coins

1. Introduction

The author encountered such a problem in the algorithm competition in the University. Now I take it out and share with you: there are eight silver coins abcdefgh. It is known that one of them is a counterfeit coin and its weight is different from the real coin, but I don't know whether it is lighter or heavier. How to use the balance to determine which is a counterfeit coin with the least number of comparisons, and know that the counterfeit coin is lighter or heavier than the real coin.

2. Analysis

If this problem is only a very simple solution to which counterfeit money is, the problem is not very complex. We can get the result only by backtracking and recursion. The difficulty of the problem, we need to use the least steps!!!

Compared with the previous data structure problems, there are recursion and backtracking. Today we may touch on a new concept called tree. As the name suggests, the number structure means that our analysis diagram is like a tree with branch nodes and other information. Tree structure is a large chapter in data structure, which is not in our discussion. In this topic, we will introduce a small molecule of tree, decision tree.

Let's first establish a mathematical model for solving eight silver coins. A simple situation is that we name the silver coins ABCDEFG, etc. we compare a + B + C and D + e + F. if they are equal, the counterfeit currency must be g or h. We first compare g or h which is heavier, if G is heavier, and then compare with a (a is the real currency). If G is equal to a, G is the real currency, then h is the counterfeit currency. Because h is lighter than g and G is the real currency, the weight of H counterfeit currency is lighter than the real currency.

What if they are not equal? In what case, we will branch back and compare in turn until we get the final answer!

3. Example diagram

According to the above analysis, we can have a complete decision tree diagram:

4. Code

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 ponder the code. For this code, the above analysis is enough. The rest needs to be pondered and studied by yourself, so that you can deeply understand it.

summary

The above is all about Java programming code sharing for solving eight silver coins. I hope it will be helpful to you. Interested friends can continue to refer to other related topics on this site. If there are deficiencies, please leave a message to point out. Thank you for your support!