美文网首页产品之火
算法:如何实现群发红包算法

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

作者: 文子产品笔记 | 来源:发表于2019-01-06 01:31 被阅读290次

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

    拿微信群红包举例吧,想实现微信红包需要满足三个条件:
    • 每个人获取金额范围概率相同
    • 所有人金额总数等于总金额
    • 每个人最少获取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。浮点数的值实际上是由一个特定的数学公式计算得到的。

    相关文章

      网友评论

        本文标题:算法:如何实现群发红包算法

        本文链接:https://www.haomeiwen.com/subject/kvgdrqtx.html