Maison  >  Questions et réponses  >  le corps du texte

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

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

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

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

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

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

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

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

高洛峰高洛峰2771 Il y a quelques jours6239

répondre à tous(41)je répondrai

  • 巴扎黑

    巴扎黑2017-04-11 09:56:50

    如题,首先要获取大于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来控制。

    répondre
    0
  • 黄舟

    黄舟2017-04-11 09:56:50

     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));
    
    借鉴了楼主思路  英文不好 变量命名不是很标准 别喷~ 期待更好随机性解析代码

    répondre
    0
  • 怪我咯

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

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

    我的总体思路是这样的:先均分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;
        } 

    困死了,不写了

    répondre
    0
  • PHP中文网

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

    作为热门问题 前端人员表示想过来贴个 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);

    répondre
    0
  • 伊谢尔伦

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

    楼主的方法只能处理整数问题吧,题目中并没有交代一定是整数。
    每次取随机的范围都是变化的
    下限从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();
        }
    }
    

    某次运行截图

    répondre
    0
  • 怪我咯

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

    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)

    répondre
    0
  • PHPz

    PHPz2017-04-11 09:56:50

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

    répondre
    0
  • 天蓬老师

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

    这么多人会,就我不会

    répondre
    0
  • Annulerrépondre