Java實(shí)現(xiàn)4種微信搶紅包算法(小結(jié))

更新時(shí)間：2021年12月21日 11:24:13 作者：科技農(nóng)民工

微信紅包是大家經(jīng)常使用的，到現(xiàn)在為止仍然有很多紅包開發(fā)的需求，實(shí)現(xiàn)搶紅包算法也是面試?？碱}，本文就詳細(xì)的來介紹一下如何實(shí)現(xiàn)，感興趣的可以了解一下

概述

14年微信推出紅包功能以后，很多公司開始上自己的紅包功能，到現(xiàn)在為止仍然有很多紅包開發(fā)的需求，實(shí)現(xiàn)搶紅包算法也是面試?？碱}。

要求：

保證每個(gè)紅包最少分得0.01元
保證每個(gè)紅包金額概率盡量均衡
所有紅包累計(jì)金額登于紅包總金額

本文提供4中紅包算法及Java代碼實(shí)現(xiàn)demo，僅供參考。其中每種算法測試場景為：0.1元10個(gè)包，1元10個(gè)包，100元10個(gè)包，1000元10個(gè)包。

一、剩余金額隨機(jī)法

以10元10個(gè)紅包為例，去除每個(gè)紅包的最小金額后，紅包剩余9.9元；

第一個(gè)紅包在[0,9.9]范圍隨機(jī)，假設(shè)隨機(jī)得1元，則第一個(gè)紅包金額為1.1元，紅包剩余8.9元。
第二個(gè)紅包在[0,8.9]范圍隨機(jī)，假設(shè)隨機(jī)得1.5元，則第二個(gè)紅包金額為1.6元，紅包剩余7.4元。
第三個(gè)紅包在[0,7.4]范圍隨機(jī)，假設(shè)隨機(jī)得0.5元，則第三個(gè)紅包金額為0.6元，紅包剩余6.9元。
以此類推。

public static void main(String[] args) {
    //初始化測試場景
    BigDecimal[][] rrr = {
            {new BigDecimal("0.1"), new BigDecimal("10")},
            {new BigDecimal("1"), new BigDecimal("10")},
            {new BigDecimal("100"), new BigDecimal("10")},
            {new BigDecimal("1000"), new BigDecimal("10")}
    };
    BigDecimal min = new BigDecimal("0.01");
    //測試個(gè)場景
    for (BigDecimal[] decimals : rrr) {
        final BigDecimal amount = decimals[0];
        final BigDecimal num = decimals[1];
        System.out.println(amount + "元" + num + "個(gè)人搶=======================================================");
        test1(amount, min, num);
    }
}

private static void test1(BigDecimal amount, BigDecimal min, BigDecimal num) {
    BigDecimal remain = amount.subtract(min.multiply(num));
    final Random random = new Random();
    final BigDecimal hundred = new BigDecimal("100");
    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 {
            redpeck = new BigDecimal(nextInt).multiply(remain).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) + "個(gè)人搶到紅包金額為：" + min.add(redpeck));
    }
    System.out.println("校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果：" + (amount.compareTo(sum) == 0));
}

測試結(jié)果如下:可以看出此算法有明顯缺陷，即：先領(lǐng)取的紅包金額較大，后領(lǐng)取的紅包金額較小，這就使得搶紅包便的不公平。
0.1元10個(gè)人搶=======================================================
第1個(gè)人搶到紅包金額為：0.01
第2個(gè)人搶到紅包金額為：0.01
第3個(gè)人搶到紅包金額為：0.01
第4個(gè)人搶到紅包金額為：0.01
第5個(gè)人搶到紅包金額為：0.01
第6個(gè)人搶到紅包金額為：0.01
第7個(gè)人搶到紅包金額為：0.01
第8個(gè)人搶到紅包金額為：0.01
第9個(gè)人搶到紅包金額為：0.01
第10個(gè)人搶到紅包金額為：0.01
校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果：true
1元10個(gè)人搶=======================================================
第1個(gè)人搶到紅包金額為：0.09
第2個(gè)人搶到紅包金額為：0.28
第3個(gè)人搶到紅包金額為：0.19
第4個(gè)人搶到紅包金額為：0.20
第5個(gè)人搶到紅包金額為：0.15
第6個(gè)人搶到紅包金額為：0.02
第7個(gè)人搶到紅包金額為：0.03
第8個(gè)人搶到紅包金額為：0.01
第9個(gè)人搶到紅包金額為：0.01
第10個(gè)人搶到紅包金額為：0.02
校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果：true
100元10個(gè)人搶=======================================================
第1個(gè)人搶到紅包金額為：19.99
第2個(gè)人搶到紅包金額為：29.58
第3個(gè)人搶到紅包金額為：38.27
第4個(gè)人搶到紅包金額為：11.85
第5個(gè)人搶到紅包金額為：0.11
第6個(gè)人搶到紅包金額為：0.13
第7個(gè)人搶到紅包金額為：0.01
第8個(gè)人搶到紅包金額為：0.01
第9個(gè)人搶到紅包金額為：0.03
第10個(gè)人搶到紅包金額為：0.02
校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果：true
1000元10個(gè)人搶=======================================================
第1個(gè)人搶到紅包金額為：60.00
第2個(gè)人搶到紅包金額為：695.54
第3個(gè)人搶到紅包金額為：229.72
第4個(gè)人搶到紅包金額為：8.95
第5個(gè)人搶到紅包金額為：0.29
第6個(gè)人搶到紅包金額為：4.64
第7個(gè)人搶到紅包金額為：0.01
第8個(gè)人搶到紅包金額為：0.69
第9個(gè)人搶到紅包金額為：0.12
第10個(gè)人搶到紅包金額為：0.04
校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果：true

二、二倍均值法(微信紅包采用此法)

還是以10元10個(gè)紅包為例，去除每個(gè)紅包的最小金額后，紅包剩余9.9元，二倍均值計(jì)算公式：2 * 剩余金額/剩余紅包數(shù)

第一個(gè)紅包在[0,1.98]范圍隨機(jī)，假設(shè)隨機(jī)得1.9，則第一個(gè)紅包金額為2.0，紅包剩余8元。
第二個(gè)紅包在[0,2]范圍隨機(jī)，假設(shè)隨機(jī)的1元，則第二個(gè)紅包金額為1.1元，紅包剩余7元。
第三個(gè)紅包在[0,2]范圍隨機(jī)，假設(shè)隨機(jī)的0.5元，則第三個(gè)紅包金額為0.6元，紅包剩余5.5元。
以此類推。

public static void main(String[] args) {
    //初始化測試場景
    BigDecimal[][] rrr = {
            {new BigDecimal("0.1"), new BigDecimal("10")},
            {new BigDecimal("1"), new BigDecimal("10")},
            {new BigDecimal("100"), new BigDecimal("10")},
            {new BigDecimal("1000"), new BigDecimal("10")}
    };
    BigDecimal min = new BigDecimal("0.01");
    //測試個(gè)場景
    for (BigDecimal[] decimals : rrr) {
        final BigDecimal amount = decimals[0];
        final BigDecimal num = decimals[1];
        System.out.println(amount + "元" + num + "個(gè)人搶=======================================================");
        test2(amount, min, num);
    }
}


private static void test2(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{
            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)+"個(gè)人搶到紅包金額為："+min.add(redpeck));
    }
    System.out.println("校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果："+amount.compareTo(sum));
}

測試結(jié)果如下:此算法很好的保證了搶紅包幾率大致均等。
0.1元10個(gè)人搶=======================================================
第1個(gè)人搶到紅包金額為：0.01
第2個(gè)人搶到紅包金額為：0.01
第3個(gè)人搶到紅包金額為：0.01
第4個(gè)人搶到紅包金額為：0.01
第5個(gè)人搶到紅包金額為：0.01
第6個(gè)人搶到紅包金額為：0.01
第7個(gè)人搶到紅包金額為：0.01
第8個(gè)人搶到紅包金額為：0.01
第9個(gè)人搶到紅包金額為：0.01
第10個(gè)人搶到紅包金額為：0.01
校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果：true
100元10個(gè)人搶=======================================================
第1個(gè)人搶到紅包金額為：6.20
第2個(gè)人搶到紅包金額為：7.09
第3個(gè)人搶到紅包金額為：10.62
第4個(gè)人搶到紅包金額為：18.68
第5個(gè)人搶到紅包金額為：18.74
第6個(gè)人搶到紅包金額為：2.32
第7個(gè)人搶到紅包金額為：15.44
第8個(gè)人搶到紅包金額為：5.43
第9個(gè)人搶到紅包金額為：15.16
第10個(gè)人搶到紅包金額為：0.32
校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果：true
1元10個(gè)人搶=======================================================
第1個(gè)人搶到紅包金額為：0.08
第2個(gè)人搶到紅包金額為：0.05
第3個(gè)人搶到紅包金額為：0.17
第4個(gè)人搶到紅包金額為：0.17
第5個(gè)人搶到紅包金額為：0.08
第6個(gè)人搶到紅包金額為：0.06
第7個(gè)人搶到紅包金額為：0.18
第8個(gè)人搶到紅包金額為：0.10
第9個(gè)人搶到紅包金額為：0.02
第10個(gè)人搶到紅包金額為：0.09
校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果：true
1000元10個(gè)人搶=======================================================
第1個(gè)人搶到紅包金額為：125.99
第2個(gè)人搶到紅包金額為：165.08
第3個(gè)人搶到紅包金額為：31.90
第4個(gè)人搶到紅包金額為：94.78
第5個(gè)人搶到紅包金額為：137.79
第6個(gè)人搶到紅包金額為：88.89
第7個(gè)人搶到紅包金額為：156.44
第8個(gè)人搶到紅包金額為：7.97
第9個(gè)人搶到紅包金額為：151.01
第10個(gè)人搶到紅包金額為：40.15
校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果：true

三、整體隨機(jī)法

還是以10元10個(gè)紅包為例，隨機(jī)10個(gè)數(shù)，紅包金額公式為：紅包總額 * 隨機(jī)數(shù)/隨機(jī)數(shù)總和，假設(shè)10個(gè)隨機(jī)數(shù)為[5,9,8,7,6,5,4,3,2,1],10個(gè)隨機(jī)數(shù)總和為50，

第一個(gè)紅包10*5/50，得1元。
第二個(gè)紅包10*9/50，得1.8元。
第三個(gè)紅包10*8/50，得1.6元。
以此類推。

public static void main(String[] args) {
    //初始化測試場景
    BigDecimal[][] rrr = {
            {new BigDecimal("0.1"), new BigDecimal("10")},
            {new BigDecimal("1"), new BigDecimal("10")},
            {new BigDecimal("100"), new BigDecimal("10")},
            {new BigDecimal("1000"), new BigDecimal("10")}
    };
    BigDecimal min = new BigDecimal("0.01");
    //測試個(gè)場景
    for (BigDecimal[] decimals : rrr) {
        final BigDecimal amount = decimals[0];
        final BigDecimal num = decimals[1];
        System.out.println(amount + "元" + num + "個(gè)人搶=======================================================");
        test3(amount, min, num);
    }
}

private static void test3(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)+"個(gè)人搶到紅包金額為："+min.add(redpeck));
    }

    System.out.println("校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果："+(amount.compareTo(sum1)==0));
}

測試結(jié)果如下:此算法隨機(jī)性較大。
0.1元10個(gè)人搶=======================================================
第1個(gè)人搶到紅包金額為：0.01
第2個(gè)人搶到紅包金額為：0.01
第3個(gè)人搶到紅包金額為：0.01
第4個(gè)人搶到紅包金額為：0.01
第5個(gè)人搶到紅包金額為：0.01
第6個(gè)人搶到紅包金額為：0.01
第7個(gè)人搶到紅包金額為：0.01
第8個(gè)人搶到紅包金額為：0.01
第9個(gè)人搶到紅包金額為：0.01
第10個(gè)人搶到紅包金額為：0.01
校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果：true
100元10個(gè)人搶=======================================================
第1個(gè)人搶到紅包金額為：2.35
第2個(gè)人搶到紅包金額為：14.12
第3個(gè)人搶到紅包金額為：5.74
第4個(gè)人搶到紅包金額為：6.61
第5個(gè)人搶到紅包金額為：0.65
第6個(gè)人搶到紅包金額為：10.97
第7個(gè)人搶到紅包金額為：9.15
第8個(gè)人搶到紅包金額為：7.93
第9個(gè)人搶到紅包金額為：1.31
第10個(gè)人搶到紅包金額為：41.17
校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果：true
1元10個(gè)人搶=======================================================
第1個(gè)人搶到紅包金額為：0.10
第2個(gè)人搶到紅包金額為：0.02
第3個(gè)人搶到紅包金額為：0.12
第4個(gè)人搶到紅包金額為：0.03
第5個(gè)人搶到紅包金額為：0.05
第6個(gè)人搶到紅包金額為：0.12
第7個(gè)人搶到紅包金額為：0.06
第8個(gè)人搶到紅包金額為：0.01
第9個(gè)人搶到紅包金額為：0.04
第10個(gè)人搶到紅包金額為：0.45
校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果：true
1000元10個(gè)人搶=======================================================
第1個(gè)人搶到紅包金額為：148.96
第2個(gè)人搶到紅包金額為：116.57
第3個(gè)人搶到紅包金額為：80.49
第4個(gè)人搶到紅包金額為：32.48
第5個(gè)人搶到紅包金額為：89.39
第6個(gè)人搶到紅包金額為：65.60
第7個(gè)人搶到紅包金額為：20.77
第8個(gè)人搶到紅包金額為：16.03
第9個(gè)人搶到紅包金額為：36.79
第10個(gè)人搶到紅包金額為：392.92
校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果：true

四、割線法

還是以10元10個(gè)紅包為例，在(0,10)范圍隨機(jī)9個(gè)間隔大于等于0.01數(shù)，假設(shè)為[1,1.2,2,3,4,5,6,7,8]

第一個(gè)紅包得1元
第二個(gè)紅包得0.2元
第三個(gè)紅得0.8元。
以此類推。

public static void main(String[] args) {
    //初始化測試場景
    BigDecimal[][] rrr = {
            {new BigDecimal("0.1"), new BigDecimal("10")},
            {new BigDecimal("1"), new BigDecimal("10")},
            {new BigDecimal("100"), new BigDecimal("10")},
            {new BigDecimal("1000"), new BigDecimal("10")}
    };
    BigDecimal min = new BigDecimal("0.01");
    //測試個(gè)場景
    for (BigDecimal[] decimals : rrr) {
        final BigDecimal amount = decimals[0];
        final BigDecimal num = decimals[1];
        System.out.println(amount + "元" + num + "個(gè)人搶=======================================================");
        test3(amount, min, num);
    }
}

private static void test3(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)+"個(gè)人搶到紅包金額為："+min.add(redpeck));
    }

    System.out.println("校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果："+(amount.compareTo(sum1)==0));
}

測試結(jié)果如下:此算法隨機(jī)性較大，且性能不好
0.1元10個(gè)人搶=======================================================
第1個(gè)人搶到紅包金額為：0.01
第2個(gè)人搶到紅包金額為：0.01
第3個(gè)人搶到紅包金額為：0.01
第4個(gè)人搶到紅包金額為：0.01
第5個(gè)人搶到紅包金額為：0.01
第6個(gè)人搶到紅包金額為：0.01
第7個(gè)人搶到紅包金額為：0.01
第8個(gè)人搶到紅包金額為：0.01
第9個(gè)人搶到紅包金額為：0.01
第10個(gè)人搶到紅包金額為：0.01
校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果：true
100元10個(gè)人搶=======================================================
第1個(gè)人搶到紅包金額為：19.84
第2個(gè)人搶到紅包金額為：2.73
第3個(gè)人搶到紅包金額為：8.95
第4個(gè)人搶到紅包金額為：14.10
第5個(gè)人搶到紅包金額為：18.60
第6個(gè)人搶到紅包金額為：3.66
第7個(gè)人搶到紅包金額為：9.17
第8個(gè)人搶到紅包金額為：15.49
第9個(gè)人搶到紅包金額為：5.61
第10個(gè)人搶到紅包金額為：1.85
校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果：true
1元10個(gè)人搶=======================================================
第1個(gè)人搶到紅包金額為：0.02
第2個(gè)人搶到紅包金額為：0.28
第3個(gè)人搶到紅包金額為：0.03
第4個(gè)人搶到紅包金額為：0.02
第5個(gè)人搶到紅包金額為：0.11
第6個(gè)人搶到紅包金額為：0.23
第7個(gè)人搶到紅包金額為：0.18
第8個(gè)人搶到紅包金額為：0.09
第9個(gè)人搶到紅包金額為：0.03
第10個(gè)人搶到紅包金額為：0.01
校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果：true
1000元10個(gè)人搶=======================================================
第1個(gè)人搶到紅包金額為：69.28
第2個(gè)人搶到紅包金額為：14.68
第3個(gè)人搶到紅包金額為：373.16
第4個(gè)人搶到紅包金額為：274.73
第5個(gè)人搶到紅包金額為：30.77
第6個(gè)人搶到紅包金額為：30.76
第7個(gè)人搶到紅包金額為：95.55
第8個(gè)人搶到紅包金額為：85.20
第9個(gè)人搶到紅包金額為：10.44
第10個(gè)人搶到紅包金額為：15.43
校驗(yàn)每個(gè)紅包累計(jì)額度是否等于紅包總額結(jié)果：true