今天想讲的是一个小算法,关于如何实现一个群发红包的功能,写这个小算法是因为以前一个朋友在面试的时候被面试官问到了,完事了就回来问我这个面试题,我当时第一想法是不就是一个随机数生成嘛,有什么难度的,后来仔细一想,不对呀,不是想的那么简单,我忽略了每个人得获取红包金额的概率的均衡,想想挺有意思的,于是就总结下这个小算法。
拿微信群红包举例吧,想实现微信红包需要满足三个条件:
- 每个人获取金额范围概率相同
- 所有人金额总数等于总金额
- 每个人最少获取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。
23A2DCD9-3D4E-4F2E-A5E7-1E20CD1B9DD1.png
当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。浮点数的值实际上是由一个特定的数学公式计算得到的。
网友评论