Java實現四種微信搶紅包演算法,拿走不謝

語言: CN / TW / HK

概述

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

要求:

  1. 保證每個紅包最少分得0.01元
  2. 保證每個紅包金額概率儘量均衡
  3. 所有紅包累計金額等於紅包總金額

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

一、剩餘金額隨機法

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

  1. 第一個紅包在[0,9.9]範圍隨機,假設隨機得1元,則第一個紅包金額為1.1元,紅包剩餘8.9元。
  2. 第二個紅包在[0,8.9]範圍隨機,假設隨機得1.5元,則第二個紅包金額為1.6元,紅包剩餘7.4元。
  3. 第三個紅包在[0,7.4]範圍隨機,假設隨機得0.5元,則第三個紅包金額為0.6元,紅包剩餘6.9元。
  4. 以此類推。
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 * 剩餘金額/剩餘紅包數

  1. 第一個紅包在[0,1.98]範圍隨機,假設隨機得1.9,則第一個紅包金額為2.0,紅包剩餘8元。
  2. 第二個紅包在[0,2]範圍隨機,假設隨機的1元,則第二個紅包金額為1.1元,紅包剩餘7元。
  3. 第三個紅包在[0,2]範圍隨機,假設隨機的0.5元,則第三個紅包金額為0.6元,紅包剩餘5.5元。
  4. 以此類推。
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,

  1. 第一個紅包10*5/50,得1元。
  2. 第二個紅包10*9/50,得1.8元。
  3. 第三個紅包10*8/50,得1.6元。
  4. 以此類推。
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. 第一個紅包得1元
  2. 第二個紅包得0.2元
  3. 第三個紅得0.8元。
  4. 以此類推。
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