二倍均值法(公平版)
发出一个固定金额的红包,由若干个人来抢,需要满足哪些规则?
1、所有人抢到金额之和等于红包金额,不能超过,也不能少于。
2、每个人至少抢到一分钱。
3、要保证所有人抢到金额的几率相等。
假设剩余红包金额为M,剩余人数为N,那么有如下公式:
每次抢到的金额 = 随机区间 (0, M / N × 2)
这个公式,保证了每次随机金额的平均值是相等的,不会因为抢红包的先后顺序而造成不公平。举个例子:
假设有10个人,红包总额100元。100/10×2 = 20, 所以第一个人的随机范围是(0,20 ),平均可以抢到10元。假设第一个人随机到10元,那么剩余金额是100-10 = 90 元。90/9×2 = 20, 所以第二个人的随机范围同样是(0,20 ),平均可以抢到10元。假设第二个人随机到10元,那么剩余金额是90-10 = 80 元。80/8×2 = 20, 所以第三个人的随机范围同样是(0,20 ),平均可以抢到10元。以此类推,每一次随机范围的均值是相等的。
static void Main(string[] args) { for (int i = 0; i < 10; i++) { var list = DivideRedPackage(100* 100, 10); Console.WriteLine(string.Join(",", list)); int count = 0; foreach (var item in list) { count += item; } Console.WriteLine(count); } System.Console.ReadKey(); } /// <summary> /// 产生红包数组 /// </summary> /// <param name="cashCount">红包总金额,单位分</param> /// <param name="peopleNumber">红包人数</param> /// <returns></returns> static List<int> DivideRedPackage(int cashCount, int peopleNumber) { List<int> redPackageList = new List<int>(); if (cashCount <= peopleNumber) { for (int i = 0; i < cashCount; i++) { redPackageList.Add(1); } return redPackageList; } Random random = new Random(GetRandomSeed()); int restCash = cashCount, restPeople = peopleNumber; for (int i = 0; i < peopleNumber - 1; i++) { var cash = random.Next(1, restCash / restPeople * 2); restCash -= cash; restPeople--; redPackageList.Add(cash); } redPackageList.Add(restCash); return redPackageList; }
例如,产生的结果如下:
1960,189,234,1763,1211,1236,1340,53,1652,362 10000 1032,1380,456,1885,608,857,1541,452,1273,516 10000 976,955,749,936,1990,1177,781,325,527,1584 10000 794,935,272,216,2034,522,455,2313,2260,199 10000 1376,1539,1292,614,443,1874,889,544,821,608 10000 914,15,877,1738,604,932,321,983,3106,510 10000 659,791,800,1066,788,908,991,2473,495,1029 10000 1256,733,1385,667,1192,1237,455,105,2121,849 10000 1941,1173,567,1280,1558,618,183,644,133,1903 10000 1313,735,1198,1173,1288,522,1879,1155,59,678 10000
上述示例中需注意,Random是一个伪随机数生成器,在大多数 Windows 系统上,Random 类 (System) | Microsoft Docs 15 毫秒内创建的对象可能具有相同的种子值。
因此,如果New Random在循环中使用,就必须提供随机的种子值。
我们可以使用RNGCryptoServiceProvider 类 (System.Security.Cryptography) | Microsoft Docs类产生随机树种子。
具体代码如下:
/// <summary> /// 产生加密的随机数种子值 /// </summary> /// <returns></returns> static int GetRandomSeed() { byte[] bytes = new byte[4]; System.Security.Cryptography.RNGCryptoServiceProvider rng = new System.Security.Cryptography.RNGCryptoServiceProvider(); rng.GetBytes(bytes); return BitConverter.ToInt32(bytes, 0); }
线段切割法(手速版)
算法思路如下:
线段分割法就是把红包总金额想象成一条线段,而每个人抢到的金额,则是这条主线段所拆分出的子线段。
当N个人一起抢红包的时候,就需要确定N-1个切割点。
因此,当N个人一起抢总金额为M的红包时,我们需要做N-1次随机运算,以此确定N-1个切割点。
随机的范围区间是(1, M)。当所有切割点确定以后,子线段的长度也随之确定。这样每个人来抢红包的时候,只需要顺次领取与子线段长度等价的红包金额即可。
需要注意一下两点:
1、每个人至少抢到一分钱。
2、分割的线段如果重复需要重新切割
具体代码如下:
class Program { static List<int> DivideRedPackage(int cashCount, int peopleNumber) { List<int> redPackageList = new List<int>(); if (cashCount <= peopleNumber) { for (int i = 0; i < cashCount; i++) { redPackageList.Add(1); } return redPackageList; } Random random = new Random(GetRandomSeed()); int restPeople = peopleNumber; List<int> lineList = new List<int>(); while (restPeople > 1) { var line = random.Next(1, cashCount); if (lineList.Contains(line) == false) { lineList.Add(line); restPeople--; } } lineList.Sort(); redPackageList.Add(lineList[0]); for (int i = 0; i < peopleNumber - 2; i++) { var cash = lineList[i + 1] - lineList[i]; redPackageList.Add(cash); } redPackageList.Add(cashCount - lineList[lineList.Count - 1]); return redPackageList; } static int GetRandomSeed() { byte[] bytes = new byte[4]; System.Security.Cryptography.RNGCryptoServiceProvider rng = new System.Security.Cryptography.RNGCryptoServiceProvider(); rng.GetBytes(bytes); return BitConverter.ToInt32(bytes, 0); } static void Main(string[] args) { for (int i = 0; i < 10; i++) { var list = DivideRedPackage(100 * 100, 10); Console.WriteLine(string.Join(",", list)); int count = 0; foreach (var item in list) { count += item; } Console.WriteLine(count); } System.Console.ReadKey(); } }
输出结果如下:
409,2233,1843,546,983,679,1621,460,369,857 10000 50,472,281,603,577,1007,3929,38,591,2452 10000 194,1241,675,209,3507,1714,1199,596,313,352 10000 2127,578,16,2413,1332,586,91,260,465,2132 10000 1015,1421,963,626,3031,955,171,1112,60,646 10000 118,352,1062,1128,8,374,1879,1707,1755,1617 10000 2805,592,391,90,1468,392,2201,40,1426,595 10000 145,251,2910,59,1065,235,2761,997,1564,13 10000 814,1725,1886,39,696,202,44,992,3099,503 10000 828,1281,2402,579,380,2246,154,855,564,711 10000