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

WBOY
Release: 2016-07-13 09:44:02
Original
1053 people have browsed it

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] 
Copy after login

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++; 
}
Copy after login
Copy after login

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++; 
} 
Copy after login

输入一看,波动太大,这数据太无趣了!

第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++; 
}
Copy after login
Copy after login

输出结果见下图

第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 元

小结:

小编觉得这完全可以理解成一个红包引发的血案,小编仅仅列举了几个,还有一些工程学的同学直接抛出了数学模型、离散函数等等,但是无论算法是简单还是复杂,玩的开心就够了。

www.bkjia.comtruehttp://www.bkjia.com/PHPjc/1050139.htmlTechArticle大家在抢红包,程序员在研究红包算法,抢红包红包 除夕全天微信用户红包总发送量达到10.1亿次,摇一摇互动量达到110亿次,红包峰值发...
Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template