“This is the 27th day of my participation in the Gwen Challenge in November. See details of the event: The Last Gwen Challenge in 2021”

Introduction to the

Today, we introduce a very classic method to solve the problem of counterfeit money reduction method, method from the optimization algorithm book.

Problem: counterfeit money problem

Of the n identical looking coins, one is a counterfeit and is known to be lighter. It is possible to compare two groups of coins at will by using a scale to know whether they weigh the same or which group is lighter. The base coin problem requires designing an efficient algorithm to detect the fake coin.

idea

The most natural idea to solve the counterfeit problem is to split the coin in two, which means that you divide n coins into two groups, each group has n/2 coins, and if n is odd, you keep one coin, and then you place the two groups on opposite sides of the scale. If both sets of coins weigh the same, the coin left behind is counterfeit; Otherwise, do the same for the lighter group of coins in the same way, because the counterfeit coins must be in the lighter group.

In the counterfeit coin problem, although we divided the coins into two groups, we only need to solve a problem of half size after comparing with the balance each time, so it belongs to an interstitial subtraction algorithm. In the worst case, the algorithm satisfies the following recursion:

  • T(n) = 0 when n = 1
  • T(n) = T(n/2) + 1 when n is greater than 1

The extended recursion technique is applied to solve this recursion and T(n) = O(log2n) is obtained.

To the problem of counterfeit problem size in half of the algorithm is easy to think of, but in fact, half is not a best choice, consider is not put the COINS into two groups, but is divided into three groups, the former two groups have [3] n/group of COINS, the rest of the COINS as a third group, the former two groups of COINS on the balance, if they are different, the weight of the counterfeit notes must be in the third group, The third group was treated in the same way; If the first two groups differ in weight, the counterfeit coins must be processed in the same way as the lighter coins in the lighter group. Obviously, this algorithm satisfies the following recurrence:

  • T(n) = 0 when n = 1
  • T(n) = T(n/3) + 1 when n is greater than 1

The solution of this recursion is T(n) = O(log3n), dividing the original problem into three to obtain fewer comparisons.

algorithm

Recursive technology is adopted to design the algorithm for counterfeiting problem, and the function Coin is designed to realize the counterfeiting problem. The algorithm is described by pseudo-code as follows:

Coin input: the subscript range of the array where the Coin is located is low and high, the number of the Coin n Output: the serial number of the counterfeit Coin in the Coin set 1. If n is equal to 1, the coin is a counterfeit coin, output the corresponding serial number, and the algorithm ends. 2. Count the number of coins num1, num2, and num3. 3. Add1 = the sum of the weight of the first group of coins; Add2 = the sum of the weight of the second set of coins; 4. Perform one of the following operations as required: 4.1 If ADD1 is greater than ADD2, search for the first group of coins; 4.2 If ADD1 is greater than ADD2, search in the second group of coins; 4.3 If add1 equals add2, look in the third group of coins.Copy the code

remarks

Today is also a day for little leaves to review the exam, time is limited, only preliminary to introduce the problem of counterfeit money, this classic reduction algorithm. I hope I can help you.