Java实现四种微信抢红包算法，拿走不谢

概述

14年微信推出红包功能以后，很多公司开始上自己的红包功能，到现在为止仍然有很多红包开发的需求，实现抢红包算法也是面试常考题。

要求：

1. 保证每个红包最少分得0.01元
2. 保证每个红包金额概率尽量均衡
3. 所有红包累计金额等于红包总金额

本文提供4中红包算法及Java代码实现demo，仅供参考。其中每种算法测试场景为：0.1元10个包，1元10个包，100元10个包，1000元10个包。

一、剩余金额随机法

以10元10个红包为例，去除每个红包的最小金额后，红包剩余9.9元;

1. 第一个红包在[0,9.9]范围随机，假设随机得1元，则第一个红包金额为1.1元，红包剩余8.9元。
2. 第二个红包在[0,8.9]范围随机，假设随机得1.5元，则第二个红包金额为1.6元，红包剩余7.4元。
3. 第三个红包在[0,7.4]范围随机，假设随机得0.5元，则第三个红包金额为0.6元，红包剩余6.9元。
4. 以此类推。

1. public static void main(String[] args) {
2. //初始化测试场景
3. BigDecimal[][] rrr = {
4. {new BigDecimal("0.1"), new BigDecimal("10")},
5. {new BigDecimal("1"), new BigDecimal("10")},
6. {new BigDecimal("100"), new BigDecimal("10")},
7. {new BigDecimal("1000"), new BigDecimal("10")}
8. };
9. BigDecimal min = new BigDecimal("0.01");
10. //测试个场景
11. for (BigDecimal[] decimals : rrr) {
12. final BigDecimal amount = decimals[0];
13. final BigDecimal num = decimals[1];
14. System.out.println(amount + "元" + num + "个人抢=======================================================");
15. test1(amount, min, num);
16. }
17. }
19. private static void test1(BigDecimal amount, BigDecimal min, BigDecimal num) {
20. BigDecimal remain = amount.subtract(min.multiply(num));
21. final Random random = new Random();
22. final BigDecimal hundred = new BigDecimal("100");
23. BigDecimal sum = BigDecimal.ZERO;
24. BigDecimal redpeck;
25. for (int i = 0; i < num.intValue(); i++) {
26. final int nextInt = random.nextInt(100);
27. if (i == num.intValue() - 1) {
28. redpeck = remain;
29. } else {
30. redpeck = new BigDecimal(nextInt).multiply(remain).divide(hundred, 2, RoundingMode.FLOOR);
31. }
32. if (remain.compareTo(redpeck) > 0) {
33. remain = remain.subtract(redpeck);
34. } else {
35. remain = BigDecimal.ZERO;
36. }
37. sum = sum.add(min.add(redpeck));
38. System.out.println("第" + (i + 1) + "个人抢到红包金额为：" + min.add(redpeck));
39. }
40. System.out.println("校验每个红包累计额度是否等于红包总额结果：" + (amount.compareTo(sum) == 0));
41. }

测试结果如下:可以看出此算法有明显缺陷，即：先领取的红包金额较大，后领取的红包金额较小，这就使得抢红包变的不公平。

1. 0.1元10个人抢=======================================================
2. 第1个人抢到红包金额为：0.01
3. 第2个人抢到红包金额为：0.01
4. 第3个人抢到红包金额为：0.01
5. 第4个人抢到红包金额为：0.01
6. 第5个人抢到红包金额为：0.01
7. 第6个人抢到红包金额为：0.01
8. 第7个人抢到红包金额为：0.01
9. 第8个人抢到红包金额为：0.01
10. 第9个人抢到红包金额为：0.01
11. 第10个人抢到红包金额为：0.01
12. 校验每个红包累计额度是否等于红包总额结果：true
13. 1元10个人抢=======================================================
14. 第1个人抢到红包金额为：0.09
15. 第2个人抢到红包金额为：0.28
16. 第3个人抢到红包金额为：0.19
17. 第4个人抢到红包金额为：0.20
18. 第5个人抢到红包金额为：0.15
19. 第6个人抢到红包金额为：0.02
20. 第7个人抢到红包金额为：0.03
21. 第8个人抢到红包金额为：0.01
22. 第9个人抢到红包金额为：0.01
23. 第10个人抢到红包金额为：0.02
24. 校验每个红包累计额度是否等于红包总额结果：true
25. 100元10个人抢=======================================================
26. 第1个人抢到红包金额为：19.99
27. 第2个人抢到红包金额为：29.58
28. 第3个人抢到红包金额为：38.27
29. 第4个人抢到红包金额为：11.85
30. 第5个人抢到红包金额为：0.11
31. 第6个人抢到红包金额为：0.13
32. 第7个人抢到红包金额为：0.01
33. 第8个人抢到红包金额为：0.01
34. 第9个人抢到红包金额为：0.03
35. 第10个人抢到红包金额为：0.02
36. 校验每个红包累计额度是否等于红包总额结果：true
37. 1000元10个人抢=======================================================
38. 第1个人抢到红包金额为：60.00
39. 第2个人抢到红包金额为：695.54
40. 第3个人抢到红包金额为：229.72
41. 第4个人抢到红包金额为：8.95
42. 第5个人抢到红包金额为：0.29
43. 第6个人抢到红包金额为：4.64
44. 第7个人抢到红包金额为：0.01
45. 第8个人抢到红包金额为：0.69
46. 第9个人抢到红包金额为：0.12
47. 第10个人抢到红包金额为：0.04
48. 校验每个红包累计额度是否等于红包总额结果：true

二、二倍均值法(微信红包采用此法)

还是以10元10个红包为例，去除每个红包的最小金额后，红包剩余9.9元，二倍均值计算公式：2 * 剩余金额/剩余红包数

1. 第一个红包在[0,1.98]范围随机，假设随机得1.9，则第一个红包金额为2.0，红包剩余8元。
2. 第二个红包在[0,2]范围随机，假设随机的1元，则第二个红包金额为1.1元，红包剩余7元。
3. 第三个红包在[0,2]范围随机，假设随机的0.5元，则第三个红包金额为0.6元，红包剩余5.5元。
4. 以此类推。

1. public static void main(String[] args) {
2. //初始化测试场景
3. BigDecimal[][] rrr = {
4. {new BigDecimal("0.1"), new BigDecimal("10")},
5. {new BigDecimal("1"), new BigDecimal("10")},
6. {new BigDecimal("100"), new BigDecimal("10")},
7. {new BigDecimal("1000"), new BigDecimal("10")}
8. };
9. BigDecimal min = new BigDecimal("0.01");
10. //测试个场景
11. for (BigDecimal[] decimals : rrr) {
12. final BigDecimal amount = decimals[0];
13. final BigDecimal num = decimals[1];
14. System.out.println(amount + "元" + num + "个人抢=======================================================");
15. test2(amount, min, num);
16. }
17. }
20. private static void test2(BigDecimal amount,BigDecimal min ,BigDecimal num){
21. BigDecimal remain = amount.subtract(min.multiply(num));
22. final Random random = new Random();
23. final BigDecimal hundred = new BigDecimal("100");
24. final BigDecimal two = new BigDecimal("2");
25. BigDecimal sum = BigDecimal.ZERO;
26. BigDecimal redpeck;
27. for (int i = 0; i < num.intValue(); i++) {
28. final int nextInt = random.nextInt(100);
29. if(i == num.intValue() -1){
30. redpeck = remain;
31. }else{
32. redpeck = new BigDecimal(nextInt).multiply(remain.multiply(two).divide(num.subtract(new BigDecimal(i)),2,RoundingMode.CEILING)).divide(hundred,2, RoundingMode.FLOOR);
33. }
34. if(remain.compareTo(redpeck) > 0){
35. remain = remain.subtract(redpeck);
36. }else{
37. remain = BigDecimal.ZERO;
38. }
39. sum = sum.add(min.add(redpeck));
40. System.out.println("第"+(i+1)+"个人抢到红包金额为："+min.add(redpeck));
41. }
42. System.out.println("校验每个红包累计额度是否等于红包总额结果："+amount.compareTo(sum));
43. }

测试结果如下:此算法很好的保证了抢红包几率大致均等。

1. 0.1元10个人抢=======================================================
2. 第1个人抢到红包金额为：0.01
3. 第2个人抢到红包金额为：0.01
4. 第3个人抢到红包金额为：0.01
5. 第4个人抢到红包金额为：0.01
6. 第5个人抢到红包金额为：0.01
7. 第6个人抢到红包金额为：0.01
8. 第7个人抢到红包金额为：0.01
9. 第8个人抢到红包金额为：0.01
10. 第9个人抢到红包金额为：0.01
11. 第10个人抢到红包金额为：0.01
12. 校验每个红包累计额度是否等于红包总额结果：true
13. 100元10个人抢=======================================================
14. 第1个人抢到红包金额为：6.20
15. 第2个人抢到红包金额为：7.09
16. 第3个人抢到红包金额为：10.62
17. 第4个人抢到红包金额为：18.68
18. 第5个人抢到红包金额为：18.74
19. 第6个人抢到红包金额为：2.32
20. 第7个人抢到红包金额为：15.44
21. 第8个人抢到红包金额为：5.43
22. 第9个人抢到红包金额为：15.16
23. 第10个人抢到红包金额为：0.32
24. 校验每个红包累计额度是否等于红包总额结果：true
25. 1元10个人抢=======================================================
26. 第1个人抢到红包金额为：0.08
27. 第2个人抢到红包金额为：0.05
28. 第3个人抢到红包金额为：0.17
29. 第4个人抢到红包金额为：0.17
30. 第5个人抢到红包金额为：0.08
31. 第6个人抢到红包金额为：0.06
32. 第7个人抢到红包金额为：0.18
33. 第8个人抢到红包金额为：0.10
34. 第9个人抢到红包金额为：0.02
35. 第10个人抢到红包金额为：0.09
36. 校验每个红包累计额度是否等于红包总额结果：true
37. 1000元10个人抢=======================================================
38. 第1个人抢到红包金额为：125.99
39. 第2个人抢到红包金额为：165.08
40. 第3个人抢到红包金额为：31.90
41. 第4个人抢到红包金额为：94.78
42. 第5个人抢到红包金额为：137.79
43. 第6个人抢到红包金额为：88.89
44. 第7个人抢到红包金额为：156.44
45. 第8个人抢到红包金额为：7.97
46. 第9个人抢到红包金额为：151.01
47. 第10个人抢到红包金额为：40.15
48. 校验每个红包累计额度是否等于红包总额结果：true

三、整体随机法

还是以10元10个红包为例，随机10个数，红包金额公式为：红包总额 * 随机数/随机数总和，假设10个随机数为[5,9,8,7,6,5,4,3,2,1],10个随机数总和为50，

1. 第一个红包10*5/50，得1元。
2. 第二个红包10*9/50，得1.8元。
3. 第三个红包10*8/50，得1.6元。
4. 以此类推。

1. public static void main(String[] args) {
2. //初始化测试场景
3. BigDecimal[][] rrr = {
4. {new BigDecimal("0.1"), new BigDecimal("10")},
5. {new BigDecimal("1"), new BigDecimal("10")},
6. {new BigDecimal("100"), new BigDecimal("10")},
7. {new BigDecimal("1000"), new BigDecimal("10")}
8. };
9. BigDecimal min = new BigDecimal("0.01");
10. //测试个场景
11. for (BigDecimal[] decimals : rrr) {
12. final BigDecimal amount = decimals[0];
13. final BigDecimal num = decimals[1];
14. System.out.println(amount + "元" + num + "个人抢=======================================================");
15. test3(amount, min, num);
16. }
17. }
19. private static void test3(BigDecimal amount,BigDecimal min ,BigDecimal num){
20. final Random random = new Random();
21. final int[] rand = new int[num.intValue()];
22. BigDecimal sum1 = BigDecimal.ZERO;
23. BigDecimal redpeck ;
24. int sum = 0;
25. for (int i = 0; i < num.intValue(); i++) {
26. rand[i] = random.nextInt(100);
27. sum += rand[i];
28. }
29. final BigDecimal bigDecimal = new BigDecimal(sum);
30. BigDecimal remain = amount.subtract(min.multiply(num));
31. for (int i = 0; i < rand.length; i++) {
32. if(i == num.intValue() -1){
33. redpeck = remain;
34. }else{
35. redpeck = remain.multiply(new BigDecimal(rand[i])).divide(bigDecimal,2,RoundingMode.FLOOR);
36. }
37. if(remain.compareTo(redpeck) > 0){
38. remain = remain.subtract(redpeck);
39. }else{
40. remain = BigDecimal.ZERO;
41. }
42. sum1= sum1.add(min.add(redpeck));
43. System.out.println("第"+(i+1)+"个人抢到红包金额为："+min.add(redpeck));
44. }
46. System.out.println("校验每个红包累计额度是否等于红包总额结果："+(amount.compareTo(sum1)==0));
47. }

测试结果如下:此算法随机性较大。

1. 0.1元10个人抢=======================================================
2. 第1个人抢到红包金额为：0.01
3. 第2个人抢到红包金额为：0.01
4. 第3个人抢到红包金额为：0.01
5. 第4个人抢到红包金额为：0.01
6. 第5个人抢到红包金额为：0.01
7. 第6个人抢到红包金额为：0.01
8. 第7个人抢到红包金额为：0.01
9. 第8个人抢到红包金额为：0.01
10. 第9个人抢到红包金额为：0.01
11. 第10个人抢到红包金额为：0.01
12. 校验每个红包累计额度是否等于红包总额结果：true
13. 100元10个人抢=======================================================
14. 第1个人抢到红包金额为：2.35
15. 第2个人抢到红包金额为：14.12
16. 第3个人抢到红包金额为：5.74
17. 第4个人抢到红包金额为：6.61
18. 第5个人抢到红包金额为：0.65
19. 第6个人抢到红包金额为：10.97
20. 第7个人抢到红包金额为：9.15
21. 第8个人抢到红包金额为：7.93
22. 第9个人抢到红包金额为：1.31
23. 第10个人抢到红包金额为：41.17
24. 校验每个红包累计额度是否等于红包总额结果：true
25. 1元10个人抢=======================================================
26. 第1个人抢到红包金额为：0.10
27. 第2个人抢到红包金额为：0.02
28. 第3个人抢到红包金额为：0.12
29. 第4个人抢到红包金额为：0.03
30. 第5个人抢到红包金额为：0.05
31. 第6个人抢到红包金额为：0.12
32. 第7个人抢到红包金额为：0.06
33. 第8个人抢到红包金额为：0.01
34. 第9个人抢到红包金额为：0.04
35. 第10个人抢到红包金额为：0.45
36. 校验每个红包累计额度是否等于红包总额结果：true
37. 1000元10个人抢=======================================================
38. 第1个人抢到红包金额为：148.96
39. 第2个人抢到红包金额为：116.57
40. 第3个人抢到红包金额为：80.49
41. 第4个人抢到红包金额为：32.48
42. 第5个人抢到红包金额为：89.39
43. 第6个人抢到红包金额为：65.60
44. 第7个人抢到红包金额为：20.77
45. 第8个人抢到红包金额为：16.03
46. 第9个人抢到红包金额为：36.79
47. 第10个人抢到红包金额为：392.92
48. 校验每个红包累计额度是否等于红包总额结果：true

四、割线法

还是以10元10个红包为例，在(0,10)范围随机9个间隔大于等于0.01数，假设为[1,1.2,2,3,4,5,6,7,8]

1. 第一个红包得1元
2. 第二个红包得0.2元
3. 第三个红得0.8元。
4. 以此类推。

1. public static void main(String[] args) {
2. //初始化测试场景
3. BigDecimal[][] rrr = {
4. {new BigDecimal("0.1"), new BigDecimal("10")},
5. {new BigDecimal("1"), new BigDecimal("10")},
6. {new BigDecimal("100"), new BigDecimal("10")},
7. {new BigDecimal("1000"), new BigDecimal("10")}
8. };
9. BigDecimal min = new BigDecimal("0.01");
10. //测试个场景
11. for (BigDecimal[] decimals : rrr) {
12. final BigDecimal amount = decimals[0];
13. final BigDecimal num = decimals[1];
14. System.out.println(amount + "元" + num + "个人抢=======================================================");
15. test3(amount, min, num);
16. }
17. }
19. private static void test3(BigDecimal amount,BigDecimal min ,BigDecimal num){
20. final Random random = new Random();
21. final int[] rand = new int[num.intValue()];
22. BigDecimal sum1 = BigDecimal.ZERO;
23. BigDecimal redpeck ;
24. int sum = 0;
25. for (int i = 0; i < num.intValue(); i++) {
26. rand[i] = random.nextInt(100);
27. sum += rand[i];
28. }
29. final BigDecimal bigDecimal = new BigDecimal(sum);
30. BigDecimal remain = amount.subtract(min.multiply(num));
31. for (int i = 0; i < rand.length; i++) {
32. if(i == num.intValue() -1){
33. redpeck = remain;
34. }else{
35. redpeck = remain.multiply(new BigDecimal(rand[i])).divide(bigDecimal,2,RoundingMode.FLOOR);
36. }
37. if(remain.compareTo(redpeck) > 0){
38. remain = remain.subtract(redpeck);
39. }else{
40. remain = BigDecimal.ZERO;
41. }
42. sum1= sum1.add(min.add(redpeck));
43. System.out.println("第"+(i+1)+"个人抢到红包金额为："+min.add(redpeck));
44. }
46. System.out.println("校验每个红包累计额度是否等于红包总额结果："+(amount.compareTo(sum1)==0));
47. }

测试结果如下:此算法随机性较大，且性能不好。

1. 0.1元10个人抢=======================================================
2. 第1个人抢到红包金额为：0.01
3. 第2个人抢到红包金额为：0.01
4. 第3个人抢到红包金额为：0.01
5. 第4个人抢到红包金额为：0.01
6. 第5个人抢到红包金额为：0.01
7. 第6个人抢到红包金额为：0.01
8. 第7个人抢到红包金额为：0.01
9. 第8个人抢到红包金额为：0.01
10. 第9个人抢到红包金额为：0.01
11. 第10个人抢到红包金额为：0.01
12. 校验每个红包累计额度是否等于红包总额结果：true
13. 100元10个人抢=======================================================
14. 第1个人抢到红包金额为：19.84
15. 第2个人抢到红包金额为：2.73
16. 第3个人抢到红包金额为：8.95
17. 第4个人抢到红包金额为：14.10
18. 第5个人抢到红包金额为：18.60
19. 第6个人抢到红包金额为：3.66
20. 第7个人抢到红包金额为：9.17
21. 第8个人抢到红包金额为：15.49
22. 第9个人抢到红包金额为：5.61
23. 第10个人抢到红包金额为：1.85
24. 校验每个红包累计额度是否等于红包总额结果：true
25. 1元10个人抢=======================================================
26. 第1个人抢到红包金额为：0.02
27. 第2个人抢到红包金额为：0.28
28. 第3个人抢到红包金额为：0.03
29. 第4个人抢到红包金额为：0.02
30. 第5个人抢到红包金额为：0.11
31. 第6个人抢到红包金额为：0.23
32. 第7个人抢到红包金额为：0.18
33. 第8个人抢到红包金额为：0.09
34. 第9个人抢到红包金额为：0.03
35. 第10个人抢到红包金额为：0.01
36. 校验每个红包累计额度是否等于红包总额结果：true
37. 1000元10个人抢=======================================================
38. 第1个人抢到红包金额为：69.28
39. 第2个人抢到红包金额为：14.68
40. 第3个人抢到红包金额为：373.16
41. 第4个人抢到红包金额为：274.73
42. 第5个人抢到红包金额为：30.77
43. 第6个人抢到红包金额为：30.76
44. 第7个人抢到红包金额为：95.55
45. 第8个人抢到红包金额为：85.20
46. 第9个人抢到红包金额为：10.44
47. 第10个人抢到红包金额为：15.43
48. 校验每个红包累计额度是否等于红包总额结果：true

原文链接：https://www.toutiao.com/a7031002228831896075/