首先来看一下抢红包的基本要求:

  1. 所有人抢到金额之和等于红包金额,不能超过,也不能少于。
  2. 每个人至少抢到一分钱。
  3. 要保证所有人抢到金额的几率相等。

下面来看具体的算法实现。

第一种算法

每个人每次抢到的金额范围是:(0,剩余金额)。

不过这个算法思路会违背“每个人分的金额随机,不能差距太大”。

为什么会这样,举个例子:

假设有10元钱,10个人分。

第一个人的随机范围是(0,10),平均分到5元。

假设第一个人随机分到5元,剩余金额为10-5=5元。

第二个人的随机范围是(0,5),平均分到2.5元。

假设第二个人随机分到2.5元,剩余金额为5-2.5=2.5元。

第三个人的随机范围是(0,2.5),平均分到1.25元

以此类推,每一次随机范围越来越小,违背了“每个人分的金额随机,不能差距太大”。

具体实现代码如下:

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * @author god-jiang
 * @date 2020/1/26  16:49
 */
public class Algorithm {
    public static List<Integer> divideRedPackage(Integer totalAmount, Integer totalPeopleNum) {
        List<Integer> amountList = new ArrayList<>();
        Integer restAmount = totalAmount;
        Integer restPeopleNum = totalPeopleNum;
        Random random = new Random();
        for (int i = 0; i < totalPeopleNum - 1; i++) {
            int amount = random.nextInt(restAmount - restPeopleNum - 1) + 1;
            restAmount -= amount;
            restPeopleNum--;
            amountList.add(amount);
        }
        amountList.add(restAmount);
        return amountList;
    }

    public static void main(String[] args) {
        List<Integer> amountList = divideRedPackage(1000, 10);
        for (Integer amount : amountList
        ) {
            System.out.println("抢到金额" + new BigDecimal(amount).divide(new BigDecimal(100)));
        }
    }
}

第二种算法:二倍均值法

思路

每次抢到的金额=随机范围(0,M/N *2)

M表示剩余红包金额,N表示剩余人数。这个公式保证了每次随机金额的平均值是相等的。

举个例子:

假设有10元钱,10个人分:

10/10 *2=2,所以第一个人分到的范围是(0,2),平均可以分到1元。

假设第一个人随机分到1元,那么剩余金额是10-1=9元。

9/9 *2=2,所以第二个人分到的范围是(0,2),平均可以分到1元。

假设第二个人随机分到1元,那么剩余金额是9-1=8元。

8/8 *2=2,所以第三个人的随机范围也是(0,2),平均可以分到1元。

以此类推,每一次随机范围都是相等的。

相关代码实现如下:

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * @author god-jiang
 * @date 2020/1/26  15:39
 */
public class Algorithm {
    public static List<Integer> divideRedPackage(Integer totalAmount, Integer totalPeopleNum) {
        List<Integer> amountList = new ArrayList<>();
        Integer restAmount = totalAmount;
        Integer restPeopleNum = totalPeopleNum;
        Random random = new Random();
        for (int i = 0; i < totalPeopleNum - 1; i++) {
            //保证金额范围是[1,剩余金额2倍),左闭右开
            int amount = random.nextInt(restAmount / restPeopleNum * 2 - 1) + 1;
            restAmount -= amount;
            restPeopleNum--;
            amountList.add(amount);
        }
        amountList.add(restAmount);
        return amountList;
    }

    public static void main(String[] args) {
        List<Integer> amountList = divideRedPackage(1000, 10);
        for (Integer amount : amountList
        ) {
            System.out.println("抢到金额" + new BigDecimal(amount).divide(new BigDecimal(100)));
        }
    }
}

这种算法其实也有弊端,比如经常会有人使用1块钱发100份的情况,或者1.01发100份的情况,此时最后抢的金额始终是2分。

另外,除了最后一次,任何一次抢到的红包的金额都小于人均金额的两倍,并不是任意随机的。

第三种方案:线段切割法

何谓线段切割法?我们可以把红包总金额想象成一条很长的线段,而每个人抢到的金额,则是这条主线段所拆分出的若干子线段。

如何确定每一条子线段的长度呢?由“切割点”来决定。当 N 个人一起抢红包的时候,就需要确定 N-1 个切割点。因此,我们需要做 N-1 次随机运算,以此确定 N-1 个切割点。随机的范围区间是(1, M)。

当所有切割点确定以后,子线段的长度也随之确定。这样每个人来抢红包的时候,只需要顺次领取与子线段长度等价的红包金额即可。

这就是线段切割法的思路。在这里需要注意以下两点:

  1. 当随机切割点出现重复,如何处理。
  2. 如何尽可能降低时间复杂度和空间复杂度。

相关实现代码如下:

public static List<Integer> lineCut(int money, int people) {

		List<Integer> teams = new ArrayList<>(people - 1);
		List<Integer> result = new ArrayList<>(people);

		Random random = new Random();
		while (teams.size() < people - 1) {
			int point = random.nextInt(money - 1) + 1;
			if (!teams.contains(point)) {
				teams.add(point);
			}
		}
		Collections.sort(teams);
		System.out.print("分割点:");
		System.out.println(teams);

		int left = 0;
		for (Integer integer : teams) {
			result.add(integer - left);
			left = integer;
		}
		result.add(money - left);

		System.out.print("每人金额:");
		System.out.println(result);

		// 验证分割后的数是否是输入的总金额
		Optional<Integer> r = result.stream().reduce(Integer::sum);
		System.out.print("总金额:");
		System.out.println(r.get());
		return result;
	}

小结

其实,如果你的项目中对指定的红包有特殊的要求,还可结合将三种算法结合起来进行使用。比如部分红包采用第二种,剩余红包采用第三种的形式来实现。



抢红包的三种算法插图

关注公众号:程序新视界,一个让你软实力、硬技术同步提升的平台

除非注明,否则均为程序新视界原创文章,转载必须以链接形式标明本文链接

本文链接:https://www.choupangxia.com/2020/04/15/grab-red-packet/