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

时间:2022-09-22 22:20:00

概述

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

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

要求:

  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. }
  18. private static void test1(BigDecimal amount, BigDecimal min, BigDecimal num) {
  19. BigDecimal remain = amount.subtract(min.multiply(num));
  20. final Random random = new Random();
  21. final BigDecimal hundred = new BigDecimal("100");
  22. BigDecimal sum = BigDecimal.ZERO;
  23. BigDecimal redpeck;
  24. for (int i = 0; i < num.intValue(); i++) {
  25. final int nextInt = random.nextInt(100);
  26. if (i == num.intValue() - 1) {
  27. redpeck = remain;
  28. } else {
  29. redpeck = new BigDecimal(nextInt).multiply(remain).divide(hundred, 2, RoundingMode.FLOOR);
  30. }
  31. if (remain.compareTo(redpeck) > 0) {
  32. remain = remain.subtract(redpeck);
  33. } else {
  34. remain = BigDecimal.ZERO;
  35. }
  36. sum = sum.add(min.add(redpeck));
  37. System.out.println("第" + (i + 1) + "个人抢到红包金额为:" + min.add(redpeck));
  38. }
  39. System.out.println("校验每个红包累计额度是否等于红包总额结果:" + (amount.compareTo(sum) == 0));
  40. }

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

  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. }
  18. private static void test2(BigDecimal amount,BigDecimal min ,BigDecimal num){
  19. BigDecimal remain = amount.subtract(min.multiply(num));
  20. final Random random = new Random();
  21. final BigDecimal hundred = new BigDecimal("100");
  22. final BigDecimal two = new BigDecimal("2");
  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.multiply(two).divide(num.subtract(new BigDecimal(i)),2,RoundingMode.CEILING)).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));
  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. 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. }
  18. private static void test3(BigDecimal amount,BigDecimal min ,BigDecimal num){
  19. final Random random = new Random();
  20. final int[] rand = new int[num.intValue()];
  21. BigDecimal sum1 = BigDecimal.ZERO;
  22. BigDecimal redpeck ;
  23. int sum = 0;
  24. for (int i = 0; i < num.intValue(); i++) {
  25. rand[i] = random.nextInt(100);
  26. sum += rand[i];
  27. }
  28. final BigDecimal bigDecimal = new BigDecimal(sum);
  29. BigDecimal remain = amount.subtract(min.multiply(num));
  30. for (int i = 0; i < rand.length; i++) {
  31. if(i == num.intValue() -1){
  32. redpeck = remain;
  33. }else{
  34. redpeck = remain.multiply(new BigDecimal(rand[i])).divide(bigDecimal,2,RoundingMode.FLOOR);
  35. }
  36. if(remain.compareTo(redpeck) > 0){
  37. remain = remain.subtract(redpeck);
  38. }else{
  39. remain = BigDecimal.ZERO;
  40. }
  41. sum1= sum1.add(min.add(redpeck));
  42. System.out.println("第"+(i+1)+"个人抢到红包金额为:"+min.add(redpeck));
  43. }
  44. System.out.println("校验每个红包累计额度是否等于红包总额结果:"+(amount.compareTo(sum1)==0));
  45. }

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

  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. }
  18. private static void test3(BigDecimal amount,BigDecimal min ,BigDecimal num){
  19. final Random random = new Random();
  20. final int[] rand = new int[num.intValue()];
  21. BigDecimal sum1 = BigDecimal.ZERO;
  22. BigDecimal redpeck ;
  23. int sum = 0;
  24. for (int i = 0; i < num.intValue(); i++) {
  25. rand[i] = random.nextInt(100);
  26. sum += rand[i];
  27. }
  28. final BigDecimal bigDecimal = new BigDecimal(sum);
  29. BigDecimal remain = amount.subtract(min.multiply(num));
  30. for (int i = 0; i < rand.length; i++) {
  31. if(i == num.intValue() -1){
  32. redpeck = remain;
  33. }else{
  34. redpeck = remain.multiply(new BigDecimal(rand[i])).divide(bigDecimal,2,RoundingMode.FLOOR);
  35. }
  36. if(remain.compareTo(redpeck) > 0){
  37. remain = remain.subtract(redpeck);
  38. }else{
  39. remain = BigDecimal.ZERO;
  40. }
  41. sum1= sum1.add(min.add(redpeck));
  42. System.out.println("第"+(i+1)+"个人抢到红包金额为:"+min.add(redpeck));
  43. }
  44. System.out.println("校验每个红包累计额度是否等于红包总额结果:"+(amount.compareTo(sum1)==0));
  45. }

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

  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/