What are the rules for sending a fixed amount of red envelope to be grabbed by several people?
1. The sum of money grabbed by all the participants is equal to the red envelope amount, no more than, no less than.
2. Everyone gets at least a penny.
3. Make sure everyone has an equal chance of getting the money.
What kind of train of thought is small grey?
Amount grabbed per time = random interval (0, remaining amount)
Why do you say that? Let’s look at a chestnut:
Suppose there are 10 people and the red envelope amounts to 100 yuan.
The first person has a random range of ($0,100) and can grab an average of $50.
Let’s say the first person gets 50 dollars at random, then the remaining amount is 100 minus 50 = 50 dollars.
The second person has a random range of (0, 50 yuan) and can grab 25 yuan on average.
Let’s say the second person randomly gets $25, then the remaining amount is $50-25 = $25.
The third person has a random range of (0, 25 yuan) and can grab an average of 12.5 yuan.
And so on, each time the random range gets smaller and smaller.
Method 1: double mean method
If the amount of the remaining red envelope is M and the number of people remaining is N, the following formula can be obtained:
Amount of money captured = random interval (0, M/N X 2)
This formula ensures that the average value of each random amount is the same, and will not cause injustice because of the sequence of snatching red packets.
Here’s an example:
Suppose there are 10 people and the red envelope amounts to 100 yuan.
100/10×2 = 20, so the random range of the first person is (0,20), and the average person can grab 10 dollars.
If the first person gets 10 dollars at random, then the remaining amount is 100-10 = 90 dollars.
90/9 x2 = 20, so the random range of the second person is also (0,20), and the average person can grab 10 dollars.
Let’s say the second person gets 10 dollars at random, then the remaining amount is 90 minus 10 = 80 dollars.
80/8 x2 is 20, so the random range of the third person is also (0,20), and the average person can grab 10 dollars.
And so on, the mean of each random range is the same.
The program output is as follows:
Amount grabbed: 2.92
Amount grabbed: 1.48
Amount grabbed: 3.05
Amount grabbed: 0.53
Amount grabbed: 0.45
Amount grabbed: 1.36
Amount captured: 1.02
Amount grabbed: 1.99
Amount captured: 1.3
Amount captured: 0.48
Amount captured: 0.83
Amount grabbed: 2.89
Amount captured: 0.94
Amount grabbed: 2.11
Amount grabbed: 3.13
Amount grabbed: 0.91
Amount grabbed: 2.64
Amount grabbed: 2.02
Amount grabbed: 2.88
Amount grabbed: 1.13
Amount grabbed: 2.09
Amount grabbed: 1.37
Amount grabbed: 2.41
Amount grabbed: 2.13
Amount captured: 1.32
Amount captured: 0.44
Amount grabbed: 1.62
Amount grabbed: 1.89
Amount grabbed: 2.23
Amount captured: 0.44
Method 2: line segment cutting method
What is line segment cutting? We can think of the total amount of red packets as a long line segment, and the amount of money grabbed by each person is divided into several sublines of this main line segment.
How do you determine the length of each line segment? It’s determined by the cut point. When N people grab red envelopes together, n-1 cutting points need to be determined.
Therefore, when N people grab red packets with a total amount of M, we need to do n-1 random operations to determine n-1 cutting points. The random range is (1, M).
When all the cutting points are determined, the length of the subline segment is also determined. In this way, when each person comes to grab a red envelope, they only need to get the red envelope amount equal to the length of the subline.
So that’s the idea of line segment cutting. Two points to note here:
1. How to deal with the repetition of random cutting points.
2. How to reduce time and space complexity as much as possible.
— — the END — — –
If you like this article, please long click the picture below to follow the subscription number programmer Xiao Grey and watch more exciting content
