Home >Backend Development >PHP Tutorial >Everyone is grabbing red envelopes, and programmers are studying red envelope algorithms and grabbing red envelopes_PHP Tutorial
Everyone is grabbing red envelopes, and programmers are studying red envelope algorithms and grabbing red envelopes_PHP Tutorial
- WBOYOriginal
- 2016-07-13 09:44:021036browse
Everyone is grabbing red envelopes, and programmers are studying red envelope algorithms to grab red envelopes and red envelopes
The total number of red envelopes sent by WeChat users throughout the day on New Year’s Eve reached 1.01 billion, and the number of shake interactions reached 1.01 billion. 11 billion times, and the peak red envelope sending volume is 810 million times/minute.
Putting aside the market value of WeChat red envelopes, the algorithm of the red envelopes themselves has also triggered heated discussions. Since the official has not given a clear statement, everyone has different opinions. The editor will also bring you some analysis below.
First look at the data analysis emperor
Most people make their own guesses, which is the only choice when they don’t know the internal random algorithm, but most people don’t give their own personal investigation results. Here is a survey sample data of 100 samples and put forward your own guess.
1. The wallet money satisfies the censored normal random number distribution. Roughly speaking, random numbers are taken from a censored normal distribution, and the summed number is divided by the total value to obtain the correction factor, and then the correction factor is multiplied by all the random numbers to obtain the red envelope value.
This distribution means: there are more red envelopes below the average, but not far from the average; there are few red envelopes above the average, but there are more red envelopes far greater than the average.
Figure 1. Wallet value and its frequency distribution histogram and its normal fitting
But looking at the distribution histogram, it cannot be inferred that it conforms to the normal distribution, but considering the simplicity of the program and the rationality of the random numbers, this is the most reasonable guess.
The wallets at the back are generally more valuable
Figure 2. Relationship curve between wallet sequence number and its value
From the linear fitting red line in Figure 2, we can see that the overall change trend of wallet value is slowly increasing, and its change range is approximately a "channel" delineated by the upper and lower bounds of the green dotted line. (The curve can be enclosed in such a conventional "channel", which also reflects the rationality of Rule 1 from the side and illustrates that random numbers are not uniformly distributed)
This pattern can also be seen from another plot of averages.
Figure 3. The change curve of the average with the number of sequences
In the sample, a wallet worth 1000 is divided into 100 parts, with an average value of 10. However, in Figure 3 we can see that before the last wallet, the average has been lower than 10, which shows that the value of the wallet at the beginning is low, and has been pulled upward by the value of the wallet in the later period. The value is higher.
3. Of course, the average graph can also reveal another rule, that is, the last person is often lucky enough to draw more. Because the last person gets whatever is left in their wallet, and the average of everyone before is less than 10, it is at least guaranteed that the last person will be higher than the average. In this sample, wallet number 98 drew 35, while the last wallet drew 46.
To sum up, guess based on the sample:
1. Most of the time, the money drawn is as small as others, but once it is more, it is much easier to get more.
2. The further you draw the back of your wallet, the easier it is to make money.
3. The last person is often prone to bad luck.
Comment: This is obviously a very practical difference. The editor only pays a few cents every time he grabs it.
The second student wrote a simple python code
According to observations, red envelope distribution meets the following points:
1. No one will not get money
2. It will not be distributed in advance
3. Money fluctuates widely
When the red envelope is initially created, the distribution plan is already set. When grabbing red envelopes, it’s just pop up one by one.
So the python code is as follows:
def weixin_divide_hongbao(money, n): divide_table = [random.randint(1, 10000) for x in xrange(0, n)] sum_ = sum(divide_table) return [x*money/sum_ for x in divide_table]
However, there are two small problems with the above algorithm:
1. Floating point precision issue
2. Processing of boundary values
The third student wrote a java version based on the python circulated on the Internet
int j=1;
while(j<1000)
{
int number=10;
float total=100;
float money;
double min=0.01;
double max;
int i=1;
List math=new ArrayList();
while(i<number)
{
max = total- min*(number- i);
int k = (int)((number-i)/2);
if (number -i <= 2)
{k = number -i;}
max = max/k;
money=(int)(min*100+Math.random()*(max*100-min*100+1));
money=(float)money/100;
total=total-money;
math.add(money);
System.out.println("第"+i+"个人拿到"+money+"剩下"+total);
i++;
if(i==number)
{
math.add(total);
System.out.println("第"+i+"个人拿到"+total+"剩下0");
}
}
System.out.println("本轮发红包中第"+(math.indexOf(Collections.max(math))+1)+"个人手气最佳");
j++;
}
The algorithm of the fourth student looks very scientific.
He thinks:
1. Everyone must be able to receive red envelopes;
2. The total amount of red envelopes received by each person = total amount;
3. The amount of red envelopes received by each person varies, but it cannot be too different, otherwise it will be uninteresting;
4. The algorithm must be simple, otherwise we will lose the reputation of Tencent;
正式编码之前，先搭建一个递进的模型来分析规律
设定总金额为10元，有N个人随机领取：
N=1
则红包金额=X元；
N=2
为保证第二个红包可以正常发出，第一个红包金额=0.01至9.99之间的某个随机数
第二个红包=10-第一个红包金额；
N=3
红包1=0.01至0.98之间的某个随机数
红包2=0.01至(10-红包1-0.01)的某个随机数
红包3=10-红包1-红包2
……
int j=1;
while(j<1000)
{
int number=10;
float total=100;
float money;
double min=0.01;
double max;
int i=1;
List math=new ArrayList();
while(i<number)
{
max = total- min*(number- i);
int k = (int)((number-i)/2);
if (number -i <= 2)
{k = number -i;}
max = max/k;
money=(int)(min*100+Math.random()*(max*100-min*100+1));
money=(float)money/100;
total=total-money;
math.add(money);
System.out.println("第"+i+"个人拿到"+money+"剩下"+total);
i++;
if(i==number)
{
math.add(total);
System.out.println("第"+i+"个人拿到"+total+"剩下0");
}
}
System.out.println("本轮发红包中第"+(math.indexOf(Collections.max(math))+1)+"个人手气最佳");
j++;
}
输入一看，波动太大，这数据太无趣了！
第1个红包：7.48 元，余额：2.52 元
第2个红包：1.9 元，余额：0.62 元
第3个红包：0.49 元，余额：0.13 元
第4个红包：0.04 元，余额：0.09 元
第5个红包：0.03 元，余额：0.06 元
第6个红包：0.03 元，余额：0.03 元
第7个红包：0.01 元，余额：0.02 元
第8个红包：0.02 元，余额：0 元
改良一下，将平均值作为随机安全上限来控制波动差
int j=1;
while(j<1000)
{
int number=10;
float total=100;
float money;
double min=0.01;
double max;
int i=1;
List math=new ArrayList();
while(i<number)
{
max = total- min*(number- i);
int k = (int)((number-i)/2);
if (number -i <= 2)
{k = number -i;}
max = max/k;
money=(int)(min*100+Math.random()*(max*100-min*100+1));
money=(float)money/100;
total=total-money;
math.add(money);
System.out.println("第"+i+"个人拿到"+money+"剩下"+total);
i++;
if(i==number)
{
math.add(total);
System.out.println("第"+i+"个人拿到"+total+"剩下0");
}
}
System.out.println("本轮发红包中第"+(math.indexOf(Collections.max(math))+1)+"个人手气最佳");
j++;
}
输出结果见下图
第1个红包：0.06 元，余额：9.94 元
第2个红包：1.55 元，余额：8.39 元
第3个红包：0.25 元，余额：8.14 元
第4个红包：0.98 元，余额：7.16 元
第5个红包：1.88 元，余额：5.28 元
第6个红包：1.92 元，余额：3.36 元
第7个红包：2.98 元，余额：0.38 元
第8个红包：0.38 元，余额：0 元
小结：
小编觉得这完全可以理解成一个红包引发的血案，小编仅仅列举了几个，还有一些工程学的同学直接抛出了数学模型、离散函数等等，但是无论算法是简单还是复杂，玩的开心就够了。