今天想讲的是一个小算法，关于如何实现一个群发红包的功能，写这个小算法是因为以前一个朋友在面试的时候被面试官问到了，完事了就回来问我这个面试题，我当时第一想法是不就是一个随机数生成嘛，有什么难度的，后来仔细一想，不对呀，不是想的那么简单，我忽略了每个人得获取红包金额的概率的均衡，想想挺有意思的，于是就总结下这个小算法。
拿微信群红包举例吧，想实现微信红包需要满足三个条件：
- 每个人获取金额范围概率相同
- 所有人金额总数等于总金额
- 每个人最少获取0.01元
那么基于以上三个条件有两个方案可以实现：
方案一：二倍均值法
在二倍均值法中，每个人领取红包的 （金额范围 = 总金额/总人数 x 2）， 这样可以保证每次随机金额的平均值是相等的，不会因为先后顺序而造成不公平。
可以这样理解，假设100个人分10个红包，那么：
第一个人 100/10 x 2 = 20，所以第一个人领取红包范围是（0，20），平均可以领取10元。
第二个人 90/9 x 2 = 20，所以第一个人领取红包范围是（0，20），平均可以领取10元。
第三个人 80/8 x 2 = 20，所以第一个人领取红包范围是（0，20），平均可以领取10元。
第一个人 100/10 x 2 = 20，所以第一个人领取红包范围是（0，20），平均可以领取10元。
那么以此类推，每次领取随机范围均值是相同的，也许你会问如果第一个人随机抢到15元，那么第二个人随机范围就是 85/9x2=18，那么区间是（0-18）了，其实我这里想讲的是第一个人随机到10元以上的概率和随机到10元以下的概率是一样的，所以第二个人的抢到的金额在（0-20）的范围的扩大或者缩小的概率也是一样的。
如果不太好理解，我就举个例子吧：10个人抓阄，只有一个阄是中奖的，大家随意去拿一个，不管先后顺序，每个人中奖的概率是0.1对吧，不能说第一个人没抓到中奖，那么第二个人中奖的概率就不是0.1了对吧，因为谁也不知道第一个人到底能不能中奖，我们这里讨论的是一个基准平均概率。
那么算法的实现如下：
//二倍均值法
public static void getRandomMoney(double amount,Integer person){
if (person == 1){
person --;
double lastMoney = (double)Math.round(amount*100)/100;
System.out.println("第"+(person+1)+"个人："+lastMoney+"元");
return;
}
Random r = new Random();
double min = 0.01;
double max = amount/person * 2;
double money = r.nextDouble() * max;
money = money<=min ? 0.01 : money;
money = Math.floor(money * 100) / 100;
person --;
amount -= money;
System.out.println("第"+(person+1)+"个人："+money+"元");
getRandomMoney(amount,person);
}
当然用递归其实是没必要的，有些资源浪费了，可以这样写比较好：
@Test
public void testtMoney() throws Exception {
//这里100 元 * 100 是想让红包金额随机到小数点后两位
List<Integer> amountList = divideRedPackage((100*100), 10);
float a = 0;
for (Integer amount : amountList){
System.out.println("抢到金额：" + new BigDecimal(amount).divide(new BigDecimal(100)));
a+=amount;
}
System.out.println("总金额="+a);
}
//二倍均值法
//发红包算法，金额参数以分为单位
public static List <Integer> divideRedPackage(Integer totalAmount, Integer totalPeopleNum){
List<Integer> amountList = new ArrayList<Integer>();
Integer restAmount = totalAmount;
Integer restPeopleNum = totalPeopleNum;
Random random = new Random();
for (int i= 0; i<totalPeopleNum- 1; i++){
//随机范围：[1，剩余人均金额的两倍)，左闭右开
int amount = random.nextInt(restAmount / restPeopleNum * 2 - 1) + 1;
//System.out.println(amount);
restAmount -= amount;
restPeopleNum --;
amountList.add(amount);
}
amountList.add(restAmount);
return amountList;
}
那么这种方法随机金额最多是人均金额的两倍，虽然比较公平，但是随机自由度不高，那么怎么样能做到随机自由度比较高，并且还公平呢？于是引出下面这一种算法了。
方案二：区间切割法
这种方法比较容易理解，所谓区间切割，就是我们可以把总金额当作一个区间，随机进行n次切割，保证切割的区域块等于总人数就ok。
当N个人一起抢总金额为M的红包时候，我们可以做N-1次随机运算，以此确定N-1个切割点，随机范围的区间是（1，M）。
也可以不看金额，直接在（0-1）之间生成N-1个点，然后根据每个点和上个点区间计算百分比，用百分比x总金额得出每个人的红包额度。
ps：需要注意的是防止随机点重复出现
那么算法实现如下：
//区间切割法
public static void getRandomMoney2(double amount,Integer person){
BigDecimal amount1 = new BigDecimal(Double.valueOf(amount));
//计算出随机数分布值
amount1 = amount1.multiply(BigDecimal.valueOf(100));
Set set = new HashSet();
ArrayList<Integer> list = new ArrayList();
list.add(0,0);
Random r = new Random();
for (int i=0;i<person-1;i++){
//防止重复点
while (true){
Integer money = r.nextInt(amount1.intValue());
boolean isContain = set.contains(money);
if (isContain == false){
set.add(money);
list.add(money);
break;
}
}
}
list.add(person,amount1.intValue());
//排序
Collections.sort(list, Collections.reverseOrder());
//根据比例计算金额
BigDecimal count = new BigDecimal(0);
for(int i=0;i<list.size()-1;i++){
if (i==list.size()-2){
BigDecimal a = amount1.divide(BigDecimal.valueOf(100)).subtract(count);
System.out.println("第"+i+"个人红包为："+a);
count = count.add(a);
System.out.println("总金额="+count);
return;
}
double gap = list.get(i) - list.get(i+1);
DecimalFormat df = new DecimalFormat("0.00");
String mon = df.format(new BigDecimal(gap/amount * (amount/100)));
count = count.add(BigDecimal.valueOf(Double.parseDouble(mon)));
System.out.println("第"+i+"个人红包为："+mon);
}
}
结果如下：
第0个人红包为：18.88
第1个人红包为：10.45
第2个人红包为：4.88
第3个人红包为：6.08
第4个人红包为：21.47
第5个人红包为：6.94
第6个人红包为：5.98
第7个人红包为：21.55
第8个人红包为：1.15
第9个人红包为：2.62
总金额=100.00
以上便是群发红包实现算法，需要注意的是BigDecimal这个类，其实java的float只能用来进行科学计算或工程计算，在大多数的商业计算中，一般采用java.math.BigDecimal类来进行精确计算。如果不用BigDecimal，那么两个float类型数据运算时候会出现一些莫名的错误导致计算结果偏差。
原因在于我们的计算机是二进制的。浮点数没有办法是用二进制进行精确表示。我们的CPU表示浮点数由两个部分组成：指数和尾数，这样的表示方法一般都会失去一定的精确度，有些浮点数运算也会产生一定的误差。如：2.4的二进制表示并非就是精确的2.4。反而最为接近的二进制表示是 2.3999999999999999。浮点数的值实际上是由一个特定的数学公式计算得到的。
