Java實(shí)現(xiàn)四種微信搶紅包算法,拿走不謝
概述
14年微信推出紅包功能以后,很多公司開始上自己的紅包功能,到現(xiàn)在為止仍然有很多紅包開發(fā)的需求,實(shí)現(xiàn)搶紅包算法也是面試??碱}。
要求:
- 保證每個(gè)紅包最少分得0.01元
- 保證每個(gè)紅包金額概率盡量均衡
- 所有紅包累計(jì)金額等于紅包總金額
本文提供4中紅包算法及Java代碼實(shí)現(xiàn)demo,僅供參考。其中每種算法測(cè)試場(chǎng)景為:0.1元10個(gè)包,1元10個(gè)包,100元10個(gè)包,1000元10個(gè)包。
一、剩余金額隨機(jī)法
以10元10個(gè)紅包為例,去除每個(gè)紅包的最小金額后,紅包剩余9.9元;
- 第一個(gè)紅包在[0,9.9]范圍隨機(jī),假設(shè)隨機(jī)得1元,則第一個(gè)紅包金額為1.1元,紅包剩余8.9元。
- 第二個(gè)紅包在[0,8.9]范圍隨機(jī),假設(shè)隨機(jī)得1.5元,則第二個(gè)紅包金額為1.6元,紅包剩余7.4元。
- 第三個(gè)紅包在[0,7.4]范圍隨機(jī),假設(shè)隨機(jī)得0.5元,則第三個(gè)紅包金額為0.6元,紅包剩余6.9元。
- 以此類推。
- public static void main(String[] args) {
- //初始化測(cè)試場(chǎng)景
- 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("0.01");
- //測(cè)試個(gè)場(chǎng)景
- for (BigDecimal[] decimals : rrr) {
- final BigDecimal amount = decimals[0];
- final BigDecimal num = decimals[1];
- System.out.println(amount + "元" + num + "個(gè)人搶=======================================================");
- 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("第" + (i + 1) + "個(gè)人搶到紅包金額為:" + min.add(redpeck));
- }
- System.out.println("校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果:" + (amount.compareTo(sum) == 0));
- }
測(cè)試結(jié)果如下:可以看出此算法有明顯缺陷,即:先領(lǐng)取的紅包金額較大,后領(lǐng)取的紅包金額較小,這就使得搶紅包變的不公平。
- 0.1元10個(gè)人搶=======================================================
- 第1個(gè)人搶到紅包金額為:0.01
- 第2個(gè)人搶到紅包金額為:0.01
- 第3個(gè)人搶到紅包金額為:0.01
- 第4個(gè)人搶到紅包金額為:0.01
- 第5個(gè)人搶到紅包金額為:0.01
- 第6個(gè)人搶到紅包金額為:0.01
- 第7個(gè)人搶到紅包金額為:0.01
- 第8個(gè)人搶到紅包金額為:0.01
- 第9個(gè)人搶到紅包金額為:0.01
- 第10個(gè)人搶到紅包金額為:0.01
- 校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果:true
- 1元10個(gè)人搶=======================================================
- 第1個(gè)人搶到紅包金額為:0.09
- 第2個(gè)人搶到紅包金額為:0.28
- 第3個(gè)人搶到紅包金額為:0.19
- 第4個(gè)人搶到紅包金額為:0.20
- 第5個(gè)人搶到紅包金額為:0.15
- 第6個(gè)人搶到紅包金額為:0.02
- 第7個(gè)人搶到紅包金額為:0.03
- 第8個(gè)人搶到紅包金額為:0.01
- 第9個(gè)人搶到紅包金額為:0.01
- 第10個(gè)人搶到紅包金額為:0.02
- 校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果:true
- 100元10個(gè)人搶=======================================================
- 第1個(gè)人搶到紅包金額為:19.99
- 第2個(gè)人搶到紅包金額為:29.58
- 第3個(gè)人搶到紅包金額為:38.27
- 第4個(gè)人搶到紅包金額為:11.85
- 第5個(gè)人搶到紅包金額為:0.11
- 第6個(gè)人搶到紅包金額為:0.13
- 第7個(gè)人搶到紅包金額為:0.01
- 第8個(gè)人搶到紅包金額為:0.01
- 第9個(gè)人搶到紅包金額為:0.03
- 第10個(gè)人搶到紅包金額為:0.02
- 校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果:true
- 1000元10個(gè)人搶=======================================================
- 第1個(gè)人搶到紅包金額為:60.00
- 第2個(gè)人搶到紅包金額為:695.54
- 第3個(gè)人搶到紅包金額為:229.72
- 第4個(gè)人搶到紅包金額為:8.95
- 第5個(gè)人搶到紅包金額為:0.29
- 第6個(gè)人搶到紅包金額為:4.64
- 第7個(gè)人搶到紅包金額為:0.01
- 第8個(gè)人搶到紅包金額為:0.69
- 第9個(gè)人搶到紅包金額為:0.12
- 第10個(gè)人搶到紅包金額為:0.04
- 校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果:true
二、二倍均值法(微信紅包采用此法)
還是以10元10個(gè)紅包為例,去除每個(gè)紅包的最小金額后,紅包剩余9.9元,二倍均值計(jì)算公式:2 * 剩余金額/剩余紅包數(shù)
- 第一個(gè)紅包在[0,1.98]范圍隨機(jī),假設(shè)隨機(jī)得1.9,則第一個(gè)紅包金額為2.0,紅包剩余8元。
- 第二個(gè)紅包在[0,2]范圍隨機(jī),假設(shè)隨機(jī)的1元,則第二個(gè)紅包金額為1.1元,紅包剩余7元。
- 第三個(gè)紅包在[0,2]范圍隨機(jī),假設(shè)隨機(jī)的0.5元,則第三個(gè)紅包金額為0.6元,紅包剩余5.5元。
- 以此類推。
- public static void main(String[] args) {
- //初始化測(cè)試場(chǎng)景
- 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("0.01");
- //測(cè)試個(gè)場(chǎng)景
- for (BigDecimal[] decimals : rrr) {
- final BigDecimal amount = decimals[0];
- final BigDecimal num = decimals[1];
- System.out.println(amount + "元" + num + "個(gè)人搶=======================================================");
- 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("第"+(i+1)+"個(gè)人搶到紅包金額為:"+min.add(redpeck));
- }
- System.out.println("校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果:"+amount.compareTo(sum));
- }
測(cè)試結(jié)果如下:此算法很好的保證了搶紅包幾率大致均等。
- 0.1元10個(gè)人搶=======================================================
- 第1個(gè)人搶到紅包金額為:0.01
- 第2個(gè)人搶到紅包金額為:0.01
- 第3個(gè)人搶到紅包金額為:0.01
- 第4個(gè)人搶到紅包金額為:0.01
- 第5個(gè)人搶到紅包金額為:0.01
- 第6個(gè)人搶到紅包金額為:0.01
- 第7個(gè)人搶到紅包金額為:0.01
- 第8個(gè)人搶到紅包金額為:0.01
- 第9個(gè)人搶到紅包金額為:0.01
- 第10個(gè)人搶到紅包金額為:0.01
- 校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果:true
- 100元10個(gè)人搶=======================================================
- 第1個(gè)人搶到紅包金額為:6.20
- 第2個(gè)人搶到紅包金額為:7.09
- 第3個(gè)人搶到紅包金額為:10.62
- 第4個(gè)人搶到紅包金額為:18.68
- 第5個(gè)人搶到紅包金額為:18.74
- 第6個(gè)人搶到紅包金額為:2.32
- 第7個(gè)人搶到紅包金額為:15.44
- 第8個(gè)人搶到紅包金額為:5.43
- 第9個(gè)人搶到紅包金額為:15.16
- 第10個(gè)人搶到紅包金額為:0.32
- 校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果:true
- 1元10個(gè)人搶=======================================================
- 第1個(gè)人搶到紅包金額為:0.08
- 第2個(gè)人搶到紅包金額為:0.05
- 第3個(gè)人搶到紅包金額為:0.17
- 第4個(gè)人搶到紅包金額為:0.17
- 第5個(gè)人搶到紅包金額為:0.08
- 第6個(gè)人搶到紅包金額為:0.06
- 第7個(gè)人搶到紅包金額為:0.18
- 第8個(gè)人搶到紅包金額為:0.10
- 第9個(gè)人搶到紅包金額為:0.02
- 第10個(gè)人搶到紅包金額為:0.09
- 校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果:true
- 1000元10個(gè)人搶=======================================================
- 第1個(gè)人搶到紅包金額為:125.99
- 第2個(gè)人搶到紅包金額為:165.08
- 第3個(gè)人搶到紅包金額為:31.90
- 第4個(gè)人搶到紅包金額為:94.78
- 第5個(gè)人搶到紅包金額為:137.79
- 第6個(gè)人搶到紅包金額為:88.89
- 第7個(gè)人搶到紅包金額為:156.44
- 第8個(gè)人搶到紅包金額為:7.97
- 第9個(gè)人搶到紅包金額為:151.01
- 第10個(gè)人搶到紅包金額為:40.15
- 校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果:true
三、整體隨機(jī)法
還是以10元10個(gè)紅包為例,隨機(jī)10個(gè)數(shù),紅包金額公式為:紅包總額 * 隨機(jī)數(shù)/隨機(jī)數(shù)總和,假設(shè)10個(gè)隨機(jī)數(shù)為[5,9,8,7,6,5,4,3,2,1],10個(gè)隨機(jī)數(shù)總和為50,
- 第一個(gè)紅包10*5/50,得1元。
- 第二個(gè)紅包10*9/50,得1.8元。
- 第三個(gè)紅包10*8/50,得1.6元。
- 以此類推。
- public static void main(String[] args) {
- //初始化測(cè)試場(chǎng)景
- 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("0.01");
- //測(cè)試個(gè)場(chǎng)景
- for (BigDecimal[] decimals : rrr) {
- final BigDecimal amount = decimals[0];
- final BigDecimal num = decimals[1];
- System.out.println(amount + "元" + num + "個(gè)人搶=======================================================");
- 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("第"+(i+1)+"個(gè)人搶到紅包金額為:"+min.add(redpeck));
- }
- System.out.println("校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果:"+(amount.compareTo(sum1)==0));
- }
測(cè)試結(jié)果如下:此算法隨機(jī)性較大。
- 0.1元10個(gè)人搶=======================================================
- 第1個(gè)人搶到紅包金額為:0.01
- 第2個(gè)人搶到紅包金額為:0.01
- 第3個(gè)人搶到紅包金額為:0.01
- 第4個(gè)人搶到紅包金額為:0.01
- 第5個(gè)人搶到紅包金額為:0.01
- 第6個(gè)人搶到紅包金額為:0.01
- 第7個(gè)人搶到紅包金額為:0.01
- 第8個(gè)人搶到紅包金額為:0.01
- 第9個(gè)人搶到紅包金額為:0.01
- 第10個(gè)人搶到紅包金額為:0.01
- 校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果:true
- 100元10個(gè)人搶=======================================================
- 第1個(gè)人搶到紅包金額為:2.35
- 第2個(gè)人搶到紅包金額為:14.12
- 第3個(gè)人搶到紅包金額為:5.74
- 第4個(gè)人搶到紅包金額為:6.61
- 第5個(gè)人搶到紅包金額為:0.65
- 第6個(gè)人搶到紅包金額為:10.97
- 第7個(gè)人搶到紅包金額為:9.15
- 第8個(gè)人搶到紅包金額為:7.93
- 第9個(gè)人搶到紅包金額為:1.31
- 第10個(gè)人搶到紅包金額為:41.17
- 校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果:true
- 1元10個(gè)人搶=======================================================
- 第1個(gè)人搶到紅包金額為:0.10
- 第2個(gè)人搶到紅包金額為:0.02
- 第3個(gè)人搶到紅包金額為:0.12
- 第4個(gè)人搶到紅包金額為:0.03
- 第5個(gè)人搶到紅包金額為:0.05
- 第6個(gè)人搶到紅包金額為:0.12
- 第7個(gè)人搶到紅包金額為:0.06
- 第8個(gè)人搶到紅包金額為:0.01
- 第9個(gè)人搶到紅包金額為:0.04
- 第10個(gè)人搶到紅包金額為:0.45
- 校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果:true
- 1000元10個(gè)人搶=======================================================
- 第1個(gè)人搶到紅包金額為:148.96
- 第2個(gè)人搶到紅包金額為:116.57
- 第3個(gè)人搶到紅包金額為:80.49
- 第4個(gè)人搶到紅包金額為:32.48
- 第5個(gè)人搶到紅包金額為:89.39
- 第6個(gè)人搶到紅包金額為:65.60
- 第7個(gè)人搶到紅包金額為:20.77
- 第8個(gè)人搶到紅包金額為:16.03
- 第9個(gè)人搶到紅包金額為:36.79
- 第10個(gè)人搶到紅包金額為:392.92
- 校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果:true
四、割線法
還是以10元10個(gè)紅包為例,在(0,10)范圍隨機(jī)9個(gè)間隔大于等于0.01數(shù),假設(shè)為[1,1.2,2,3,4,5,6,7,8]
- 第一個(gè)紅包得1元
- 第二個(gè)紅包得0.2元
- 第三個(gè)紅得0.8元。
- 以此類推。
- public static void main(String[] args) {
- //初始化測(cè)試場(chǎng)景
- 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("0.01");
- //測(cè)試個(gè)場(chǎng)景
- for (BigDecimal[] decimals : rrr) {
- final BigDecimal amount = decimals[0];
- final BigDecimal num = decimals[1];
- System.out.println(amount + "元" + num + "個(gè)人搶=======================================================");
- 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("第"+(i+1)+"個(gè)人搶到紅包金額為:"+min.add(redpeck));
- }
- System.out.println("校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果:"+(amount.compareTo(sum1)==0));
- }
測(cè)試結(jié)果如下:此算法隨機(jī)性較大,且性能不好。
- 0.1元10個(gè)人搶=======================================================
- 第1個(gè)人搶到紅包金額為:0.01
- 第2個(gè)人搶到紅包金額為:0.01
- 第3個(gè)人搶到紅包金額為:0.01
- 第4個(gè)人搶到紅包金額為:0.01
- 第5個(gè)人搶到紅包金額為:0.01
- 第6個(gè)人搶到紅包金額為:0.01
- 第7個(gè)人搶到紅包金額為:0.01
- 第8個(gè)人搶到紅包金額為:0.01
- 第9個(gè)人搶到紅包金額為:0.01
- 第10個(gè)人搶到紅包金額為:0.01
- 校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果:true
- 100元10個(gè)人搶=======================================================
- 第1個(gè)人搶到紅包金額為:19.84
- 第2個(gè)人搶到紅包金額為:2.73
- 第3個(gè)人搶到紅包金額為:8.95
- 第4個(gè)人搶到紅包金額為:14.10
- 第5個(gè)人搶到紅包金額為:18.60
- 第6個(gè)人搶到紅包金額為:3.66
- 第7個(gè)人搶到紅包金額為:9.17
- 第8個(gè)人搶到紅包金額為:15.49
- 第9個(gè)人搶到紅包金額為:5.61
- 第10個(gè)人搶到紅包金額為:1.85
- 校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果:true
- 1元10個(gè)人搶=======================================================
- 第1個(gè)人搶到紅包金額為:0.02
- 第2個(gè)人搶到紅包金額為:0.28
- 第3個(gè)人搶到紅包金額為:0.03
- 第4個(gè)人搶到紅包金額為:0.02
- 第5個(gè)人搶到紅包金額為:0.11
- 第6個(gè)人搶到紅包金額為:0.23
- 第7個(gè)人搶到紅包金額為:0.18
- 第8個(gè)人搶到紅包金額為:0.09
- 第9個(gè)人搶到紅包金額為:0.03
- 第10個(gè)人搶到紅包金額為:0.01
- 校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果:true
- 1000元10個(gè)人搶=======================================================
- 第1個(gè)人搶到紅包金額為:69.28
- 第2個(gè)人搶到紅包金額為:14.68
- 第3個(gè)人搶到紅包金額為:373.16
- 第4個(gè)人搶到紅包金額為:274.73
- 第5個(gè)人搶到紅包金額為:30.77
- 第6個(gè)人搶到紅包金額為:30.76
- 第7個(gè)人搶到紅包金額為:95.55
- 第8個(gè)人搶到紅包金額為:85.20
- 第9個(gè)人搶到紅包金額為:10.44
- 第10個(gè)人搶到紅包金額為:15.43
- 校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果:true