php - 面试问题：发一个随机红包，100块钱给10个人。每个人最多12块钱，最少6块钱。怎么分？

Question

以前想过一个类似问题，就是没有每个人最大、最小的得钱数的限制，以前的问题可以很好用随机数解决。

于是这个问题也被以前的思想带坑里了，把突破口完全放在了如何处理每个人的随机数上。

于是在面试时间就没有解决这个问题，直到面试结束自己安静下来，仔细想想，发现思路错了。

我认为正确的思路是：每个人先得6块钱，这样剩下40块钱，之后每次拿出一块钱，随机分配给一个人，如果某个人的钱数达到了上限，那么这个人下次就没有了再得到钱的资格了。这样直到剩下钱都分配完。

当然在接口的实际处理上可以做些优化，例如剩下的钱每次随机分配的钱可以是随机的（当然这个随机要做一些限制，以免一下就分配超额了），然后如果某个人钱+这次随机分配的钱>每个人的上限，那么他就没有资格得到这个钱了。

随机分配也好实现，先算有几个人有资格得到这笔钱，随即一个数，决定给第几个符合资格的人。

我的思路就是这样，大家如果有更好的思路，请告知。谢谢。

Answer 1

$money =[6,6,6,6,6,6,6,6,6,6];
$left=40; //最低6元,所以先每个6块钱分过去,剩40了
 
while($left!=0){
	 for($i=0;$i<=9;$i++){
		 $t=rand(0,(1200-$money[$i]*100))/100;//随机生成一个数,在0到自己离12多远的数之间
		 if($t>=$left){$t=$left;}//万一生成的数超过剩下的总值,就干脆全给他好了
		 $money[$i]=$money[$i]+$t;//加上
		 $left=$left-$t;//看看生成数后,总仓库还有多少
		 if ($left===0){exit ;}//仓库都没了的话就不用算了,直接结束掉
	 }
 
 }
print_r($money); 
print_r(array_sum($money));

这样的话感觉效率不会很高,但很少代码量....

万一那个生成数一直很小,是要循环很多次......

Answer 2

最简单示例：

$money = '';
while(array_sum($money)!=100) {
    for($i = 1; $i < 11; $i++) {
        $money[$i] = rand(5,11)+rand(1,99)/100;
    }
}
print_r($money);

Answer 3

这是我无意间看到的：不能理解随机安全上限 

$total=20;//红包总金额   $num=10;// 分成10个红包，支持10人随机领取   $min=0.01;//每个人最少能收到0.01元   
for ($i=1;$i<$num;$i++)   
{   
   $safe_total=($total-($num-$i)*$min)/($num-$i);//随机安全上限   
   $money=mt_rand($min*100,$safe_total*100)/100;   
   $total=$total-$money;  
    
   echo '第'.$i.'个红包：'.$money.' 元，余额：'.$total.' 元 ';   
}   
echo '第'.$num.'个红包：'.$total.' 元，余额：0 元';

Answer 4

$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;

性能篇
$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;

Answer 5

<?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));

可能写复杂了，突然想到的就这样了。

还有更简单粗暴的，效率也还行。

<?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;
}

最后就是精确到分为单位的，上面两种方法都可以这么改造。除了人数所有数量乘以一百，运算完之后再除以一百。

<?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 bcp($money,100,2);
    },$result);
}

$result = makePaper();
var_dump($result);
var_dump(array_sum($result));

写这么多还被踩，也不给个理由。什么情况？

Answer 6

我写了个思路迥异的。。。感觉有点麻烦，不过效率和可扩展性还凑合。

思路：每次分配后，都确定剩余的金钱在合理范围。
若合理，进行下次分配
否则，重新进行此次分配。

<?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));

运行结果：

Answer 7

我的想法是采用递归来实现，代码如下:

 
//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);
      

最后生成的结果如下 ：

生成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 )

Answer 8

X为已经抽取的数值
Y为已经抽取的人数

思路：
因为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请不要吐槽，位数采用默认的很多位小数，根据实际情况再进行削减）

#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))

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

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

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

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

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

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

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

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

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

Answer 9

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

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

Answer 10

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

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()));

7.20更新高新能版

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;
}