浅沫记忆 发表于 2021-11-27 11:13:37

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

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

要求:

[*]保证每个红包最少分得0.01元
[*]保证每个红包金额概率尽量均衡
[*]所有红包累计金额等于红包总金额
本文提供4中红包算法及Java代码实现demo,仅供参考。其中每种算法测试场景为:0.1元10个包,1元10个包,100元10个包,1000元10个包。
一、剩余金额随机法
以10元10个红包为例,去除每个红包的最小金额后,红包剩余9.9元;

[*]第一个红包在范围随机,假设随机得1元,则第一个红包金额为1.1元,红包剩余8.9元。
[*]第二个红包在范围随机,假设随机得1.5元,则第二个红包金额为1.6元,红包剩余7.4元。
[*]第三个红包在范围随机,假设随机得0.5元,则第三个红包金额为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");

//测试个场景

for (BigDecimal[] decimals : rrr) {

final BigDecimal amount = decimals;

final BigDecimal num = decimals;

System.out.println(amount + "元" + num + "个人抢=======================================================");

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) + "个人抢到红包金额为:" + min.add(redpeck));

}

System.out.println("校验每个红包累计额度是否等于红包总额结果:" + (amount.compareTo(sum) == 0));

}

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

第1个人抢到红包金额为:0.01

第2个人抢到红包金额为:0.01

第3个人抢到红包金额为:0.01

第4个人抢到红包金额为:0.01

第5个人抢到红包金额为:0.01

第6个人抢到红包金额为:0.01

第7个人抢到红包金额为:0.01

第8个人抢到红包金额为:0.01

第9个人抢到红包金额为:0.01

第10个人抢到红包金额为:0.01

校验每个红包累计额度是否等于红包总额结果:true

1元10个人抢=======================================================

第1个人抢到红包金额为:0.09

第2个人抢到红包金额为:0.28

第3个人抢到红包金额为:0.19

第4个人抢到红包金额为:0.20

第5个人抢到红包金额为:0.15

第6个人抢到红包金额为:0.02

第7个人抢到红包金额为:0.03

第8个人抢到红包金额为:0.01

第9个人抢到红包金额为:0.01

第10个人抢到红包金额为:0.02

校验每个红包累计额度是否等于红包总额结果:true

100元10个人抢=======================================================

第1个人抢到红包金额为:19.99

第2个人抢到红包金额为:29.58

第3个人抢到红包金额为:38.27

第4个人抢到红包金额为:11.85

第5个人抢到红包金额为:0.11

第6个人抢到红包金额为:0.13

第7个人抢到红包金额为:0.01

第8个人抢到红包金额为:0.01

第9个人抢到红包金额为:0.03

第10个人抢到红包金额为:0.02

校验每个红包累计额度是否等于红包总额结果:true

1000元10个人抢=======================================================

第1个人抢到红包金额为:60.00

第2个人抢到红包金额为:695.54

第3个人抢到红包金额为:229.72

第4个人抢到红包金额为:8.95

第5个人抢到红包金额为:0.29

第6个人抢到红包金额为:4.64

第7个人抢到红包金额为:0.01

第8个人抢到红包金额为:0.69

第9个人抢到红包金额为:0.12

第10个人抢到红包金额为:0.04

校验每个红包累计额度是否等于红包总额结果:true

二、二倍均值法(微信红包采用此法)
还是以10元10个红包为例,去除每个红包的最小金额后,红包剩余9.9元,二倍均值计算公式:2 * 剩余金额/剩余红包数

[*]第一个红包在范围随机,假设随机得1.9,则第一个红包金额为2.0,红包剩余8元。
[*]第二个红包在范围随机,假设随机的1元,则第二个红包金额为1.1元,红包剩余7元。
[*]第三个红包在范围随机,假设随机的0.5元,则第三个红包金额为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");

//测试个场景

for (BigDecimal[] decimals : rrr) {

final BigDecimal amount = decimals;

final BigDecimal num = decimals;

System.out.println(amount + "元" + num + "个人抢=======================================================");

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)+"个人抢到红包金额为:"+min.add(redpeck));

}

System.out.println("校验每个红包累计额度是否等于红包总额结果:"+amount.compareTo(sum));

}

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

第1个人抢到红包金额为:0.01

第2个人抢到红包金额为:0.01

第3个人抢到红包金额为:0.01

第4个人抢到红包金额为:0.01

第5个人抢到红包金额为:0.01

第6个人抢到红包金额为:0.01

第7个人抢到红包金额为:0.01

第8个人抢到红包金额为:0.01

第9个人抢到红包金额为:0.01

第10个人抢到红包金额为:0.01

校验每个红包累计额度是否等于红包总额结果:true

100元10个人抢=======================================================

第1个人抢到红包金额为:6.20

第2个人抢到红包金额为:7.09

第3个人抢到红包金额为:10.62

第4个人抢到红包金额为:18.68

第5个人抢到红包金额为:18.74

第6个人抢到红包金额为:2.32

第7个人抢到红包金额为:15.44

第8个人抢到红包金额为:5.43

第9个人抢到红包金额为:15.16

第10个人抢到红包金额为:0.32

校验每个红包累计额度是否等于红包总额结果:true

1元10个人抢=======================================================

第1个人抢到红包金额为:0.08

第2个人抢到红包金额为:0.05

第3个人抢到红包金额为:0.17

第4个人抢到红包金额为:0.17

第5个人抢到红包金额为:0.08

第6个人抢到红包金额为:0.06

第7个人抢到红包金额为:0.18

第8个人抢到红包金额为:0.10

第9个人抢到红包金额为:0.02

第10个人抢到红包金额为:0.09

校验每个红包累计额度是否等于红包总额结果:true

1000元10个人抢=======================================================

第1个人抢到红包金额为:125.99

第2个人抢到红包金额为:165.08

第3个人抢到红包金额为:31.90

第4个人抢到红包金额为:94.78

第5个人抢到红包金额为:137.79

第6个人抢到红包金额为:88.89

第7个人抢到红包金额为:156.44

第8个人抢到红包金额为:7.97

第9个人抢到红包金额为:151.01

第10个人抢到红包金额为:40.15

校验每个红包累计额度是否等于红包总额结果:true

三、整体随机法
还是以10元10个红包为例,随机10个数,红包金额公式为:红包总额 * 随机数/随机数总和,假设10个随机数为,10个随机数总和为50,

[*]第一个红包10*5/50,得1元。
[*]第二个红包10*9/50,得1.8元。
[*]第三个红包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");

//测试个场景

for (BigDecimal[] decimals : rrr) {

final BigDecimal amount = decimals;

final BigDecimal num = decimals;

System.out.println(amount + "元" + num + "个人抢=======================================================");

test3(amount, min, num);

}

}



private static void test3(BigDecimal amount,BigDecimal min ,BigDecimal num){

final Random random = new Random();

final int[] rand = new int;

BigDecimal sum1 = BigDecimal.ZERO;

BigDecimal redpeck ;

int sum = 0;

for (int i = 0; i < num.intValue(); i++) {

rand = random.nextInt(100);

sum += rand;

}

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)).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)+"个人抢到红包金额为:"+min.add(redpeck));

}



System.out.println("校验每个红包累计额度是否等于红包总额结果:"+(amount.compareTo(sum1)==0));

}

测试结果如下:此算法随机性较大。
0.1元10个人抢=======================================================

第1个人抢到红包金额为:0.01

第2个人抢到红包金额为:0.01

第3个人抢到红包金额为:0.01

第4个人抢到红包金额为:0.01

第5个人抢到红包金额为:0.01

第6个人抢到红包金额为:0.01

第7个人抢到红包金额为:0.01

第8个人抢到红包金额为:0.01

第9个人抢到红包金额为:0.01

第10个人抢到红包金额为:0.01

校验每个红包累计额度是否等于红包总额结果:true

100元10个人抢=======================================================

第1个人抢到红包金额为:2.35

第2个人抢到红包金额为:14.12

第3个人抢到红包金额为:5.74

第4个人抢到红包金额为:6.61

第5个人抢到红包金额为:0.65

第6个人抢到红包金额为:10.97

第7个人抢到红包金额为:9.15

第8个人抢到红包金额为:7.93

第9个人抢到红包金额为:1.31

第10个人抢到红包金额为:41.17

校验每个红包累计额度是否等于红包总额结果:true

1元10个人抢=======================================================

第1个人抢到红包金额为:0.10

第2个人抢到红包金额为:0.02

第3个人抢到红包金额为:0.12

第4个人抢到红包金额为:0.03

第5个人抢到红包金额为:0.05

第6个人抢到红包金额为:0.12

第7个人抢到红包金额为:0.06

第8个人抢到红包金额为:0.01

第9个人抢到红包金额为:0.04

第10个人抢到红包金额为:0.45

校验每个红包累计额度是否等于红包总额结果:true

1000元10个人抢=======================================================

第1个人抢到红包金额为:148.96

第2个人抢到红包金额为:116.57

第3个人抢到红包金额为:80.49

第4个人抢到红包金额为:32.48

第5个人抢到红包金额为:89.39

第6个人抢到红包金额为:65.60

第7个人抢到红包金额为:20.77

第8个人抢到红包金额为:16.03

第9个人抢到红包金额为:36.79

第10个人抢到红包金额为:392.92

校验每个红包累计额度是否等于红包总额结果:true

四、割线法
还是以10元10个红包为例,在(0,10)范围随机9个间隔大于等于0.01数,假设为

[*]第一个红包得1元
[*]第二个红包得0.2元
[*]第三个红得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");

//测试个场景

for (BigDecimal[] decimals : rrr) {

final BigDecimal amount = decimals;

final BigDecimal num = decimals;

System.out.println(amount + "元" + num + "个人抢=======================================================");

test3(amount, min, num);

}

}



private static void test3(BigDecimal amount,BigDecimal min ,BigDecimal num){

final Random random = new Random();

final int[] rand = new int;

BigDecimal sum1 = BigDecimal.ZERO;

BigDecimal redpeck ;

int sum = 0;

for (int i = 0; i < num.intValue(); i++) {

rand = random.nextInt(100);

sum += rand;

}

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)).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)+"个人抢到红包金额为:"+min.add(redpeck));

}



System.out.println("校验每个红包累计额度是否等于红包总额结果:"+(amount.compareTo(sum1)==0));

}

测试结果如下:此算法随机性较大,且性能不好。
0.1元10个人抢=======================================================

第1个人抢到红包金额为:0.01

第2个人抢到红包金额为:0.01

第3个人抢到红包金额为:0.01

第4个人抢到红包金额为:0.01

第5个人抢到红包金额为:0.01

第6个人抢到红包金额为:0.01

第7个人抢到红包金额为:0.01

第8个人抢到红包金额为:0.01

第9个人抢到红包金额为:0.01

第10个人抢到红包金额为:0.01

校验每个红包累计额度是否等于红包总额结果:true

100元10个人抢=======================================================

第1个人抢到红包金额为:19.84

第2个人抢到红包金额为:2.73

第3个人抢到红包金额为:8.95

第4个人抢到红包金额为:14.10

第5个人抢到红包金额为:18.60

第6个人抢到红包金额为:3.66

第7个人抢到红包金额为:9.17

第8个人抢到红包金额为:15.49

第9个人抢到红包金额为:5.61

第10个人抢到红包金额为:1.85

校验每个红包累计额度是否等于红包总额结果:true

1元10个人抢=======================================================

第1个人抢到红包金额为:0.02

第2个人抢到红包金额为:0.28

第3个人抢到红包金额为:0.03

第4个人抢到红包金额为:0.02

第5个人抢到红包金额为:0.11

第6个人抢到红包金额为:0.23

第7个人抢到红包金额为:0.18

第8个人抢到红包金额为:0.09

第9个人抢到红包金额为:0.03

第10个人抢到红包金额为:0.01

校验每个红包累计额度是否等于红包总额结果:true

1000元10个人抢=======================================================

第1个人抢到红包金额为:69.28

第2个人抢到红包金额为:14.68

第3个人抢到红包金额为:373.16

第4个人抢到红包金额为:274.73

第5个人抢到红包金额为:30.77

第6个人抢到红包金额为:30.76

第7个人抢到红包金额为:95.55

第8个人抢到红包金额为:85.20

第9个人抢到红包金额为:10.44

第10个人抢到红包金额为:15.43

校验每个红包累计额度是否等于红包总额结果:true

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

http://www.zzvips.com/article/207395.html
页: [1]
查看完整版本: Java实现四种微信抢红包算法,拿走不谢