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

Question

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

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

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

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

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

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

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

Answer 1

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

Answer 2

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

Answer 3

我从题目中获取的信息是这样的：
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]

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

Answer 4

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

Answer 5

根据楼主我实现一种

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

Answer 6

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

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

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
)

Answer 7

<?php

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

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

Answer 8

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

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

Answer 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的生成器可以简单的实现：

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

Answer 10

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

如果用 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)