跟你揭秘抢红包背后的算法
原创
又快到春节了，春节最幸福莫过于有红包收；而在某年因为手机抢红包而红遍大江南北的微信将春节加了一把火。那我们今天就来说说抢红包的机制及后面的算法。
首先抢红包必须要满足以下的条件：
1、所有人抢到的金额加起来必须等于红包的金额，不能少或多。这是必须的。
2、每个人的金额尽量平均，这样体现公平工作。但这个也不是必须。
3、要考虑到高并非的问题。
那有什么办法呢？
首先我想到的是当发红包时，立即进行划分，例如：100元，立即划分为5分，当然不能平均（100/5=20）这样肯定无法体现金额多少的乐趣。那怎么处理呢。。
我的思路是，首先将随机得到一个100以内的数值，然后减去，在剩余的随机，再随机。
using System;
using System.Collections;
namespace CSharpTest01
{
class Program
{
/// <summary>
/// 抢红包
/// </summary>
static Queue CutLineGetRedPacket(int money_YUAN, int peopleNum)
{
Queue moneyList_YUAN = new Queue();
//float[] moneyList_YUAN = new float[peopleNum];
int money_FEN = money_YUAN * 100; // 元转为分
int[] cutLineQueue = GetCutLineList(money_FEN, peopleNum);
int lastCutPoint = 0;
float curMoney_FEN = 0;
for (int i = 0; i < peopleNum - 1; i++)
{
int curCutPoint = cutLineQueue[i];
curMoney_FEN = curCutPoint - lastCutPoint;
//moneyList_YUAN[i] = curMoney_FEN/100;
moneyList_YUAN.Enqueue(curMoney_FEN / 100);
lastCutPoint = curCutPoint;
}
curMoney_FEN = money_FEN - lastCutPoint;
//moneyList_YUAN[peopleNum - 1] = curMoney_FEN / 100;
moneyList_YUAN.Enqueue(curMoney_FEN / 100);
return moneyList_YUAN;
}
/// <summary>
/// 切割法
/// </summary>
/// <returns>n个人,n-1个切割点</returns>
static int[] GetCutLineList(int money_FEN, int peopleNum)
{
int cutNum = peopleNum - 1;
int[] cutLineList = new int[cutNum];
Random random = new Random();
int cutPoint = 0;
int curListLen = 0;
while (cutNum > 0)
{
cutPoint = random.Next(1, money_FEN - 1);
if (CheckIsCutPointLegal(cutLineList, cutPoint))
{
InsertValueWithSort(ref cutLineList, curListLen, cutPoint);
curListLen++;
cutNum--;
}
}
return cutLineList;
}
private static void InsertValueWithSort(ref int[] cutList, int curListLen, int value)
{
bool isSwap = false;
int temp = 0;
int insertValue = value;
for (int i = 0; i < curListLen; i++)
{
if (isSwap)
{
temp = cutList[i];
cutList[i] = insertValue;
insertValue = temp;
}
if (value < cutList[i]&&!isSwap)
{
temp = cutList[i];
cutList[i] = insertValue;
insertValue = temp;
isSwap = true;
}
}
cutList[curListLen] = insertValue;
}
private static bool CheckIsCutPointLegal(int[] cutLineList, int cutPoint)
{
bool isLegal = true;
foreach (var item in cutLineList)
{
if (item == cutPoint)
{
isLegal = false;
break;
}
}
return isLegal;
}
static void Main(string[] args)
{
Console.WriteLine("Program Start:");
int money_YUAN = 10;
int peopleNum = 10;
Queue moneyList_YUAN = CutLineGetRedPacket(money_YUAN, peopleNum);
for (int i = 0; i < peopleNum; i++)
{
var value = moneyList_YUAN.Dequeue();
Console.WriteLine(value);
}
Console.WriteLine("Program End:");
}
}
}还是上代码吧。。当这个后我发现还有一个算法：
每次抢到的金额=随机区间[0.01, m/n x 2 - 0.01]元
这个比较简单点，至于行不行就各位自己测试了。。上代码
using System;
using System.Collections;
namespace CSharpTest01
{
class Program
{
public static Queue DivideRedPacket(float money_YUAN, int peopleNum)
{
Queue money_YUAN_Queue = new Queue();
int reset_FEN = (int)money_YUAN * 100;
int resetPeopleNum = peopleNum;
Random random = new Random();
for (int i = 0; i < peopleNum-1; i++)
{
// 随机范围：[1, 剩余人均金额的2倍-1]分
int curMoney_FEN = random.Next(1, reset_FEN/resetPeopleNum * 2 - 1);
money_YUAN_Queue.Enqueue((float)curMoney_FEN / 100);
reset_FEN -= curMoney_FEN;
resetPeopleNum--;
}
money_YUAN_Queue.Enqueue((float)reset_FEN / 100);
return money_YUAN_Queue;
}
static void Main(string[] args)
{
Console.WriteLine("Program Start:");
float money_YUAN = 10.00f;
int peopleNum = 10;
Queue moneyList_YUAN = DivideRedPacket(money_YUAN, peopleNum);
for (int i = 0; i < peopleNum; i++)
{
var value = moneyList_YUAN.Dequeue();
Console.WriteLine(value);
}
Console.WriteLine("Program End:");
}
}
}为什么要写这篇文字呢，是因为这种算法很多时候需要用到。所以就留个脚印吧。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
作者已关闭评论
推荐阅读