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

yexiaobai 发布于2019-06-27 14:05 / 1008人阅读

这问题是@xinhaip从那边看来。
他之前的思路是这样子：

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

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

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

在我看来其实他一开始的思路恰恰是正确的，然而我在他的问题下面发布了答案，却没什么人赞同。
我只能在自己写个文章分析下我的解题思路。

题目

发一个随机红包，100块钱给10个人。每个人最多12块钱，最少6块钱。怎么分？

答案

设sum=100，n=10,则题目可以得到以下结论6n <= sum <= 12n。

设randNum为随机红包的大小，则可以推出6(n-1) <= (sum-randNum) <= 12(n-1)

从上面的结论里我们可以得到以下答案

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

进阶

上面的答案效率不是很高，其实我们可以通过计算红包的上下界，然后通过一次随机得到答案。
由6(n-1) <= (sum-randNum) <= 12(n-1)可得sum - 12(n-1) <= randNum <= sum - 6(n-1)。
又由6 <= randNum <= 12计算得到红包的上下界:

 $min = ($sum - 12 * ($i-1))>6?($sum - 12 * ($i-1)):6;
 $max = ($sum - 6 * ($i-1))<12?($sum - 6 * ($i-1)):12;

则最终答案是

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

根据种子生成序列,且符合期望

评论里说生成的序列不符合平均为10的期望,所以我们需要在返回结果结果前打乱序列。
最好还能根据种子生成每次都相同的结果，在这里我们要自定义shuffle函数。

function myShuffle(&$items,$seed) { 
    mt_srand($seed); 
    for ($i = count($items) - 1; $i > 0; $i--){ 
        $j = @mt_rand(0, $i); 
        $tmp = $items[$i]; 
        $items[$i] = $items[$j]; 
        $items[$j] = $tmp; 
    } 
} 

function makeSeq2($seed){
    mt_srand($seed);
    $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;
    }
    myShuffle($result,$seed);
    return $result;
}

云服务器 GPU云服务器免备案云服务器100块钱 10块钱的云服务器阿里云9块钱个人服务器几十块钱一个月的云服务器

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/21788.html

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

摘要：以前想过一个类似问题，就是没有每个人最大最小的得钱数的限制，以前的问题可以很好用随机数解决。于是这个问题也被以前的思想带坑里了，把突破口完全放在了如何处理每个人的随机数上。在与面试交谈中，明显有些紧张。以前想过一个类似问题，就是没有每个人最大、最小的得钱数的限制，以前的问题可以很好用随机数解决。于是这个问题也被以前的思想带坑里了，把突破口完全放在了如何处理每个人的随机数上。于是在...

toddmark 2019-06-27 14:06 评论0 收藏0
入职三天，公司给了100块钱叫我走人

摘要：初来乍到，请多多指教，踏入广州那一刻，我满怀热情的对广州说。本以为，作为大学毕业的我，在国内最大的软件服务商被寄予厚望的我，在广州应该也是个热饽饽，不愁吃不愁穿不愁的。然而现实是广州的公司对我并没有多多指教，而是多多抛弃。十月，金秋季节，本是丰收之时，却因为陆续有同事离职，心中多少有些悲凉之意，顿然想起从参加工作到现在，五年已过，当年青涩懵懂的小年轻，如今出街招摇过市时，被小孩子看到...

Chao 2019-08-16 13:24 评论0 收藏0
入职三天，公司给了100块钱叫我走人

摘要：初来乍到，请多多指教，踏入广州那一刻，我满怀热情的对广州说。本以为，作为大学毕业的我，在国内最大的软件服务商被寄予厚望的我，在广州应该也是个热饽饽，不愁吃不愁穿不愁的。然而现实是广州的公司对我并没有多多指教，而是多多抛弃。十月，金秋季节，本是丰收之时，却因为陆续有同事离职，心中多少有些悲凉之意，顿然想起从参加工作到现在，五年已过，当年青涩懵懂的小年轻，如今出街招摇过市时，被小孩子看到...

Karrdy 2019-08-02 11:43 评论0 收藏0
入职三天，公司给了100块钱叫我走人

摘要：初来乍到，请多多指教，踏入广州那一刻，我满怀热情的对广州说。本以为，作为大学毕业的我，在国内最大的软件服务商被寄予厚望的我，在广州应该也是个热饽饽，不愁吃不愁穿不愁的。然而现实是广州的公司对我并没有多多指教，而是多多抛弃。十月，金秋季节，本是丰收之时，却因为陆续有同事离职，心中多少有些悲凉之意，顿然想起从参加工作到现在，五年已过，当年青涩懵懂的小年轻，如今出街招摇过市时，被小孩子看到...

kgbook 2019-08-23 12:21 评论0 收藏0