Java實(shí)現(xiàn)四種微信搶紅包算法，拿走不謝

作者：科技農(nóng)民工 2021-11-16 23:11:24

開發(fā) 后端算法

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

概述

[[435386]]

要求：

保證每個(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

責(zé)任編輯：華軒來源：今日頭條

Java 微信搶紅包