算法：如何实现群发红包算法

今天想讲的是一个小算法，关于如何实现一个群发红包的功能，写这个小算法是因为以前一个朋友在面试的时候被面试官问到了，完事了就回来问我这个面试题，我当时第一想法是不就是一个随机数生成嘛，有什么难度的，后来仔细一想，不对呀，不是想的那么简单，我忽略了每个人得获取红包金额的概率的均衡，想想挺有意思的，于是就总结下这个小算法。

拿微信群红包举例吧，想实现微信红包需要满足三个条件：

• 每个人获取金额范围概率相同
• 所有人金额总数等于总金额
• 每个人最少获取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。浮点数的值实际上是由一个特定的数学公式计算得到的。