PK Creative Spring Festival, I am participating in the “Spring Festival Creative Submission Contest”, please see: Spring Festival Creative Submission Contest”
preface
The essential activity of the Spring Festival is to grab the red envelope, from the previous paper red envelope to the Internet red envelope (headed by wechat red envelope), today we will analyze the algorithm to grab the red envelope, some of which are wechat red envelope algorithm, after reading you will know how to produce the best luck!
Algorithm 1: random residual amount method
Algorithm 1 is not recommended. The full name of algorithm 1 is residual amount random method. It can be seen from the name that this method is to randomly allocate the residual amount.
// The algorithm for allocating red packets
private static void testPocket(BigDecimal amount, BigDecimal min, BigDecimal num) {
BigDecimal remain = amount.subtract(min.multiply(num));
final Random random = new Random();
final BigDecimal hundred = new BigDecimal("100");
BigDecimal sum = BigDecimal.ZERO;
BigDecimal redpeck ;
for (int i = 0; i < num.intValue(); i++) {
final int nextInt = random.nextInt(100);
if (i == num.intValue() - 1) {
redpeck = remain;
} else {
redpeck = new BigDecimal(nextInt).multiply(remain).divide(hundred, 2, RoundingMode.FLOOR);
}
if (remain.compareTo(redpeck) > 0) {
remain = remain.subtract(redpeck);
} else {
remain = BigDecimal.ZERO;
}
sum = sum.add(min.add(redpeck));
System.out.println("The first" + (i + 1) + "The amount of red envelope grabbed by individuals is:" + min.add(redpeck).setScale(2, BigDecimal.ROUND_HALF_UP));
}
System.out.println("Total amount of red envelope:" + sum.setScale(2, BigDecimal.ROUND_HALF_UP));
}
// Test the code
public static void main(String[] args) {
BigDecimal amount = new BigDecimal(100).setScale(2, BigDecimal.ROUND_HALF_UP);
BigDecimal min = new BigDecimal(0.01).setScale(2, BigDecimal.ROUND_HALF_UP);
BigDecimal num = new BigDecimal(10).setScale(2, BigDecimal.ROUND_HALF_UP);
testPocket2(amount,min,num);
}
Copy the code
We can see that this method has obvious defects, that is, at the beginning, the person who gets the red envelope may get the largest amount, and then the amount gets smaller, because he is random from the remaining amount. Obviously wechat is certainly not using this method as a red envelope partition algorithm, otherwise every time there is a red envelope, immediately get it is possible to get the best luck, but obviously not.
Algorithm two: the whole random method
The formula of total amount randomization method is: total amount of red envelopes * Random number/sum of Random numbers. The core of this method is to use a Random number as the standard for dividing red envelopes, which is randomly generated by the Random class. His randomness is relatively large, it looks like it is about the same as we usually grab red envelopes, but wechat red envelopes are not used in this way, because this randomness is too large, not very fair.
private static void testPocket2(BigDecimal amount,BigDecimal min ,BigDecimal num){
final Random random = new Random();
final int[] rand = new int[num.intValue()];
BigDecimal sum1 = BigDecimal.ZERO;
BigDecimal redpeck ;
int sum = 0;
for (int i = 0; i < num.intValue(); i++) {
rand[i] = random.nextInt(100);
sum += rand[i];
}
final BigDecimal bigDecimal = new BigDecimal(sum);
BigDecimal remain = amount.subtract(min.multiply(num));
for (int i = 0; i < rand.length; i++) {
if(i == num.intValue() -1){
redpeck = remain;
}else{
redpeck = remain.multiply(new BigDecimal(rand[i])).divide(bigDecimal,2,RoundingMode.FLOOR);
}
if(remain.compareTo(redpeck) > 0){
remain = remain.subtract(redpeck);
}else{
remain = BigDecimal.ZERO;
}
sum1= sum1.add(min.add(redpeck)).setScale(2, BigDecimal.ROUND_HALF_UP);
System.out.println("The first"+(i+1) +"The amount of red envelope grabbed by individuals is:"+min.add(redpeck).setScale(2, BigDecimal.ROUND_HALF_UP));
}
System.out.println("Total amount of red envelope:"+sum1);
}
// Test the code
public static void main(String[] args) {
BigDecimal amount = new BigDecimal(100).setScale(2, BigDecimal.ROUND_HALF_UP);
BigDecimal min = new BigDecimal(0.01).setScale(2, BigDecimal.ROUND_HALF_UP);
BigDecimal num = new BigDecimal(10).setScale(2, BigDecimal.ROUND_HALF_UP);
testPocket2(amount,min,num);
}
Copy the code
He is highly random and not the best choice.
Algorithm three: secant line method
Secant line method is to imagine the total amount of the red envelope as a long line segment, and the amount of money grabbed by each person is a number of sub-line segments separated from the main line segment. When all the cutting points are determined, the length of the sub-line segment is also determined. In this way, when each person comes to grab a red envelope, they only need to get the red envelope amount equal to the length of the subline.
private static void testPocket3(BigDecimal amount, BigDecimal min, BigDecimal num) {
final Random random = new Random();
final int[] rand = new int[num.intValue()];
BigDecimal sum1 = BigDecimal.ZERO;
BigDecimal redpeck;
int sum = 0;
for (int i = 0; i < num.intValue(); i++) {
rand[i] = random.nextInt(100);
sum += rand[i];
}
final BigDecimal bigDecimal = new BigDecimal(sum);
BigDecimal remain = amount.subtract(min.multiply(num));
for (int i = 0; i < rand.length; i++) {
if (i == num.intValue() - 1) {
redpeck = remain;
} else {
redpeck = remain.multiply(new BigDecimal(rand[i]))
.divide(bigDecimal, 2, RoundingMode.FLOOR);
}
if (remain.compareTo(redpeck) > 0) {
remain = remain.subtract(redpeck).setScale(2, BigDecimal.ROUND_HALF_UP);
} else {
remain = BigDecimal.ZERO;
}
sum1 = sum1.add(min.add(redpeck).setScale(2, BigDecimal.ROUND_HALF_UP));
System.out.println("The first" + (i + 1) + "The amount of red envelope grabbed by individuals is:" + min.add(redpeck));
}
System.out.println("Total amount of red envelope:" + sum1);
}
// Test the code
public static void main(String[] args) {
BigDecimal amount = new BigDecimal(100).setScale(2, BigDecimal.ROUND_HALF_UP);
BigDecimal min = new BigDecimal(0.01).setScale(2, BigDecimal.ROUND_HALF_UP);
BigDecimal num = new BigDecimal(10).setScale(2, BigDecimal.ROUND_HALF_UP);
testPocket2(amount,min,num);
}
Copy the code
He also has a lot of randomness, but his most lethal feature is performance, because he needs to perform the cutting step.
Algorithm four: double mean method
Algorithm 4 is the algorithm currently used in wechat red envelope (general idea, code simulation), the double mean calculation formula: 2 * the remaining amount/the number of remaining red envelope.
BigDecimal remain = amount.subtract(min.multiply(num));
final Random random = new Random();
final BigDecimal hundred = new BigDecimal("100");
final BigDecimal two = new BigDecimal("2");
BigDecimal sum = BigDecimal.ZERO;
BigDecimal redpeck;
for (int i = 0; i < num.intValue(); i++) {
final int nextInt = random.nextInt(100);
if(i == num.intValue() -1){
redpeck = remain;
}else{
redpeck = new BigDecimal(nextInt).multiply(remain.multiply(two).divide(num.subtract(new BigDecimal(i)),2,RoundingMode.CEILING)).divide(hundred,2, RoundingMode.FLOOR);
}
if(remain.compareTo(redpeck) > 0){
remain = remain.subtract(redpeck).setScale(2, BigDecimal.ROUND_HALF_UP);
}else{
remain = BigDecimal.ZERO;
}
sum = sum.add(min.add(redpeck)).setScale(2, BigDecimal.ROUND_HALF_UP);
System.out.println("The first"+(i+1) +"The amount of red envelope grabbed by individuals is:"+min.add(redpeck));
}
System.out.println("Total amount of red envelope:" + sum);
}
Copy the code
He is better to ensure that the amount of each red envelope is roughly the same, there will be no extreme situations.