Java實現4種微信搶紅包算法(小結)

Posted on by

概述

14年微信推出紅包功能以後，很多公司開始上自己的紅包功能，到現在為止仍然有很多紅包開發的需求，實現搶紅包算法也是面試常考題。

要求：

  • 保證每個紅包最少分得0.01元
  • 保證每個紅包金額概率盡量均衡
  • 所有紅包累計金額登於紅包總金額

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

一、剩餘金額隨機法

以10元10個紅包為例，去除每個紅包的最小金額後，紅包剩餘9.9元；

  • 第一個紅包在[0,9.9]范圍隨機，假設隨機得1元，則第一個紅包金額為1.1元，紅包剩餘8.9元。
  • 第二個紅包在[0,8.9]范圍隨機，假設隨機得1.5元，則第二個紅包金額為1.6元，紅包剩餘7.4元。
  • 第三個紅包在[0,7.4]范圍隨機，假設隨機得0.5元，則第三個紅包金額為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");
    //測試個場景
    for (BigDecimal[] decimals : rrr) {
        final BigDecimal amount = decimals[0];
        final BigDecimal num = decimals[1];
        System.out.println(amount + "元" + num + "個人搶=======================================================");
        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) + "個人搶到紅包金額為：" + min.add(redpeck));
    }
    System.out.println("校驗每個紅包累計額度是否等於紅包總額結果：" + (amount.compareTo(sum) == 0));
}

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

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

還是以10元10個紅包為例，去除每個紅包的最小金額後，紅包剩餘9.9元，二倍均值計算公式：2 * 剩餘金額/剩餘紅包數

  • 第一個紅包在[0,1.98]范圍隨機，假設隨機得1.9，則第一個紅包金額為2.0，紅包剩餘8元。
  • 第二個紅包在[0,2]范圍隨機，假設隨機的1元，則第二個紅包金額為1.1元，紅包剩餘7元。
  • 第三個紅包在[0,2]范圍隨機，假設隨機的0.5元，則第三個紅包金額為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");
    //測試個場景
    for (BigDecimal[] decimals : rrr) {
        final BigDecimal amount = decimals[0];
        final BigDecimal num = decimals[1];
        System.out.println(amount + "元" + num + "個人搶=======================================================");
        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)+"個人搶到紅包金額為："+min.add(redpeck));
    }
    System.out.println("校驗每個紅包累計額度是否等於紅包總額結果："+amount.compareTo(sum));
}

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

三、整體隨機法

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

  • 第一個紅包10*5/50，得1元。
  • 第二個紅包10*9/50，得1.8元。
  • 第三個紅包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");
    //測試個場景
    for (BigDecimal[] decimals : rrr) {
        final BigDecimal amount = decimals[0];
        final BigDecimal num = decimals[1];
        System.out.println(amount + "元" + num + "個人搶=======================================================");
        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)+"個人搶到紅包金額為："+min.add(redpeck));
    }

    System.out.println("校驗每個紅包累計額度是否等於紅包總額結果："+(amount.compareTo(sum1)==0));
}

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

四、割線法

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

  • 第一個紅包得1元
  • 第二個紅包得0.2元
  • 第三個紅得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");
    //測試個場景
    for (BigDecimal[] decimals : rrr) {
        final BigDecimal amount = decimals[0];
        final BigDecimal num = decimals[1];
        System.out.println(amount + "元" + num + "個人搶=======================================================");
        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)+"個人搶到紅包金額為："+min.add(redpeck));
    }

    System.out.println("校驗每個紅包累計額度是否等於紅包總額結果："+(amount.compareTo(sum1)==0));
}

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

到此這篇關於Java實現4種微信搶紅包算法(小結)的文章就介紹到這瞭,更多相關Java 微信搶紅包 內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：