解析拼手气红包金额划分算法

本文主要是介绍解析拼手气红包金额划分算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

问题抽象
问题简化
思路一
思路二
思路三
结束语

“叮咚”，微信提示音响起，打开手机发现“相亲相爱一家人”的群里收到一个红包，天不负我，这一次终于抢到的金额终于说得过去了，虽然不是“运气王”，但有时候做个榜二也是一件很幸福的事情。

由红包引发的思考
红包的金额是如何划分的？红包的金额是怎么实现的完全随机呢？

问题抽象

将M元（M可以是两位数小数）的红包完全随机划分，最小分割单位为0.01元，分割成N份，且需要保证每人最少可领取到0.01元。

问题简化

将M乘100，最小分割单位变为1，N不变，这个问题就变成了一个纯整数的运算。

将M元（整数）的红包完全随机划分，最小分割单位为1元，分割成N份，且需要保证每人最少可领取到1元。

数据约定：（0 < M <= 10000; 0 < N <= M)

思路一

假设当前还有n个人未领取，红包剩余金额为m元
剩余的n个人按顺序领取，每个人可领取[1 ～（m - (n - 1))]区间的随机金额。
(m - (n - 1))用来确保剩余的n-1人最少可以领取到1元红包。

代码实现：

private static void randomRedPacket(int m, int n, int[] result){//当前已经有多少人领取过红包int index = result.length - n;//如果是最后一个人，则将红包剩余金额全部给这个人，并结束循环if(index == result.length - 1){result[index] = m;return;}//从剩下的金额中分配随机金额int randomValue = (int) (Math.random() * (m - (n - 1)) + 1);result[index] = randomValue;randomRedPacket(m - randomValue, n - 1, result);
}

运行结果：

解析：

当两个人平分红包的时候，看不出什么问题，当参与瓜分红包的人数多了之后，发现实际结果与期望的有所偏差.
以10人瓜分百元红包为例，回顾一下我们写的算法，其中的问题还是比较容易被发现的。
第一个抢红包的人，他的随机区间为[1, 91]元（给剩下的9人每人预留一元），在第一人抢到41元之后，第二个人的随机区间变为了[1, 51]元，以此类推，在第二个人抢到49元，第三个人抢到3元之后，从第四个人开始，他们的随机区间变为了[1, 1]，排在后边的人没有了选择，只能领取保底的一元了。
由此可见，这个算法并没有实现完全的随机，排在前边的人，他们的可选区间越大，抢到大红包的可能性越大，而排在后边的人，他们的可选区间受前人影响，在前人的大快朵颐之后，只能吃些残渣剩饭了。

思路二

认识到思路一的问题，我们不妨做一些改进。
N个人，每人先领取1元。剩余的(M - N)元分成（M - N）份，依次随机分发给N个人当中的一个。

代码实现：

private static void randomRedPacket(int m, int n, int[] result){//每人先领取一元低保Arrays.fill(result, 1);//将剩下的m-n元，随机分配个其中的一个人for (int i = 0; i < m - n; i++) {result[(int) (Math.random() * n)] += 1;}
}

运行结果：

解析：

OK!看似没什么问题了，实现了对第一个领取的人和最后领取的人的公平性，红包的金额已经完全不受领取顺序影响了。
但是，细心一点的话还会发现，这个算法并不完美，最终生成的红包金额都比较趋近于平均值，2人瓜分百元红包，生成的两个红包都比较趋近于50元，5人瓜分百元红包，每个红包的金额都比较趋近于20元，10人瓜分，每个红包都比较趋近于10元。如此一来，就失去了拼手气红包的乐趣。
那么，问题出在哪里呢？
结合数学当中的概率，将N个球放到n个箱子里，求其中的一个箱子里有m个球的概率。
由此发现，每个人分得平均值的概率最大，越偏离平均值的概率越小。

思路三

N个人，每人先领取1元。
剩余的(M - N)元分成(M - N)份，在[0, (M - N)]中生成(N - 1)个随机数作为随机位置。用这(N - 1)个随机位置将剩余的（M - N）元分成N份，依次分发给每个人。

代码实现：

private static void randomRedPacket(int m, int n, int[] result){//每人先领取一元低保Arrays.fill(result, 1);//初始化一个位置数组，用于存储随机位置int[] indexArr = new int[n - 1];int lastMoney = m - n;for (int i = 0; i < n - 1; i++) {int index = (int) (Math.random() * lastMoney);indexArr[i] = index;}//对分段的位置按照从小打到排序Arrays.sort(indexArr);//将n-1个位置切割成的n段，依次分配给n个人for (int i = 0; i < result.length; i++) {if(i == 0){result[i] += indexArr[i];}else if(i == n - 1){result[i] += lastMoney - indexArr[i - 1];}else{result[i] += indexArr[i] - indexArr[i - 1];}}
}

运行结果：

解析：

终于！出现了我们想要的结果，2个人抢个百元红包你即可能抢到1元，也可能抢到99元，还可能抢到其他任意金额，开红包的过程充满了期待，充满了惊喜。

调用入口：

public static void main(String[] args) {final int[] N = new int[]{2, 5, 10};final int M = 100;for (int n : N) {final int[] result = new int[n];System.out.printf("%s个人瓜分%s元红包!\n", n, M);randomRedPacket3(M, n, result);for (int i : result) {System.out.print(i + "\t");}System.out.println();}
}