Shulou(Shulou.com)06/02 Report--

In this issue, the editor will bring you about the realization of Wechat red packet algorithm by Java. The article is rich in content and analyzes and describes it from a professional point of view. I hope you can get something after reading this article.

Overview

After Wechat launched the red packet function 14 years ago, many companies began to use their own red packet function. Up to now, there is still a lot of demand for red packet development, and the implementation of the red packet algorithm is also a common interview question.

Request:

Ensure that each red packet will receive at least 0.01 yuan.

Ensure that the probability of each red packet amount is as balanced as possible.

The cumulative amount of all red packets is listed in the total amount of red packets.

This article provides 4 red packet algorithms and Java code to achieve demo, for reference only. The test scenarios of each algorithm are as follows: 0.1yuan for 10 packets, 1yuan for 10 packets, 100yuan for 10 packets, and 1000 yuan for 10 packets.

I. Random method of residual amount

Take 10 yuan and 10 red packets as an example, after removing the minimum amount of each red packet, the red packet remains 9.9 yuan.

The first red packet is random in the range of [0jue 9.9]. Assuming that it gets 1 yuan at random, the amount of the first red packet is 1.1 yuan, and the remaining 8.9 yuan.

The second red packet is random in the range of [0BI 8.9]. Assuming 1.5 yuan is randomly obtained, the amount of the second red packet is 1.6 yuan and the remaining 7.4 yuan.

The third red packet is random in the range of [0BI 7.4]. Assuming that it gets 0.5 yuan at random, the amount of the third red packet is 0.6 yuan, and the remaining 6.9 yuan.

and so on.

Public static void main (String [] args) {/ / initialize the test scenario BigDecimal [] [] rrr = {{new BigDecimal ("0.1"), new BigDecimal ("10")}, {new BigDecimal ("1"), new BigDecimal ("10")}, {new BigDecimal ("100"), new BigDecimal ("10")}, {new BigDecimal ("1000") New BigDecimal ("10")}} BigDecimal min = new BigDecimal; / / Test scenario for (BigDecimal [] decimals: rrr) {final BigDecimal amount = decimals [0]; final BigDecimal num = decimals [1]; System.out.println (amount + "Yuan" + num + "personal robbery = ="); test1 (amount, min, num) }} private static void test1 (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 ("th" + (I + 1) + "the amount of red packets snatched by individuals is" + min.add (redpeck)) } System.out.println ("check whether the cumulative amount of each red packet is equal to the total amount of red packets" result: + (amount.compareTo (sum) = = 0);}

The test results are as follows: we can see that there are obvious defects in this algorithm, that is, the amount of red packets received first is larger, and then the amount of red packets received is smaller, which makes it unfair to grab red packets.

0.1 yuan for 10 people

The amount of red packet snatched by the first person is 0.01

The second person snatched the amount of red packet: 0.01

The third person snatched the amount of red packet: 0.01

The fourth person snatched the amount of red packet: 0.01

The amount of red packet snatched by the fifth person is: 0.01

The sixth person snatched the red packet with the amount of 0.01.

The seventh person snatched the red packet with the amount of 0.01

The eighth person snatched the red packet with the amount of 0.01.

The amount of red packet snatched by the ninth person is: 0.01

The amount of red packet snatched by the 10th person is: 0.01

Check whether the cumulative amount of each red packet is equal to the total amount of red envelopes. Result: true

1 yuan for 10 people

The amount of red packet snatched by the first person is 0.09

The amount of red packet snatched by the second person is 0.28

The amount of red packet snatched by the third person is 0.19

The amount of red packet snatched by the fourth person is 0.20.

The amount of red packet snatched by the fifth person is 0.15.

The sixth person snatched the amount of red packet: 0.02

The amount of red packet snatched by the seventh person is 0.03

The eighth person snatched the red packet with the amount of 0.01.

The amount of red packet snatched by the ninth person is: 0.01

The amount of the red packet snatched by the 10th person is 0.02

Check whether the cumulative amount of each red packet is equal to the total amount of red envelopes. Result: true

100 yuan for 10 people

The first person who snatched the red packet was 19.99.

The second person snatched the amount of red packet: 29.58

The third person snatched the amount of red packet: 38.27

The fourth person snatched the amount of red packet: 11.85

The amount of red packet snatched by the fifth person is 0.11.

The sixth person snatched the amount of red packet: 0.13

The seventh person snatched the red packet with the amount of 0.01

The eighth person snatched the red packet with the amount of 0.01.

The amount of the red packet snatched by the ninth person is 0.03

The amount of the red packet snatched by the 10th person is 0.02

Check whether the cumulative amount of each red packet is equal to the total amount of red envelopes. Result: true

1000 yuan for 10 people

The amount of red packet snatched by the first person is: 60.00

The second person snatched the red packet with the amount of 695.54

The third person snatched the red packet with the amount of 229.72

The fourth person snatched the amount of red packet: 8.95

The amount of red packet snatched by the fifth person is 0.29.

The sixth person snatched the amount of red packet: 4.64

The seventh person snatched the red packet with the amount of 0.01

The amount of red packet snatched by the eighth person is 0.69

The amount of red packet snatched by the ninth person is 0.12.

The amount of red packet snatched by the 10th person is 0.04.

Check whether the cumulative amount of each red packet is equal to the total amount of red envelopes. Result: true

Second, double mean method (this method is adopted by WeChat red packet)

Or take 10 yuan 10 red packets as an example, after removing the minimum amount of each red packet, the remaining 9.9 yuan, the double mean formula: 2 * remaining amount / number of remaining red packets

The first red packet is random in the range of [0BI 1.98]. Assuming a random score of 1.9, the amount of the first red packet is 2.0 and the remaining 8 yuan.

The second red packet is random in the range of [0Jing 2]. Assuming a random amount of 1 yuan, the amount of the second red packet is 1.1 yuan, and the remaining 7 yuan.

The third red packet is random in the range of [0Jing 2]. Assuming a random amount of 0.5 yuan, the amount of the third red packet is 0.6 yuan, and the remaining 5.5 yuan.

and so on.

Public static void main (String [] args) {/ / initialize the test scenario BigDecimal [] [] rrr = {{new BigDecimal ("0.1"), new BigDecimal ("10")}, {new BigDecimal ("1"), new BigDecimal ("10")}, {new BigDecimal ("100"), new BigDecimal ("10")}, {new BigDecimal ("1000") New BigDecimal ("10")}} BigDecimal min = new BigDecimal; / / Test scenario for (BigDecimal [] decimals: rrr) {final BigDecimal amount = decimals [0]; final BigDecimal num = decimals [1]; System.out.println (amount + "Yuan" + num + "personal robbery = ="); test2 (amount, min, num) }} private static void test2 (BigDecimal amount,BigDecimal min, BigDecimal num) {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);} else {remain = BigDecimal.ZERO;} sum = sum.add (min.add (redpeck)); System.out.println ("1st" + (item1) + "the amount of red packets snatched by individuals is" + min.add (redpeck)) } System.out.println ("check whether the cumulative amount of each red packet is equal to the total amount of red packets. Result:" + amount.compareTo (sum));}

The test results are as follows: this algorithm ensures that the probability of grabbing red packets is roughly equal.

0.1 yuan for 10 people

The amount of red packet snatched by the first person is 0.01

The second person snatched the amount of red packet: 0.01

The third person snatched the amount of red packet: 0.01

The fourth person snatched the amount of red packet: 0.01

The amount of red packet snatched by the fifth person is: 0.01

The sixth person snatched the red packet with the amount of 0.01.

The seventh person snatched the red packet with the amount of 0.01

The eighth person snatched the red packet with the amount of 0.01.

The amount of red packet snatched by the ninth person is: 0.01

The amount of red packet snatched by the 10th person is: 0.01

Check whether the cumulative amount of each red packet is equal to the total amount of red envelopes. Result: true

100 yuan for 10 people

The first person who snatched the red packet was 6.20.

The second person snatched the amount of red packet: 7.09

The third person snatched the amount of red packet: 10.62

The fourth person snatched the amount of red packet: 18.68

The amount of red packet snatched by the fifth person is 18.74.

The sixth person snatched the amount of red packet: 2.32

The seventh person snatched the amount of red packet: 15.44

The eighth person snatched the red packet and the amount was 5.43.

The ninth person snatched the red packet: 15.16

The amount of red packet snatched by the 10th person is 0.32.

Check whether the cumulative amount of each red packet is equal to the total amount of red envelopes. Result: true

1 yuan for 10 people

The amount of red packet snatched by the first person is 0.08

The second person snatched the amount of red packet: 0.05

The amount of red packet snatched by the third person is 0.17

The amount of red packet snatched by the fourth person is 0.17

The amount of red packet snatched by the fifth person is 0.08.

The sixth person snatched the amount of red packet: 0.06

The amount of red packet snatched by the seventh person is 0.18

The amount of red packet snatched by the eighth person is 0.10

The amount of the red packet snatched by the ninth person is 0.02

The amount of red packet snatched by the 10th person is 0.09.

Check whether the cumulative amount of each red packet is equal to the total amount of red envelopes. Result: true

1000 yuan for 10 people

The first person who snatched the red packet was 125.99 yuan.

The second person snatched the red packet with the amount of 165.08

The third person snatched the amount of red packet: 31.90

The fourth person snatched the amount of red packet: 94.78

The fifth person snatched the red packet with the amount of 137.79

The sixth person snatched the amount of red packet: 88.89

The seventh person snatched the red packet with the amount of 156.44.

The amount of red packet snatched by the eighth person is 7.97

The ninth person snatched the red packet and the amount was 151.01.

The amount of red packet snatched by the 10th person is 40.15.

Check whether the cumulative amount of each red packet is equal to the total amount of red envelopes. Result: true

Third, the whole random method

Or take 10 yuan 10 red packets as an example, random 10 numbers, the formula of red packet amount is: total amount of red packets * random number / random number sum, suppose 10 random numbers are [5, 9, 8, 7, 5, 5, 4, 4, 3, 2, 1], and the sum of 10 random numbers is 50.

The first red packet is 10 cents, 5 cents, 50 cents, and 1 yuan.

The second red packet, 10 cents, 9 cents, 50 yuan, is 1.8 yuan.

The third red packet, 10 cents, 8 pounds, 50 yuan, is 1.6 yuan.

and so on.

Public static void main (String [] args) {/ / initialize the test scenario BigDecimal [] [] rrr = {{new BigDecimal ("0.1"), new BigDecimal ("10")}, {new BigDecimal ("1"), new BigDecimal ("10")}, {new BigDecimal ("100"), new BigDecimal ("10")}, {new BigDecimal ("1000") New BigDecimal ("10")}} BigDecimal min = new BigDecimal; / / Test scenario for (BigDecimal [] decimals: rrr) {final BigDecimal amount = decimals [0]; final BigDecimal num = decimals [1]; System.out.println (amount + "Yuan" + num + "personal robbery = ="); test3 (amount, min, num);} private static void test3 (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)); System.out.println ("1st" + (item1) + "the amount of red packets snatched by individuals is" + min.add (redpeck)) } System.out.println ("check whether the cumulative amount of each red packet is equal to the total amount of red packets" result: + (amount.compareTo (sum1) = = 0);}

The test results are as follows: this algorithm is random.

0.1 yuan for 10 people

The amount of red packet snatched by the first person is 0.01

The second person snatched the amount of red packet: 0.01

The third person snatched the amount of red packet: 0.01

The fourth person snatched the amount of red packet: 0.01

The amount of red packet snatched by the fifth person is: 0.01

The sixth person snatched the red packet with the amount of 0.01.

The seventh person snatched the red packet with the amount of 0.01

The eighth person snatched the red packet with the amount of 0.01.

The amount of red packet snatched by the ninth person is: 0.01

The amount of red packet snatched by the 10th person is: 0.01

Check whether the cumulative amount of each red packet is equal to the total amount of red envelopes. Result: true

100 yuan for 10 people

The first person who snatched the red packet was 2.35.

The second person snatched the amount of red packet: 14.12

The third person snatched the amount of red packet: 5.74

The fourth person snatched the amount of red packet: 6.61

The amount of red packet snatched by the fifth person is 0.65.

The sixth person snatched the amount of red packet: 10.97

The seventh person snatched the amount of red packet: 9.15

The amount of red packet snatched by the eighth person is 7.93

The ninth person snatched the red packet and the amount was 1.31.

The amount of red packet snatched by the 10th person is 41.17.

Check whether the cumulative amount of each red packet is equal to the total amount of red envelopes. Result: true

1 yuan for 10 people

The first person who snatched the red packet was 0.10.

The second person snatched the amount of red packet: 0.02

The amount of red packet snatched by the third person is 0.12

The amount of red packet snatched by the fourth person is 0.03

The amount of red packet snatched by the fifth person is 0.05

The sixth person snatched the amount of red packet: 0.12

The amount of red packet snatched by the seventh person is 0.06.

The eighth person snatched the red packet with the amount of 0.01.

The amount of the red packet snatched by the ninth person is 0.04

The amount of red packet snatched by the 10th person is 0.45.

Check whether the cumulative amount of each red packet is equal to the total amount of red envelopes. Result: true

1000 yuan for 10 people

The first person who snatched the red packet was 148.96 yuan.

The second person snatched the red packet with the amount of 116.57

The third person snatched the amount of red packet: 80.49

The fourth person snatched the amount of red packet: 32.48

The fifth person snatched the red packet and the amount was 89.39.

The sixth person snatched the amount of red packet: 65.60

The seventh person snatched the amount of red packet: 20.77

The eighth person snatched the red packet and the amount was 16.03.

The amount of the red packet snatched by the ninth person is 36.79

The 10th person snatched the red packet with the amount of 392.92

Check whether the cumulative amount of each red packet is equal to the total amount of red envelopes. Result: true

4. Secant method

Or take 10 yuan 10 red packets as an example, 9 random intervals greater than or equal to 0.01 in the range of (0Jing 10), assuming that it is [1, 1, 2, 2, 3, 4, 5, 6, 7, 8]

The first red packet gets 1 yuan.

The second red packet is 0.2 yuan.

The third one gets 0.8 yuan.

and so on.

Public static void main (String [] args) {/ / initialize the test scenario BigDecimal [] [] rrr = {{new BigDecimal ("0.1"), new BigDecimal ("10")}, {new BigDecimal ("1"), new BigDecimal ("10")}, {new BigDecimal ("100"), new BigDecimal ("10")}, {new BigDecimal ("1000") New BigDecimal ("10")}} BigDecimal min = new BigDecimal; / / Test scenario for (BigDecimal [] decimals: rrr) {final BigDecimal amount = decimals [0]; final BigDecimal num = decimals [1]; System.out.println (amount + "Yuan" + num + "personal robbery = ="); test3 (amount, min, num);} private static void test3 (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)); System.out.println ("1st" + (item1) + "the amount of red packets snatched by individuals is" + min.add (redpeck)) } System.out.println ("check whether the cumulative amount of each red packet is equal to the total amount of red packets" result: + (amount.compareTo (sum1) = = 0);}

The test results are as follows: this algorithm is random and its performance is not good.

0.1 yuan for 10 people

The amount of red packet snatched by the first person is 0.01

The second person snatched the amount of red packet: 0.01

The third person snatched the amount of red packet: 0.01

The fourth person snatched the amount of red packet: 0.01

The amount of red packet snatched by the fifth person is: 0.01

The sixth person snatched the red packet with the amount of 0.01.

The seventh person snatched the red packet with the amount of 0.01

The eighth person snatched the red packet with the amount of 0.01.

The amount of red packet snatched by the ninth person is: 0.01

The amount of red packet snatched by the 10th person is: 0.01

Check whether the cumulative amount of each red packet is equal to the total amount of red envelopes. Result: true

100 yuan for 10 people

The first person who snatched the red packet was 19.84.

The second person snatched the amount of red packet: 2.73

The third person snatched the amount of red packet: 8.95

The fourth person snatched the amount of red packet: 14.10

The amount of red packet snatched by the fifth person is 18.60

The sixth person snatched the amount of red packet: 3.66

The seventh person snatched the amount of red packet: 9.17

The eighth person snatched the red packet: 15.49

The amount of the red packet snatched by the ninth person is 5.61

The amount of red packet snatched by the 10th person is 1.85

Check whether the cumulative amount of each red packet is equal to the total amount of red envelopes. Result: true

1 yuan for 10 people

The amount of red packet snatched by the first person is 0.02

The amount of red packet snatched by the second person is 0.28

The amount of the red packet snatched by the third person is 0.03

The amount of the red packet snatched by the fourth person is 0.02

The amount of red packet snatched by the fifth person is 0.11.

The sixth person snatched the amount of red packet: 0.23

The amount of red packet snatched by the seventh person is 0.18

The eighth person snatched the red packet and the amount was 0.09.

The amount of the red packet snatched by the ninth person is 0.03

The amount of red packet snatched by the 10th person is: 0.01

Check whether the cumulative amount of each red packet is equal to the total amount of red envelopes. Result: true

1000 yuan for 10 people

The amount of the red packet snatched by the first person is 69.28

The second person snatched the amount of red packet: 14.68

The third person snatched the red packet with the amount of 373.16

The fourth person snatched the red packet with the amount of 274.73

The fifth person snatched the amount of red packet: 30.77

The sixth person snatched the amount of red packet: 30.76

The amount of red packet snatched by the seventh person is 95.55

The amount of red packet snatched by the eighth person is 85.20.

The amount of the red packet snatched by the ninth person is 10.44

The amount of red packet snatched by the 10th person is 15.43

Check whether the cumulative amount of each red packet is equal to the total amount of red envelopes. Result: true

The above is the editor for you to share the Java implementation of Wechat red packet algorithm which, if there happen to be similar doubts, you might as well refer to the above analysis to understand. If you want to know more about it, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.