Java實(shí)現(xiàn)4種微信搶紅包算法(小結(jié))
概述
14年微信推出紅包功能以后,很多公司開始上自己的紅包功能,到現(xiàn)在為止仍然有很多紅包開發(fā)的需求,實(shí)現(xiàn)搶紅包算法也是面試??碱}。
要求:
- 保證每個(gè)紅包最少分得0.01元
- 保證每個(gè)紅包金額概率盡量均衡
- 所有紅包累計(jì)金額登于紅包總金額
本文提供4中紅包算法及Java代碼實(shí)現(xiàn)demo,僅供參考。其中每種算法測試場景為: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) { //初始化測試場景 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"); //測試個(gè)場景 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)); }
測試結(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) { //初始化測試場景 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"); //測試個(gè)場景 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)); }
測試結(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) { //初始化測試場景 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"); //測試個(gè)場景 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)); }
測試結(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) { //初始化測試場景 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"); //測試個(gè)場景 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)); }
測試結(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
到此這篇關(guān)于Java實(shí)現(xiàn)4種微信搶紅包算法(小結(jié))的文章就介紹到這了,更多相關(guān)Java 微信搶紅包 內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
java設(shè)計(jì)模式學(xué)習(xí)之簡單工廠模式
這篇文章主要為大家詳細(xì)介紹了java設(shè)計(jì)模式學(xué)習(xí)之簡單工廠模式,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2017-10-10SpringMVC 中HttpMessageConverter簡介和Http請求415 的問題
本文介紹且記錄如何解決在SpringMVC 中遇到415 Unsupported Media Type 的問題,并且順便介紹Spring MVC的HTTP請求信息轉(zhuǎn)換器HttpMessageConverter2016-07-07JavaWeb項(xiàng)目實(shí)戰(zhàn)之表白墻和在線相冊
這篇文章主要給大家介紹了關(guān)于JavaWeb項(xiàng)目實(shí)戰(zhàn)之表白墻和在線相冊的相關(guān)資料,JavaWeb表白墻是一款基于JavaWeb技術(shù)開發(fā)的表白墻應(yīng)用,用戶可以在上面發(fā)布表白信息,也可以查看其他用戶的表白信息,需要的朋友可以參考下2023-03-03Kafka消費(fèi)客戶端協(xié)調(diào)器GroupCoordinator詳解
這篇文章主要為大家介紹了Kafka消費(fèi)客戶端協(xié)調(diào)器GroupCoordinator使用示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-10-10