Home > Backend Development > PHP Tutorial > Interview question: Send a random red envelope of 100 yuan to 10 people. The maximum price per person is 12 yuan, and the minimum price is 6 yuan. How to divide?

Interview question: Send a random red envelope of 100 yuan to 10 people. The maximum price per person is 12 yuan, and the minimum price is 6 yuan. How to divide?

WBOY
Release: 2016-08-04 09:20:10
Original
3714 people have browsed it

I thought about a similar problem before, that is, there is no limit on the maximum and minimum amount of money that each person can get. The previous problem can be easily solved with random numbers.

So this problem was also trapped by the previous thinking, and the breakthrough was completely focused on how to deal with everyone's random numbers.

So I didn’t solve this problem during the interview. I calmed down until the end of the interview, thought about it carefully, and found that my idea was wrong.

I think the correct idea is: everyone gets 6 yuan first, so that 40 yuan is left. Then take out one yuan each time and randomly distribute it to a person. If a person’s money reaches the upper limit, then this person You won't be eligible to get money next time. This is done until all the remaining money is distributed.

Of course, some optimizations can be done in the actual processing of the interface. For example, the remaining money can be randomly allocated each time (of course, this randomness must be subject to some restrictions to avoid over-allocation at once), and then if someone has money +The money randomly distributed this time>The upper limit of each person, then he is not eligible to get this money.

Random distribution is also easy to implement. First calculate how many people are eligible to get the money, and then count them one by one to decide which qualifies people.

This is my idea. If you have better ideas, please let me know. Thanks.

Reply content:

I thought about a similar problem before, that is, there is no limit on the maximum and minimum amount of money that each person can get. The previous problem can be solved easily with random numbers.

So this problem was also trapped by the previous thinking, and the breakthrough was completely focused on how to deal with everyone's random numbers.

So I didn’t solve this problem during the interview. I calmed down until the end of the interview, thought about it carefully, and found that my idea was wrong.

I think the correct idea is: everyone gets 6 yuan first, so that 40 yuan is left. After that, one yuan is taken out each time and randomly allocated to a person. If a person's money reaches the upper limit, then this person You won't be eligible to get money next time. This is done until all the remaining money is distributed.

Of course, some optimizations can be done in the actual processing of the interface. For example, the remaining money can be randomly allocated each time (of course, this randomness must be subject to some restrictions to avoid over-allocation at once), and then if someone has money +The money randomly distributed this time>The upper limit of each person, then he is not eligible to get this money.

Random distribution is also easy to implement. First calculate how many people are eligible to get the money, and then count them one by one to decide which qualifies people.

This is my idea. If you have better ideas, please let me know. Thanks.

<code>$cash = 40;
$user_arr = array(6,6,6,6,6,6,6,6,6,6);
while($cash>0){
    $user_id = rand(0, 9);
    if($user_arr[$user_id]<12){
        $user_arr[$user_id]++;
        $cash--;
    }
}

;
var_dump($user_arr,array_sum($user_arr));die;</code>
Copy after login
<code>性能篇
$arr1=range(2,6);
shuffle($arr1);
$arr2=range(2,6);
shuffle($arr2);
$user_arr = array(6,6,6,6,6,6,6,6,6,6);
 for ($i=0;$i<10;$i++){
     
     if($i<=4){
         $user_arr[$i] += $arr1[$i];
     }else{
         $j = $i%5;
         $user_arr[$i] += $arr2[$j];
         
     }
 }
var_dump($user_arr,array_sum($user_arr));die;</code>
Copy after login

<code><?php
//总钱数
$allMoney = 100;
//人数
$peopleNum = 10;
//红包结果
$result = [];
//随机生成10个红包
for ($i=0;$i<$peopleNum;$i++){
    $result[$i] = mt_rand(6,12);
}
//取结果总钱数差
$diff = array_sum($result) - $allMoney;
$absDiff = abs($diff);
//多退少补
for($i=0;$i<$absDiff;$i++) {
    foreach ($result as $key => $value) {
        if ($diff > 0) {
            $value--;
            if ($value >= 6) {
                $result[$key] = $value;
                break;
            }
        } elseif ($diff < 0) {
            $value++;
            if ($value <= 12) {
                $result[$key] = $value;
                break;
            }
        } else {
            break 2;
        }
    }
}

//输出红包结果
var_dump($result);
//输出红包总钱数
var_dump(array_sum($result));</code>
Copy after login

Maybe it’s complicated to write, this is what comes to mind suddenly.

There are simpler and cruder ones, which are also efficient.

<code><?php
function makePaper()
{
    $result = [];
    for ($i=0;$i<10;$i++){
        $result[$i] = mt_rand(6,12);
    }
    
    if (array_sum($result) != 100) {
        return makePaper();
    }
    
    return $result;
}</code>
Copy after login

The last one is accurate enough to be divided into units. Both of the above methods can be modified in this way. All quantities except the number of people are multiplied by one hundred, and then divided by one hundred.

<code><?php

function makePaper($allMoney = 100, $peopleNum = 10, $min = 6, $max = 12)
{
    $result = [];
    for ($i=0;$i<10;$i++){
        $result[$i] = mt_rand($min*100,$max*100);
    }
    
    if (array_sum($result) != $allMoney*100) {
        return makePaper();
    }
    
    return array_map(function($money){
        return bcdiv($money,100,2);
    },$result);
}

$result = makePaper();
var_dump($result);
var_dump(array_sum($result));</code>
Copy after login

I wrote so much and still got rejected without giving a reason. what's the situation?

I wrote something with a very different idea. . . It feels a bit cumbersome, but the efficiency and scalability are acceptable.

Idea: After each allocation, make sure the remaining money is within a reasonable range.
If it is reasonable, make the next allocation
Otherwise, make this allocation again.

<code><?php

function hongbao($money, $people, $min, $max)
{
    $result = [];
    for ($i=0; $i < $people; $i++) { 
        do {
            // 1.进行本次分配
            $result[$i] = mt_rand($min*100, $max*100) / 100; 
            // 2.本次分配后,剩余人数
            $restPeople = $people - ($i+1);    
            // 3.本次分配后,剩余金钱
            $restMoney  = $money - array_sum(array_slice($result, 0, $i+1)); 
            // 4.本次分配后,剩余金钱是否在合理范围? 不在则重新分配
        } while ($restMoney > $restPeople * $max || $restMoney < $restPeople * $min);
    }
    return $result;
}

$result = hongbao(100, 10, 6, 12);
// 验证
var_dump($result);
var_dump(array_sum($result));</code>
Copy after login

Run result:
Interview question: Send a random red envelope of 100 yuan to 10 people. The maximum price per person is 12 yuan, and the minimum price is 6 yuan. How to divide?

My idea is to use recursion to achieve it, the code is as follows:

<code> 
//rem,当前递归层次还有多少个数没有生成,$total生成总量,在这个项目中为40,$must必须达到的数据,$arr,临时变量用来保存和传递用
  //返回类型,$arr,即生成的随机数组
function test($rem, $total, $must, $arr)
      {
          if($rem>=2)
          {
              $rem -= 1;
              //$min本轮生成随机数的最小值是多少
              $min = round($must - $rem * 6 , 2);
              if($min<=0)
                  $min =0;
              $max = ($must > 6) ? 6 : $must;
              $rand = round(mt_rand($min*100, $max*100)/100 , 2);
              $arr[] = $rand;              
              $must = $must - $rand;
              echo "生成rand数值:".$rand;
              echo "--剩余随机次数:".$rem."----必须达成数据:".$must;
              echo "<br>";
              return test($rem, $total, $must, $arr);
          }else{
              $arr[] = $must;
              return $arr;
          }

      }
      $arr = array();
      $brr = test(10, 40, 40,$arr);
      //以后如果我想得到5个人分20块钱,也可以直接调用
      //test(5,20,20,$arr)即可
      print_r($brr);
      </code>
Copy after login

The final generated result is as follows:

<code>生成rand数值:0.41--剩余随机次数:9----必须达成数据:39.59
生成rand数值:0.81--剩余随机次数:8----必须达成数据:38.78
生成rand数值:5.72--剩余随机次数:7----必须达成数据:33.06
生成rand数值:2.51--剩余随机次数:6----必须达成数据:30.55
生成rand数值:1.25--剩余随机次数:5----必须达成数据:29.3
生成rand数值:5.34--剩余随机次数:4----必须达成数据:23.96
生成rand数值:5.98--剩余随机次数:3----必须达成数据:17.98
生成rand数值:5.99--剩余随机次数:2----必须达成数据:11.99
生成rand数值:6--剩余随机次数:1----必须达成数据:5.99
Array ( [0] => 0.41 [1] => 0.81 [2] => 5.72 [3] => 2.51 
[4] => 1.25 [5] => 5.34 [6] => 5.98 [7] => 5.99 [8] => 6 [9] => 5.99 )</code>
Copy after login

X is the value that has been drawn
Y is the number of people that have been drawn

思路:
因为100块分10个人,可选范围是6到12。所以可以随机地在6~12分给全部人就可以了。但可能会出现派不完或者不够分的情况,所以实际上每个人的选择区间不一定是6~12,也取决于先抽到钱的人。假如他们都抽到的金额接近总体平均值,那么这个区间就会保持在6~12,假如连续开头三个人都抽到6,那么第四个人的区间就会缩小,下限会提高。然而一旦她抽到了12,又会让下一位的选择区间变大了一点。但总体来看,越接近尾声,选择区间会缩小,直到最后一个人选择时,他的选择上限和下限是恰好相等的。所以用图来描述这个动态区间,比较有意思的是像一种时间线流动一样,从最底三层都是6~12,6~12,6~12,然后后面会随着具体的数值发生变化,你也永远无法知道下一个数是什么。

这里满足四个条件:
1.剩余金额除以人数不能大于12
2.剩余金额除以人数不能小于6
3.每个人都只能在6~12里选
4.总金额100分为10个人

m为总金额,n为人数,min选择下限,max为选择上限,用方程式

方程式为 min <= (m-x-z)/(n-y-1) <= max,配平就可以

下面是已经配平的式子,式子分别为上限和下限。上限可大于12时,配成12,否则保留。下限同理。

我不懂php,用python来代替:
(我的代码写得很不pythonic请不要吐槽,位数采用默认的很多位小数,根据实际情况再进行削减)

<code>#encoding=utf8

from random import uniform

def flag(m, n, min, max):
    x = 0
    y = 0
    L = []
    for i in range(n):
        top = 12
        bottom = 6
        if not m-x-min*(n-y-1) >= 12:
            top = m-x-min*(n-y-1)
        if not m-x-max*(n-y-1) <= 6:
            bottom = m-x-max*(n-y-1)
        next = uniform(bottom, top)
        x += next
        y += 1
        L.append(next)
    return L
    
print flag(100, 10, 6, 12)
print sum(flag(100, 10, 6, 12))

</code>
Copy after login

优点是,我得出下一位数永远时即时运算的,它不是得出一个既定的组合,然后再分配给每一个人。而是根据前面的情况,即时产生下一个结果。在具体用户上,当然是没有区别,但我在思考红包这个玩意的时候,也很自然觉得要是提前分好一个模式给我,那其实下一个数是什么早有了定论,程序员log一下就能知道是什么,那样就不好玩了。另外红包派不完的情况下,我无需去记录已经分配好的模式又在过期后对它进行删除的操作。这里在随机前进行判断来缩小区间,比随即后判断是否满足条件要好那是因为,选择出来的数符合逐渐变小的区间可能性会越来越低,结果在数据规模更大时,性能会下降严重。而先判断出上下区间则保证整个计算过程长度不变,都是常数级。

缺点是,如果不作另外的解释和运算,根本不知道上面这是在算什么,思路也不明了。

=================

更新,有评论提到越后抽越多money的问题,是的:

这个是因为人均10元,下限6元比平均低4元,上限12元才高2元,不对称同时金额分10人最高只有12这个空间“拉得很紧”,所以前三个都是100%在6~12所以无问题,后面就出问题了。这样有一个问题,就是出现了明显的规律,越后面越可能大。

毕竟这里均值达到10,每抽到1个人抽到6就需要2个人抽到12来弥补,所以要么让它更为集中到10,要么分散到2端,同时后面那端要比前者的高很多,而均匀分布是不可能的。因为这里涉及到红包,红包分定额和随机两种。集中分布可以说是固定金额的近似值,所以一定要做两端分布,两端分布可以在区间随机前对区间进行权重选择再随机就能操控,另外,也可以每次随机都生成10次数据,然后再从中抽取一个出来,其他删掉,第二个人抽再根据第一个数据生成第二个数列一直到结束,就能做到“分布均匀”,但题目中的数据限制还是很多人会抽到很大的数,的确在所难免。

集中化只要为每个数据根据它的位置乘上相关系数解决。或者直接设为10,然后设定“随机抖动”= = 。

因为数学的好处所以这个性能完全是常数级的,执行步数每次都是一样的,不存在要把自己的算法的性能也连同一起和所需生成的数据一起来随机玩概率的问题。所以想要两端分布同时随机分布这里可以在最后生成的答案里加上随机选一个就能达到效果。但算法之外是这个抢红包的问题,到底是集中还是分散分布?或许很多人抢时最后的红包才大还是好事情,抢早了,红包小了,迟了,被抢光了,最后一个是最危险的也是概率上金额最大的那一个,有意思不?或者说,我喜欢平均一点,既要和某人玩随机金额才刺激,还要避免某人抽得太小而尴尬?所以最后还得看实际需求怎样才能决定。

PS:看到题主的评论,题主的思路有人提到是随机到6块这种的概率很低,假如真的如此(偷懒没试过),那算法直觉就是集中化趋势的过程了。没有好坏,只是看需求如何。

就是每个人都减去6块钱,这样问题就转变成40块分给10个人,没人不多于6块钱。这样做的核心是,把两个限制变成了一个限制,因为分到的钱一定是正数,所以大于0这个限制变得简单了。

剩下的分,在总钱数大于6块的时候,只要做一个0到6的随机就可以,小于6块的时候,做0到这个总数的随机就可以,最后一个人拿剩下的。

当剩余红包金额小于等于12 * 剩余红包个数且大于等于6 * 剩余红包个数,则将随机数加入到结果中.

<code>function makeSeq(){
    $n = 10;
    $sum = 100;
    $result = [];
    while ($n > 1) {
        // 6n <= sum <=12n
        $randNum = mt_rand(600,1200) / 100;
        if(($sum-$randNum) >= 6* ($n - 1) && ($sum-$randNum) <= 12* ($n - 1)){
            $sum -= $randNum;
            $n -= 1;
            $result[] = $randNum;
        }
    }
    $result[] = $sum;
    return $result;
}

print_r(makeSeq());
print_r(array_sum(makeSeq()));</code>
Copy after login

7.20更新高新能版

<code>function makeSeq2(){
    $n = 10;
    $sum = 100;
    $result = [];
    for($i=$n;$i>=1;$i--){
        $min = ($sum - 12 * ($i-1))>6?($sum - 12 * ($i-1)):6;
        $max = ($sum - 6 * ($i-1))<12?($sum - 6 * ($i-1)):12;
        $randNum = mt_rand($min,$max);
        $sum -= $randNum;
        $result[] = $randNum;
    }
    return $result;
}</code>
Copy after login

Interview question: Send a random red envelope of 100 yuan to 10 people. The maximum price per person is 12 yuan, and the minimum price is 6 yuan. How to divide?

一个do while循环就能解决的问题,搞那么复杂。

<code class="php"><?php

$money  = 40;
$people = array_fill(0, 10, 6);

do {

    $lucky_index = mt_rand(0, 9);
    $lucky_money = floatval(substr(mt_rand() / mt_getrandmax(), 0, 4));

    if($people[$lucky_index]+$lucky_money >= 12)
        continue;

    if($money < 1) {
        $m = $money;
    } else {
        $m = $lucky_money;
    }

    $people[$lucky_index] += $m;
    $money -= $m;

} while($money > 0);

print_r($people);

?>

                            
            </p>
<p class="answer fmt" data-id="1020000006002198">
                                    </p>
<p>你的想法基本靠谱,我认为可以这样分:<br>1.先每人分6元,还剩下40元。<br>2.起一个循环,每人分0-(12-他已有的钱)元随机,直到钱分完为止。<br>没有题主讲的这么麻烦的。</p>
                            
            <p class="answer fmt" data-id="1020000006003348">
                                    </p>
<pre class="brush:php;toolbar:false"><code>$arr = [];
for ($i=0; $i < 9; $i++) { 
    $arr[] = mt_rand(6,12);
}
array_push($arr, 100 - array_sum($arr));
var_dump($arr);
var_dump(array_sum($arr));</code>
Copy after login

先每个人分6分,然后把剩下的钱再分
这个时候取10个随机值(0-9)随意,然后取各个值在随机值总和的百分比,分别乘以剩下的10000-60;Math.ceil或者Math.floor都可以
最后一个值防止取ceil时溢出,直接用10000-60-前面九个数的和即可
然后分别加上6,换算即可

<code> <?php
    // 1.初始化,平均分配每人$initAvgMoney(根据限制条件随机产生)
    // 2.每人随机拿出一定金额到共享资金池中,进行重新分配
    // 限制条件:$initAvgMoney应满足条件:"小宝"一分钱也不放入共享资金池("特自私"),其余九人拿出尽可能多的钱到共享资金池(每人只留6元)的情况下,共享资金池平均分配后小宝的钱也不超过12块

    header("Content-type:text/html;charset=utf-8");
    $minInitAvgMoney = 600;
    // ($maxInitAvgMoney - 600) * 9 / 10 + $maxInitAvgMoney <= 1200;
    $maxInitAvgMoney = floor(1740 / 1.9);
    echo("maxInitAvgMoney:");var_dump($maxInitAvgMoney);
    
    $initAvgMoney = mt_rand($minInitAvgMoney, $maxInitAvgMoney) ;
    echo("initAvgMoney:");var_dump($initAvgMoney);
    
    $maxMinus = $initAvgMoney - 600;
    echo("maxMinus:");var_dump($maxMinus);
    
    
    $moneyArr = array();
    for($i = 0; $i < 10; $i ++){
        $randMinusArr[$i] = mt_rand(0, $maxMinus / 10) * 10;
        // echo("randMinusArr-{$i}");var_dump($randMinusArr[$i]);
        $moneyArr[$i] = $initAvgMoney - $randMinusArr[$i];
    }
    
    
    $randMinusSum = 10000 - $initAvgMoney * 10 + array_sum($randMinusArr);
    
    $avgAddMoney = $randMinusSum / 10;
    
    for($i = 0; $i < 10; $i ++){
        $moneyArr[$i] = ($moneyArr[$i] + $avgAddMoney) / 100;
    }
    
    echo "最终结果:";var_dump($moneyArr);
    echo "结果验证:";var_dump(array_sum($moneyArr));
    // 感觉还有可以完善的地方,先这样吧
</code>
Copy after login

<code>min = 6;
max = 12;
total = 100;
pe = 10;
maxTotal = max*pe - total;

list = array();
for (0<pe)
    if(maxTotal>0)
        temp = random(0,maxTotal>=6?6:maxTotal);
        maxTotal-=temp;
        list.push(12-temp);
        
if(maxTotal>0)
    pre = maxTotal/pe;
    for (0<pe)list[temp2]+=pre;
 
shuffle(list);
</code>
Copy after login

此方法是错误的,没有强迫症,不修改了

半夜看到这个问题,忽然想到二分法那种模式,于是搞了一个解决方案,先讲思路。
1.先将人分为两半,左半人分的总金额最少是左半人数x最少金额总金额-右半人数x最多金额两个数字中较大的;
2.左半人分的总金额最多是左半人数x最多金额总金额-右半人数x最少金额两个数字中较小的;
3.在这个范围内取随机数作为分给左半人的金额,然后将问题递归为左半人分钱和右半人分钱。
py代码(直接以分为单位,数字都是整数):

<code>import random

def deliver(sum_of_money,num_of_people,min_of_money,max_of_money):
    if num_of_people==1:
        arr = [sum_of_money]
        return arr
    else:
        half = num_of_people>>1
        border_left = max(min_of_money*half,(sum_of_money-(num_of_people-half)*max_of_money))
        border_right = min(max_of_money*half,(sum_of_money-(num_of_people-half)*min_of_money))
        sum_of_left = random.randint(border_left,border_right)
        arr_left = deliver(sum_of_left,half,min_of_money,max_of_money)
        arr_right = deliver(sum_of_money-sum_of_left,num_of_people-half,min_of_money,max_of_money)
        return arr_left+arr_right
        
list = deliver(10000,10,600,1200)
print list</code>
Copy after login

根据题主的思路写了这样的一个答案

<code class="javascript">function faHongBao(money, pe, min, max) {
    var sum = money,
        result = [];

    for(var i=0; i<pe; i++) {
        result.push(min);
        sum -= min;
    }

    while(sum > 0) {
        var ran = Math.floor( Math.random() * (pe - 1) );
        if(result[ran] < max) {
            result[ran]++;
            sum--;
        }
    }

    return result;
}</code>
Copy after login

Interview question: Send a random red envelope of 100 yuan to 10 people. The maximum price per person is 12 yuan, and the minimum price is 6 yuan. How to divide?

<code>
static void Main(string[] args)
        {
            int all = 100;//总金额
            int person = 10;//人数
            double min = 8;//最小金额
            double max = 12;//最大金额

            double[] array = new double[person];//分配结果集
            int i = 0;//第几人
            Random ran = new Random();

            //默认分配最小值
            for (i = 0; i < person; i++)
            {
                array[i] = min;
            }

            double yet = min * person;//已分配金额

            int whileTimes = 0;//记录循环次数
            while (yet < all)
            {
                double thisM = Math.Round((ran.NextDouble() * (max - min - 1)), 2);
                i = ran.Next(0, person);
                if (yet + thisM > all)
                {
                    thisM = all - yet;
                }

                if (array[i] + thisM < max)//判断是否超出最大金额
                {
                    array[i] += thisM;
                    yet += thisM;
                }
                whileTimes++;
            }


            Console.Write("共循环{0}次\r\n", person + whileTimes);
            yet = 0;
            for (i = 0; i < person; i++)
            {
                yet += array[i];
                Console.Write("第{0}人=>分配{1}元,合计分配{2}元\r\n", i + 1, array[i], yet);
            }
            Console.Read();

        }
</code>
Copy after login

<code>function roundmoney()
    {
        $cash=100;
    
        for ($i = 0; $i < 10; $i++) {
            $people[$i]=rand(6,12);
            $cash=$cash-$people[$i];
            if($cash==0&&$i==9)
            {
                return $people;
            }
        }
        return false;
    
    }
    while(true)
    {
        if(($res=roundmoney())!=false)
        {
            var_dump($res);
            break;
        }
    
    }</code>
Copy after login

感觉有点粗暴,就是完全让计算机随机分,什么时候刚好分够10个人并且每个人不少于6不大于10 就停止

<code>function microtime_float(){
    list($usec, $sec) = explode(" ", microtime());
    return ((float)$usec + (float)$sec);
}

function getRandParcent(){
    return rand(1,10)/rand(10,100);  
}


function randUserMoney($cash,$min=6,$max=12){
    $cash_ini = $cash;
    $user_arr = array($min,$min,$min,$min,$min,$min,$min,$min,$min,$min);
    $start = microtime_float();
    while($cash>0){
        $user_id = rand(0, 9);
        $rand_point = getRandParcent();
        if($user_arr[$user_id]<$max){
            $ing = microtime_float();
            if($ing-$start>0.01){
                return randUserMoney($cash_ini);
            }
            $rand_money = round($rand_point*$cash,2);
            $user_money = $user_arr[$user_id]+$rand_money ;
            if($user_money<$max){
                $user_arr[$user_id] = $user_money;
                $cash = $cash - $rand_money;
            }
        }
    }
    return [
    'user_money'=>$user_arr,
    'total_money'=>array_sum($user_arr),
    'excute_time'=>$ing-$start
    ];
}

var_dump(randUserMoney(40));

array (size=3)
  'user_money' => 
    array (size=10)
      0 => float 11.59
      1 => float 9.07
      2 => float 11.99
      3 => float 12
      4 => float 9.14
      5 => float 11.6
      6 => float 11.86
      7 => float 9.93
      8 => float 6
      9 => float 6.82
  'total_money' => float 100
  'excute_time' => float 0.004000186920166</code>
Copy after login

这个问题很简单,100块给10个人,那么平均数就是10,先随机一个6到12的数,如果小于10,那么剩下的钱除以9肯定平均数大于10,那就在10到12随机一个数,然后把剩下的钱除以8,如果平均数大于10继续在10到12里面随机,如果小于10,那么就在6到10之间随机,由此类推得到10个随机数。然后把这10个随机数打乱分给10个人。

我从题目中获取的信息是这样的:
1、总数是100;
2、10个人分;
3、最小6块;
4、最大12块;
5、红包分完(例如都是6块的情况不存在)。
思路:
先从总数中扣除最小红包,保证每个红包的最小基数,设置一个奖金池,奖金池等于总是减去保底红包;
每个人实际领到的红包 等于 红包基数 加上 从奖金池中获取的随机奖金;

随机奖金会判断当前奖金池数量 与 剩余人数之间的关系,决定最小奖金的大小:minSignal
① restNum * range <= restPool : 每个人得到最大奖金依然没有(刚好)分配完奖金:retrun range;
② (restNum-1) * range > restPool : 判断下一次剩余人员能否分配完奖金池,如果能,则本次随机区间在[0,range]
③ restNum range > restPool > (restNum-1) range : 不能,则随机区间在[restPool % range,range]

<code>function demo(total, min, max, num){
  var pool = total - min * num;
  var restNum = num ; // 剩余人数
  var restPool = pool; // 剩余奖金

  var minSignal = function(){ 
    var range = max - min; // 最大奖金
    return restNum * range > restPool ? (restNum-1) * range > restPool ? 0 : restPool % range : range ;
  };

  var dispatch = function (){
    var minS = minSignal();
    var temp = minS + Math.random() * ( max - min - minS);
    temp = temp > restPool ? restPool : temp; 
    restPool -= temp;
    return min + temp;
  }

  for(var i = 0; i < num; i++){  
    var prize = dispatch(); 
    restNum --; 
    console.log("第"+ (i+1) +"个人:" + prize ,"剩余奖金池:" + restPool);
  }
}

// 测试
demo(100, 6 , 12, 10)
2016-07-20 12:57:29.056 VM9998:19 第1个人:8.917007956230712 剩余奖金池:37.08299204376929
2016-07-20 12:57:29.056 VM9998:19 第2个人:11.711160108665778 剩余奖金池:31.371831935103508
2016-07-20 12:57:29.056 VM9998:19 第3个人:9.60431933144148 剩余奖金池:27.767512603662027
2016-07-20 12:57:29.057 VM9998:19 第4个人:9.005495062706432 剩余奖金池:24.762017540955597
2016-07-20 12:57:29.057 VM9998:19 第5个人:6.881776388287364 剩余奖金池:23.880241152668233
2016-07-20 12:57:29.057 VM9998:19 第6个人:11.477396582224884 剩余奖金池:18.40284457044335
2016-07-20 12:57:29.057 VM9998:19 第7个人:11.980543481582266 剩余奖金池:12.422301088861083
2016-07-20 12:57:29.057 VM9998:19 第8个人:10.577151778799255 剩余奖金池:7.845149310061829
2016-07-20 12:57:29.057 VM9998:19 第9个人:10.915993913333269 剩余奖金池:2.92915539672856
2016-07-20 12:57:29.057 VM9998:19 第10个人:8.92915539672856 剩余奖金池:0</code>
Copy after login

100元,给10人;范围6-12元
1,每人先发6元。 剩下每人最多还能分到6元。 剩下40元
2,如果按照整元分; 那么等价于40元分到60个槽。。。
3,如果要精确到分, 那么等价于40 00 分 分到 60 * 100个槽。。。

根据楼主我实现一种

<code>import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class RandomMoney {
    public static void main(String[] args) {
        int len = 10;
        float allMoney = 100;//总钱数
        float remainMoeny = 0;//剩余得钱数
        float randomMoney = 0;//随机生成得钱数![图片描述][1]
        float sumMoney = 0;//每次随机生产钱数得总和
        int index; //随机索引
        float oneMoney;//某一次随机得钱数
        List<Object> list = new ArrayList<Object>();
        Random  random = new Random();
        for (int i = 0; i < len; i++) {
            list.add(6f);
        }
        sumMoney = sumMoney(list ,len);
        Long star = System.nanoTime();//System.currentTimeMillis();
        while ((remainMoeny = allMoney - sumMoney) > 0) {
            //产生一个剩余钱下的随机数
            index = random.nextInt(10);
            //当剩余得钱数少于一角 就把剩下得随机给某一个
            if (remainMoeny < 1f&&remainMoeny > 0) {
                //某一个人的钱数
                oneMoney = (float)list.get(index)+(allMoney-sumMoney);
                if (oneMoney < 12f) {
                    list.set(index, oneMoney);
                    sumMoney = sumMoney(list, len);
                    System.out.println(list);
                    System.out.println(sumMoney);
                }
            }else {
                //随机生产得钱数
                randomMoney = random.nextInt((int)remainMoeny)+random.nextFloat();
                //某一个人得钱数
                oneMoney = (float)list.get(index)+randomMoney;
                if (oneMoney < 12f) {
                    list.set(index, oneMoney);
                    sumMoney = sumMoney(list , len);
                }
            }
        }
        long end = System.nanoTime();//System.currentTimeMillis();
        System.out.println(end-star);
    }
    public static float sumMoney(List<Object> list ,int len){
        float sumMoney = 0;
        for (int i = 0; i < len; i++) {
            sumMoney += (float)list.get(i);
        }
        return sumMoney;
    }
}</code>
Copy after login

Interview question: Send a random red envelope of 100 yuan to 10 people. The maximum price per person is 12 yuan, and the minimum price is 6 yuan. How to divide?

<code>function fhb($money,$num,$min,$max){
    $firstUse=$num*$min;
    $surplusMoney=$money-$firstUse;

    $arr=array();
    for($i=1;$i<=$num;$i++){
        $arr[]=$min;
    }

    $diff=$surplusMoney*100;
    while($diff>0){
        $randUid = rand(0, $num - 1);
        if($arr[$randUid]<$max){
            $arr[$randUid]+=0.01;
            $arr[$randUid]=number_format($arr[$randUid],2,'.','');
            $diff--;
        }
    }
    return $arr;
}

$a=fhb(100,10,6,12);</code>
Copy after login

此算法的特征是每个人分得比较均衡。

<code>Array
(
    [0] => 9.75
    [1] => 9.84
    [2] => 10.06
    [3] => 10.15
    [4] => 9.94
    [5] => 10.17
    [6] => 10.00
    [7] => 10.24
    [8] => 9.86
    [9] => 9.99
)</code>
Copy after login

<code>function hongbao($money, $people, $min, $max) {
    if($people * $min > $money || $people * $max < $money) {
        return false;
    }
    $result = [];
    for($i = 0;$i < $people; ++$i) {
        if($i == $people - 1) {
            $result[$i] = $money - array_sum($result);
            break;
        }
        $rand = mt_rand($min * 100, $max * 100)/100;
        while(!isset($result[$i])) {
            $restMoney = $money - array_sum($result) - $rand;
            if($restMoney > ($people - $i -1) * $max) {
                $rand += 1;
                $rand > $max && $rand = $max;
            } elseif($restMoney < ($people - $i - 1) * $min) {
                $rand -= 1;
            } else {
                $result[$i] = $rand;
            }
        }
    }
    return $result;
}

$result = hongbao(100, 10, 6, 12);
print_r($result);
print_r(array_sum($result));</code>
Copy after login

?>
整个算法时间复杂度比较稳定

<code><?php
function randMoney($totalMoney, $people, $max, $min)
{
    if ($max * $people < $totalMoney || $min * $people > $totalMoney) {
        throw new Exception("总金钱不可以大于最大值与人数的乘积,不可以小于最小值与人数的乘积", 1);
        return [];
    }

    $minRest   = round(($people * $max - $totalMoney) / ($people - 1), 2) + 0.01;
    $restMoney = $totalMoney;
    $result    = [];
    $time      = 0;
    while ($restMoney) {
        for ($i = 0; $i < $people; $i++) {
            $time++;
            if ($restMoney > 0) {
                if ($restMoney <= $min) {
                    $currenRand = $restMoney;
                } else {
                    $currenRand = $max - $min;
                }
                if ($restMoney <= $minRest) {
                    $rand = $restMoney;
                } else {
                    $rand = mt_rand(0.00, $currenRand * 100) / 100;
                }
                if (isset($result[$i])) {
                    if ($result[$i] + $rand <= $max) {
                        $result[$i] += $rand;
                        $restMoney -= $rand;
                    }
                } else {
                    $result[$i] = $min + $rand;
                    $restMoney -= $result[$i];
                }
                if (!$restMoney) {
                    break;
                }
            }
        }
    }
    return $result;
}

try {
    $result = randMoney(100, 10, 12, 6);
    var_dump($result);
    echo array_sum($result);
} catch (Exception $e) {
    echo $e->getMessage();
}</code>
Copy after login

按照平均法求出X和Y
X+10Y = 100;
X+Y<=12;
故X的值为20/9
(借鉴了上一位回答者的回答)

数学模型为:取随机数 x < s,范围为 [a, b],另一个条件是:
s-x:[(n-1)a, (n-1)b] ==> x: [s-(n-1)a, s-(n-1)b],
其中 s, n, a, b 分别是题中的 金额(100),人数(10),下限(6),上限(12)
php 没用过,用python的生成器可以简单的实现:

<code>import random

def hongbao(s, n, a, b):
    for i in range(n-1, -1, -1):
        x = random.randint(max(a, s-b*i), min(b, s-a*i))
        s -= x
        yield x</code>
Copy after login

相当于生成 10 个 [0, 6] 之间的随机数,并且让它们和为 40,然后再每个数加上 6 即可。

如果用 Python,可以这样实现:

<code class="python">import random

r = [6] * 10
for i in range(40):
    r[random.choice([i for i in range(10) if r[i] < 12])] += 1
print(r)</code>
Copy after login

如题,首先要获取大于6小于12的随机数,那么只要我们随机出0-6的随机数,并且加上6,就是符合要求的。
然后这个是红包,按照微信红包的需求来设计,那么随机数是有两位有效小数的。那么我们需要随机出0-600的随机数,然后除以100。
因为这种设计,所以随机出来的数值一定大于6,所以6这边边际问题,就解决了,只需要考虑12的情况。

随机出来一个数字,只要确保后面的n位数字的平均值不大于600就可以。


<code>$sum = 0;                 //生成随机数的和
$total = 4000;           //随机数总和不能大于4000
$num = 10;                //生成num个随机数
$factor_start = 0;             //优化算法效率,在一定情况下,提高系数,可以随机数的效率。
$factor_end = 600;             //后面能随机的值不够时,需要控制后面随机数的范围。
$rand_num = array();
foreach($i==1;$i<=$num;$i++){
    if($i==10){
      $rand_num[9] = 6 + ($total - $sum)/100;
      break;
    }
    do{
        $rand = mt_rand($factor_start,$factor_end);
        $tmp_sum = $sum + $rand;
        if((($total - $tmp_sum) / ($num - $i)) < 600){
            $sum  = $tmp_sum;
            $rand_num[] = 6 + $rand / 100;
            if($total - $sum<=600){
                $factor_end = $total - $sum;
            }
            break;
        }else{
            $factor_start += 100;
        }
    }while(true)
}
var_dump(shuffle($rand_num));                //重新打乱数组,并输出</code>
Copy after login

算法就是这样,结果一定是正确的。
算法中添加的$factor_start和$factor_end变量,就是为了提高算法效率。
假设前面的随机数都很小,那么后面的随机数就要大起来。这个时候就需要增大$factor_start,减少后面while循环次数,提高算法效率。

假设前面的随机数特别大,让后面的数,无法满足0,到600的随机,那么就通过$factor_end来控制。

<code> function rand_red($min,$max,$num,$count){
      $return=[];
      $shenyu=$count-($min*$num);//每个人分6块剩余的金额
       $rand_num=$max-$min;//最大分配
       $mt_rand_min=1;//剩余金额最小值 默认分1
      for($i=1;$i<=$num;$i++){
        $num_count=mt_rand($mt_rand_min,$rand_num);//随机分配金额 
        if($shenyu>$num_count){
       $shenyu=$shenyu-$num_count;
       $mt_rand_min=$shenyu/($num-$i);//计算剩余小值
       $red_num=$min+$num_count;//最少分配加上 max-min随机值
       $return[]=$red_num;
    }else{
      if($shenyu!==0){
      $red_num=$min+$shenyu;
      $shenyu=0;
       $return[]=$red_num;
      }else{
       $return[]=$rand_num;
    }
    }
    }
    return $return;
    }
    $arr=rand_red(6,12,10,100);
    var_dump($arr);
    var_dump(array_sum($arr));

借鉴了楼主思路  英文不好 变量命名不是很标准 别喷~ 期待更好随机性解析代码</code>
Copy after login

楼主的方法只能处理整数问题吧,题目中并没有交代一定是整数。
每次取随机的范围都是变化的
下限从6和(剩余钱数-12*(剩余人数-1))中取大的
上限从12和(剩余钱数-6*(剩余人数-1))中取小的
贴Java代码

<code>public class Allocation{
    public static final double Total = 100;
    public static final double Min = 6;
    public static final double Max = 12;
    public static final int peopleNum = 10;
    private static double money_left;

    public static double[] allocateMoney(){
        double[] result = new double[10];
        money_left = Total;
        double lowerBound = Min;
        double upperBound = Max;
        double money_now = 0;
        double sum = 0;
        for (int i = 0; i < peopleNum ; i++) {
            lowerBound = Min > money_left - Max*(peopleNum-i-1)?Min:(money_left - Max*(peopleNum-i-1));
            upperBound = Max < money_left - Min*(peopleNum-i-1)?Max:(money_left - Min*(peopleNum-i-1));
            money_now = (upperBound - lowerBound)*Math.random()+lowerBound;
            System.out.println((i+1)+" : " + money_now);
            result[i] = money_now;
            //verify
            sum += money_now;
            money_left = money_left - money_now;
        }
        //verify
        System.out.print("Total = " + sum);
        return result;
    }
    public static void main(String[] args) {
        allocateMoney();
    }
}
</code>
Copy after login

某次运行截图
Interview question: Send a random red envelope of 100 yuan to 10 people. The maximum price per person is 12 yuan, and the minimum price is 6 yuan. How to divide?

这么多人会,就我不会

Related labels:
php
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