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

Question

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

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

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

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

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

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

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

Answer 1

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

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

---

$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));                //重新打乱数组，并输出

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

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

Answer 2

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

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

Answer 3

答案真多，也没仔细看， 不知道有没有和我一样想法的。

我的总体思路是这样的：先均分6块；再分析每个人得钱的随机范围；每个人依次得钱直至分完，一次就分完了。

1、每人至少6块，所以先分出60，剩下40。那剩下人的每个人能得到的初看是[0～6]；
2、反推。从最后一个人(第10个人)推起，到他时，剩下的钱必定是<=6，继续往前推一个，到他时，剩下的钱必定是<=12，然后依次类推（最好在纸上写一下）。这么推我们可以得出到第5个人得钱时，剩下的钱必定是<=36, 那么前4个人必须要分掉至少4块钱，以此再推，前5个人必定要分掉至少10块钱，至最后一个至少得分掉34块钱。这样通过找规律我们得出了每个人得钱的随机范围的第一个值。
3、虽然我们得出了每个人随机范围的第一个值，但并不是每一个人的随机范围的第二个值都是 6，因为当前面的几个人已经把大部分钱都分了的时候，后面的人就没得分了。这次，我们从第一个人开始往后推，当到第N个人时剩下的钱$R<6时，这个人所能分得的钱的随机范围第二个值就是剩下的钱$R，然后他后面的人所能分得的钱的随机范围的第二个值还是$R；

说明完毕，也不知道有没有说明白，还是直接上代码吧：

    $R = 40;    //剩余钱数
    $add_max = 12 - 6;
    $arr = array(6, 6, 6, 6, 6, 6, 6, 6, 6, 6);
    for($i = 0; $i<10; $i++) {
        //默认随机数是 0～6
        $rand = mt_rand(0, $add_max);
        //反推过程可以得出从第4个人开始，rand要么是以$diff为初始值，要么就是上一行的$rand;而随机范围第二个值由剩余钱$R决定。
        if($i > 2) {
            if($R <= 0) break;
            $diff = $R - (10 - $i - 1) * $add_max;
            $rand_end = $R < 6 ? $R : $add_max;
            $diff > 0 && ($rand =  mt_rand($diff, $rand_end));
        }

        $arr[$i] += $rand;
        $R -= $rand;
    }

    var_dump($arr,array_sum($arr));

这里得出的都是整型的，如果要得到浮点数，把rand函数替换成获得浮点数的随机函数就行。这是稍微精简后的，通俗过程：

    $R = 40;
    $add_max = 12 - 6;
    $arr = array(6, 6, 6, 6, 6, 6, 6, 6, 6, 6);
    for($i = 0; $i<10; $i++) {
        //根据反推，前三个是不用考虑随机范围的，从第4个人开始才需要考虑随机范围
        if($i < 3) {
            $rand = mt_rand(0, 6);
        } else if($i == 3) {
            //留给第5个人的不能超过36。当$rand_start不为0时，说明钱还很充足的。充足到第$i个人必须抽走一些钱才行。
            
            $rand_start = $R - 36 ? $R - 36 : 0;
            $rand = mt_rand($rand_start, 6);
        } else if($i == 4) {
            //留给第6个人的不能超过30.
            $rand_start = $R - 30 ? $R - 30 : 0;
            $rand = mt_rand($rand_start, 6);
        } else if($i == 5) {
            //留给第6个人的不能超过24.到现在为止，钱一定还是充足的，所以不用考虑第二个值。
            $rand_start = $R - 24 ? $R - 24 : 0;
            $rand = mt_rand($rand_start, 6);
        }

        //...

        else if($i == 6) {
            //通过上面得出留给下一个人的不能超过 (10-$i-1)*6;  然后到第7个人时，假设前面每个人都得到了6块，即只剩下4块钱时，随机范围第二个数就不再是6了，而是剩余数$R
            $rand_start = $R - 24 ? $R - 24 : 0;
            $rand_end = $R > 6 ? 6 : $R;
            $rand = mt_rand($rand_start, $rand_end);
        }

        //...

        $arr[$i] += $rand;
        $R -= $rand;
    } 

困死了，不写了

Answer 4

作为热门问题 前端人员表示想过来贴个 JavaScript版

//  100  10   max 12 min 6
var count = 0;
function getAmount(totalAmount,number,max,min){
    count++;

    var usedAmount = 0;
    var amountList = [];

    for(var i = 0; i< number-1; i++){
        var amount = parseFloat((Math.random()*(max-min)).toFixed(2));

        amountList[i] = amount;
        usedAmount += amount;
    }

    var balance = totalAmount - min*number - usedAmount;

    amountList[9] = balance;

    if(balance > (max-min) || balance < 0){
        getAmount(totalAmount,number,max,min);
    }else{
        usedAmount = 0;
        for(var i = 0; i< number; i++){
            redPacket[i] = (6 + amountList[i]).toFixed(2);
            usedAmount += parseFloat(redPacket[i]);
        }
        // 确认总额是否是100
        console.warn(usedAmount.toFixed(2));
        // 打印每个红包金额
        console.info(redPacket);
        console.info('计算次数：' + count);
    }
}
getAmount(100,10,12,6);

Answer 5

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

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

某次运行截图

Answer 6

import random
def pocket(total=100,num=10,min=6,max=12):
    result = []
    while num > 1:
        rand_num = round(random.uniform(min,max),2)
        left_money = total - rand_num

        if left_money > min * (num-1) and left_money < max * (num-1):
            result.append(rand_num)
            num -= 1
            total -= rand_num
    result.append(round(total,2))
    return result
result = pocket()
print result
print sum(result)

Answer 7

function markPacket($money=100,$people=10,$min=6,$max=12){
    $cash = $money-$people*$min;
    $packet_arr = [$min,$min,$min,$min,$min,$min,$min,$min,$min,$min];
    $i = 0;
    while($cash > 0){
        $people_rand = rand(0,($people-1));
        $money_rand = rand(0,($max-$min)*100)/100;
        $people_money = $packet_arr[$people_rand] + $money_rand;
        if($people_money > 12){
            continue;
        }
        if($money_rand > $cash){
            $people_money = $packet_arr[$people_rand] + $cash;
        }
        $packet_arr[$people_rand] = $people_money;
        $cash -= $money_rand;
        $i++;
    }
    var_dump($packet_arr,array_sum($packet_arr),$i);
}

Answer 8

这么多人会，就我不会