说到抢红包，大家肯定是很熟悉了，尤其是微信抢红包，我们几乎天天都会接触。虽然每次抢到的红包金额有大有小，但是我们都深深的沉浸在抢红包的快乐中。不过话说回来，不知道各位小伙伴有没有思考过抢红包使用的是什么算法呢？是如何实现的呢？今天我们一探究竟...
抢红包
现在我们发放的红包无非就是两种形式：拼手气红包和固定金额红包。固定金额红包的个数可以是一个也可以是多个，而且每一个红包里的金额都是一样的，所以也就不需要使用过多的算法去计算红包金额，相对来说就简单一些；而拼手气红包就相对复杂一些了，它需要计算每个红包的金额，而且要保证每个红包尽量公平，这也就对算法的要求比较高了。通过查阅百度和咨询实现过抢红包功能的朋友，了解到现在使用频率比较高的算法就是二倍均值法，下面我们就使用二倍均值法来模拟实现抢红包功能。
通过二倍均值法模拟抢红包
首先我们先看一下拼手气红包的功能要求：
·所有红包累计金额等于红包总金额
· 每个红包金额不能小于0.01元，也就是说必须保证每个用户至少能抢到一个预设的最小金额，人民币红包设置的最小金额一般是0.01元，如果是发放其他类型的红包（比如积分、其他类型货币等），则需要自定义一个最小金额
· 抢红包的期望收益应与先后顺序无关，即每个红包的金额大小和抢红包的先后顺序无关，保证红包尽量的公平
在实现上面的功能要求之前，我们还需要了解一下什么是二倍均值法：
假设红包总金额是X，红包个数为Y，每个红包的最低金额是0.01元，那么每次抢到的红包金额的范围在 (0.01, (X/Y) *2) 之间。
咱们举个具体的例子，假如现在有10个人来抢一个金额为100元的红包，那么根据上面的公式可以得出，第一个人抢到的金额范围是在（0.01，20）之间，那么根据正态分布可以得知，第一个人抢到的金额应该是在10元左右，并且远小于10元和远大于10元的概率都会很低，这里咱们就先假设第一个人抢到了10元；这时候第二个人来抢红包了，红包中剩下90元，我们根据公式可以得出，第二个人抢到的红包金额范围也是（0.01，20）之间。以此类推，我们可以看出来每个人所抢到的红包金额都在10元左右，并且远小于10元和远大于10元的概率都会很低，这样就尽可能的保证了每个人抢到的金额都是相近的。
接下来我们来看看具体的代码：
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Random;
/**
* 通过二倍均值法模拟微信抢红包
* @description: RedEnvelope
* @author: 庄霸.liziye
* @create: 2022-02-15 14:43
**/
public class RedEnvelope {
public static void main(String[] args) {
long startTime=System.currentTimeMillis();
//初始化测试场景，模拟四种情况：
//10人抢0.1元红包
//10人抢1元红包
//10人抢10元红包
//10人抢100元红包
BigDecimal[][] scene = {
{new BigDecimal("0.1"), new BigDecimal("10")},
{new BigDecimal("1"), new BigDecimal("10")},
{new BigDecimal("10"), new BigDecimal("10")},
{new BigDecimal("100"), new BigDecimal("10")}
};
//设置每个红包的最低金额为0.01元
BigDecimal min = new BigDecimal("0.01");
//分别测试各个红包
for (BigDecimal[] decimals : scene) {
final BigDecimal amount = decimals[0];
final BigDecimal num = decimals[1];
System.out.println("=====" + num + "个人抢一个"+ amount + "元的红包" + "=====");
GrabRedEnvelope(amount, min, num);
}
long endTime=System.currentTimeMillis();
System.out.println("程序运行时间： " + (endTime - startTime) + "ms");
}
//模拟抢红包过程
private static void GrabRedEnvelope(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{
//RoundingMode.CEILING：取右边最近的整数
//RoundingMode.FLOOR：取左边最近的正数
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("所有红包累计金额是否等于红包总金额："+compare(amount, sum));
}
private static boolean compare(BigDecimal a, BigDecimal b){
if(a.compareTo(b) == 0){
return true;
}
return false;
}
}
咱们看看代码的执行结果：
=====10个人抢一个0.1元的红包=====
第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
=====10个人抢一个1元的红包=====
第1个人抢到红包金额为：0.06
第2个人抢到红包金额为：0.11
第3个人抢到红包金额为：0.14
第4个人抢到红包金额为：0.10
第5个人抢到红包金额为：0.06
第6个人抢到红包金额为：0.06
第7个人抢到红包金额为：0.10
第8个人抢到红包金额为：0.02
第9个人抢到红包金额为：0.13
第10个人抢到红包金额为：0.22
所有红包累计金额是否等于红包总金额：true
=====10个人抢一个10元的红包=====
第1个人抢到红包金额为：1.61
第2个人抢到红包金额为：1.08
第3个人抢到红包金额为：1.45
第4个人抢到红包金额为：1.35
第5个人抢到红包金额为：1.02
第6个人抢到红包金额为：0.57
第7个人抢到红包金额为：0.11
第8个人抢到红包金额为：1.16
第9个人抢到红包金额为：1.31
第10个人抢到红包金额为：0.34
所有红包累计金额是否等于红包总金额：true
=====10个人抢一个100元的红包=====
第1个人抢到红包金额为：10.19
第2个人抢到红包金额为：9.38
第3个人抢到红包金额为：14.47
第4个人抢到红包金额为：2.08
第5个人抢到红包金额为：2.98
第6个人抢到红包金额为：12.42
第7个人抢到红包金额为：13.81
第8个人抢到红包金额为：19.87
第9个人抢到红包金额为：8.58
第10个人抢到红包金额为：6.22
所有红包累计金额是否等于红包总金额：true
程序运行时间： 6ms
我们通过执行结果可以看出，二倍均值法尽可能的保证了每个红包的金额大致相近。当然了，这个算法也不能做到绝对的公平，还是按照10个人抢一个金额为100元的红包为例，如果此时第一个人抢到了15元，那么第二个人的红包金额范围就变成了（0.01，18.88），假如此时第二个人又抢了很高的金额，那对后面的人是不利的。就像上面的执行结果中一样，10个人抢100元的红包，有人抢到了16.58，还有人抢到了0.26。
除二倍均值法之外，还有一个比较有意思的算法——割线法，那么咱们再简单看看什么是割线法。
通过割线法模拟抢红包
顾名思义，割线法在计算的时候就将红包总金额看作是一根绳子，然后对这根绳子进行切割，每一段绳子的长度代表了每一个红包的金额大小。
举个例子：现在有10个人抢一个10元的红包，那么在（0，10）的范围内随机9个间隔大于等于0.01的数，假设这9个分割数是[1,1.6,2,3,4,5,6,7,8]，那么每个红包金额的大小也就是1、0.6、0.4、1、1、1、1、1、1、2。
咱们还是来看看具体的代码：
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Random;
/**
* 通过割线法模拟微信抢红包
* @description: RedEnvelope
* @author: 庄霸.liziye
* @create: 2022-02-15 14:43
**/
public class RedEnvelope {
public static void main(String[] args) {
long startTime=System.currentTimeMillis();
//初始化测试场景，模拟四种情况：
//10人抢0.1元红包
//10人抢1元红包
//10人抢10元红包
//10人抢100元红包
BigDecimal[][] scene = {
{new BigDecimal("0.1"), new BigDecimal("10")},
{new BigDecimal("1"), new BigDecimal("10")},
{new BigDecimal("10"), new BigDecimal("10")},
{new BigDecimal("100"), new BigDecimal("10")}
};
//设置每个红包的最低金额为0.01元
BigDecimal min = new BigDecimal("0.01");
//分别测试各个红包
for (BigDecimal[] decimals : scene) {
final BigDecimal amount = decimals[0];
final BigDecimal num = decimals[1];
System.out.println("=====" + num + "个人抢一个"+ amount + "元的红包" + "=====");
GrabRedEnvelope(amount, min, num);
}
long endTime=System.currentTimeMillis();
System.out.println("程序运行时间： " + (endTime - startTime) + "ms");
}
//模拟抢红包过程
private static void GrabRedEnvelope(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)+"个人抢到红包金额为："+min.add(redpeck));
}
System.out.println("所有红包累计金额是否等于红包总金额：" + compare(amount, sum1));
}
private static boolean compare(BigDecimal a, BigDecimal b){
if(a.compareTo(b) == 0){
return true;
}
return false;
}
}
接下来再看看割线法的执行结果：
=====10个人抢一个0.1元的红包=====
第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
=====10个人抢一个1元的红包=====
第1个人抢到红包金额为：0.07
第2个人抢到红包金额为：0.12
第3个人抢到红包金额为：0.01
第4个人抢到红包金额为：0.10
第5个人抢到红包金额为：0.10
第6个人抢到红包金额为：0.08
第7个人抢到红包金额为：0.06
第8个人抢到红包金额为：0.06
第9个人抢到红包金额为：0.04
第10个人抢到红包金额为：0.36
所有红包累计金额是否等于红包总金额：true
=====10个人抢一个10元的红包=====
第1个人抢到红包金额为：1.19
第2个人抢到红包金额为：1.01
第3个人抢到红包金额为：0.60
第4个人抢到红包金额为：0.69
第5个人抢到红包金额为：0.66
第6个人抢到红包金额为：0.44
第7个人抢到红包金额为：0.39
第8个人抢到红包金额为：0.62
第9个人抢到红包金额为：0.41
第10个人抢到红包金额为：3.99
所有红包累计金额是否等于红包总金额：true
=====10个人抢一个100元的红包=====
第1个人抢到红包金额为：17.51
第2个人抢到红包金额为：14.62
第3个人抢到红包金额为：2.47
第4个人抢到红包金额为：4.19
第5个人抢到红包金额为：8.63
第6个人抢到红包金额为：0.01
第7个人抢到红包金额为：0.23
第8个人抢到红包金额为：6.15
第9个人抢到红包金额为：3.66
第10个人抢到红包金额为：42.53
所有红包累计金额是否等于红包总金额：true
程序运行时间： 11ms
通过执行结果我们可以看出来割线法的随机性比较大，并不能保证每个红包的金额大致相近（10个人抢一个100元的红包，还有人会抢到0.01，这不得给人家气坏了??）；而且割线法的性能也不是很好，虽然上面的代码体现出二倍均值法和割线法的执行时间相差不大，但是当生产环境中有大量的红包需要计算时，这差距肯定是巨大的。所以我们要实现抢红包的功能时一定要仔细斟酌，选择一个既能保证金额的相近又能保证高效的算法哦~
本文内容不用于商业目的，如涉及知识产权问题，请权利人联系51Testing小编(021-64471599-8017)，我们将立即处理
