首頁  >  問答  >  主體

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

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

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

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

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

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

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

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

高洛峰高洛峰2771 天前6244

全部回覆(41)我來回復

  • PHP中文网

    PHP中文网2017-04-11 09:56:50

    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

    回覆
    0
  • PHP中文网

    PHP中文网2017-04-11 09:56:50

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

    回覆
    0
  • 天蓬老师

    天蓬老师2017-04-11 09:56:50

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

    回覆
    0
  • 伊谢尔伦

    伊谢尔伦2017-04-11 09:56:50

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

    回覆
    0
  • 阿神

    阿神2017-04-11 09:56:50

    根据楼主我实现一种

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

    回覆
    0
  • 怪我咯

    怪我咯2017-04-11 09:56:50

    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
    )

    回覆
    0
  • 迷茫

    迷茫2017-04-11 09:56:50

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

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

    回覆
    0
  • 知了停啼

    你寫的這個演算法經過我的測試,發現有極大的機率出現12塊

    知了停啼 · 2018-04-20 14:47:47
  • 大家讲道理

    大家讲道理2017-04-11 09:56:50

    <?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
    (借鉴了上一位回答者的回答)

    回覆
    0
  • 天蓬老师

    天蓬老师2017-04-11 09:56:50

    数学模型为:取随机数 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

    回覆
    0
  • 大家讲道理

    大家讲道理2017-04-11 09:56:50

    相当于生成 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)

    回覆
    0
  • 取消回覆