C#实现抢红包算法

二倍均值法（公平版）

发出一个固定金额的红包，由若干个人来抢，需要满足哪些规则？

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,362100001032,1380,456,1885,608,857,1541,452,1273,51610000976,955,749,936,1990,1177,781,325,527,158410000794,935,272,216,2034,522,455,2313,2260,199100001376,1539,1292,614,443,1874,889,544,821,60810000914,15,877,1738,604,932,321,983,3106,51010000659,791,800,1066,788,908,991,2473,495,1029100001256,733,1385,667,1192,1237,455,105,2121,849100001941,1173,567,1280,1558,618,183,644,133,1903100001313,735,1198,1173,1288,522,1879,1155,59,67810000

上述示例中需注意，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,8571000050,472,281,603,577,1007,3929,38,591,245210000194,1241,675,209,3507,1714,1199,596,313,352100002127,578,16,2413,1332,586,91,260,465,2132100001015,1421,963,626,3031,955,171,1112,60,64610000118,352,1062,1128,8,374,1879,1707,1755,1617100002805,592,391,90,1468,392,2201,40,1426,59510000145,251,2910,59,1065,235,2761,997,1564,1310000814,1725,1886,39,696,202,44,992,3099,50310000828,1281,2402,579,380,2246,154,855,564,71110000