⾯试问题：发⼀个随机红包，100块钱给10个⼈。每个⼈最多12块钱，最少6块
钱。怎么分？
以前想过⼀个类似问题，就是没有每个⼈最⼤、最⼩的得钱数的限制，以前的问题可以很好⽤随机数解决。
于是这个问题也被以前的思想带坑⾥了，把突破⼝完全放在了如何处理每个⼈的随机数上。
于是在⾯试时间就没有解决这个问题，直到⾯试结束⾃⼰安静下来，仔细想想，发现思路错了。
我认为正确的思路是：每个⼈先得6块钱，这样剩下40块钱，之后每次拿出⼀块钱，随机分配给⼀个⼈，如果某个⼈的钱数达到了上限，那么这个⼈下次就没有了再得到钱的资格了。这样直到剩下钱都分配完。
当然在接⼝的实际处理上可以做些优化，例如剩下的钱每次随机分配的钱可以是随机的（当然这个随机要做⼀些限制，以免⼀下就分配超额了），然后如果某个⼈钱+这次随机分配的钱>每个⼈的上限，那么他就没有资格得到这个钱了。
随机分配也好实现，先算有⼏个⼈有资格得到这笔钱，随即⼀个数，决定给第⼏个符合资格的⼈。
我的思路就是这样，⼤家如果有更好的思路，请告知。谢谢。
$cash = 40;
function怎么记忆
$user_arr = array(6,6,6,6,6,6,6,6,6,6);
while($cash>0){
$user_id = rand(0, 9);
if($user_arr[$user_id]<12){
$user_arr[$user_id]++;
$cash--;
}
}
;
var_dump($user_arr,array_sum($user_arr));die;
性能篇
$arr1=range(2,6);
shuffle($arr1);
$arr2=range(2,6);
shuffle($arr2);
$user_arr = array(6,6,6,6,6,6,6,6,6,6);
for ($i=0;$i<10;$i++){
if($i<=4){
$user_arr[$i] += $arr1[$i];
}else{
$j = $i%5;
$user_arr[$i] += $arr2[$j];
}
}
var_dump($user_arr,array_sum($user_arr));die;
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));
借鉴了楼主思路英⽂不好变量命名不是很标准别喷~ 期待更好随机性解析代码
<?php
//总钱数
$allMoney = 100;
//⼈数
$peopleNum = 10;
//红包结果
$result = [];
//随机⽣成10个红包
for ($i=0;$i<$peopleNum;$i++){
$result[$i] = mt_rand(6,12);
}
/
/取结果总钱数差
$diff = array_sum($result) - $allMoney;
$absDiff = abs($diff);
//多退少补
for($i=0;$i<$absDiff;$i++) {
foreach ($result as $key => $value) {
if ($diff > 0) {
$value--;
if ($value >= 6) {
$result[$key] = $value;
break;
}
} elseif ($diff < 0) {
$value++;
if ($value <= 12) {
$result[$key] = $value;
break;
}
} else {
break 2;
}
}
}
//输出红包结果
var_dump($result);
//输出红包总钱数
var_dump(array_sum($result));
可能写复杂了，突然想到的就这样了。
还有更简单粗暴的，效率也还⾏。
<?php
function makePaper()
{
$result = [];
for ($i=0;$i<10;$i++){
$result[$i] = mt_rand(6,12);
}
if (array_sum($result) != 100) {
return makePaper();
}
return $result;
}
最后就是精确到分为单位的，上⾯两种⽅法都可以这么改造。除了⼈数所有数量乘以⼀百，运算完之后再除以⼀百。<?php
function makePaper($allMoney = 100, $peopleNum = 10, $min = 6, $max = 12)
{
$result = [];
for ($i=0;$i<10;$i++){
$result[$i] = mt_rand($min*100,$max*100);
}
if (array_sum($result) != $allMoney*100) {
return makePaper();
}
return array_map(function($money){
return bcdiv($money,100,2);
},$result);
}
$result = makePaper();
var_dump($result);
var_dump(array_sum($result));
写这么多还被踩，也不给个理由。什么情况？
我从题⽬中获取的信息是这样的：
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
我写了个思路迥异的。。。感觉有点⿇烦，不过效率和可扩展性还凑合。
思路：每次分配后，都确定剩余的⾦钱在合理范围。
若合理，进⾏下次分配
否则，重新进⾏此次分配。
<?php
function hongbao($money, $people, $min, $max)
{
$result = [];
for ($i=0; $i < $people; $i++) {
do {
/
/ 1.进⾏本次分配
$result[$i] = mt_rand($min*100, $max*100) / 100;
// 2.本次分配后，剩余⼈数
$restPeople = $people - ($i+1);
// 3.本次分配后，剩余⾦钱
$restMoney  = $money - array_sum(array_slice($result, 0, $i+1));
// 4.本次分配后，剩余⾦钱是否在合理范围？不在则重新分配
} while ($restMoney > $restPeople * $max || $restMoney < $restPeople * $min);
}
return $result;
}
$result = hongbao(100, 10, 6, 12);
// 验证
var_dump($result);
var_dump(array_sum($result));
运⾏结果：
<?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));
>
整个算法时间复杂度⽐较稳定
如题，⾸先要获取⼤于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来控制。
这个问题很简单，100块给10个⼈，那么平均数就是10，先随机⼀个6到12的数，如果⼩于10，那么剩下的钱除以9肯定平均数⼤于10，那就在10到12随机⼀个数，然后把剩下的钱除以8，如果平均数⼤于10继续在10到12⾥⾯随机，如果⼩于10，那么就在6到10之间随机，由此类推得到10个随机数。然后把这10个随机数打乱分给10个⼈。
我的想法是采⽤递归来实现，代码如下:
/
/rem，当前递归层次还有多少个数没有⽣成，$total⽣成总量，在这个项⽬中为40，$must必须达到的数据,$arr，临时变量⽤来保存和传递⽤
//返回类型,$arr，即⽣成的随机数组
function test($rem, $total, $must, $arr)
{
if($rem>=2)
{
$rem -= 1;
//$min本轮⽣成随机数的最⼩值是多少
$min = round($must - $rem * 6 , 2);
if($min<=0)
$min =0;
$max = ($must > 6) ? 6 : $must;
$rand = round(mt_rand($min*100, $max*100)/100 , 2);
$arr[] = $rand;
$must = $must - $rand;
echo "⽣成rand数值:".$rand;
echo "--剩余随机次数:".$rem."----必须达成数据:".$must;
echo "<br>";
return test($rem, $total, $must, $arr);
}else{
$arr[] = $must;
return $arr;
}
}
$arr = array();
$brr = test(10, 40, 40,$arr);
//以后如果我想得到5个⼈分20块钱，也可以直接调⽤
//test(5,20,20,$arr)即可
print_r($brr);
最后⽣成的结果如下：
⽣成rand数值:0.41--剩余随机次数:9----必须达成数据:39.59
⽣成rand数值:0.81--剩余随机次数:8----必须达成数据:38.78
⽣成rand数值:5.72--剩余随机次数:7----必须达成数据:33.06
⽣成rand数值:2.51--剩余随机次数:6----必须达成数据:30.55
⽣成rand数值:1.25--剩余随机次数:5----必须达成数据:29.3
⽣成rand数值:5.34--剩余随机次数:4----必须达成数据:23.96
⽣成rand数值:5.98--剩余随机次数:3----必须达成数据:17.98
⽣成rand数值:5.99--剩余随机次数:2----必须达成数据:11.99
⽣成rand数值:6--剩余随机次数:1----必须达成数据:5.99
Array ( [0] => 0.41 [1] => 0.81 [2] => 5.72 [3] => 2.51
[4] => 1.25 [5] => 5.34 [6] => 5.98 [7] => 5.99 [8] => 6 [9] => 5.99 )
相当于⽣成 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)
X为已经抽取的数值
Y为已经抽取的⼈数
思路：
因为100块分10个⼈，可选范围是6到12。所以可以随机地在6~12分给全部⼈就可以了。但可能会出现派不完或者不够分的情况，所以实际上每个⼈的选择区间不⼀定是6~12，也取决于先抽到钱的⼈。假如他们都抽到的⾦额接近总体平均值，那么这个区间就会保持在6~12，假如连续开头三个⼈都抽到6，那么第四个⼈的区间就会缩⼩，下限会提⾼。然⽽⼀旦她抽到了12，⼜会让下⼀位的选择区间变⼤了⼀点。但总体来看，越接近尾声，选择区间会缩⼩，直到最后⼀个⼈选择时，他的选择上限和下限是恰好相等的。所以⽤图来描述这个动态区间，⽐较有意思的是像⼀种时间线流动⼀样，从最底三层都是6~12,6~12,6~12，然后后⾯会随着具体的数值发⽣变化，你也永远⽆法知道下⼀个数是什么。
这⾥满⾜四个条件：
1.剩余⾦额除以⼈数不能⼤于12
2.剩余⾦额除以⼈数不能⼩于6
3.每个⼈都只能在6~12⾥选
4.总⾦额100分为10个⼈
m为总⾦额,n为⼈数，min选择下限，max为选择上限,⽤⽅程式
⽅程式为 min <= (m-x-z)/(n-y-1) <= max，配平就可以
下⾯是已经配平的式⼦，式⼦分别为上限和下限。上限可⼤于12时，配成12，否则保留。下限同理。
我不懂php，⽤python来代替：
（我的代码写得很不pythonic请不要吐槽，位数采⽤默认的很多位⼩数，根据实际情况再进⾏削减）
#encoding=utf8
from random import uniform
def flag(m, n, min, max):
x = 0
y = 0
L = []
for i in range(n):
top = 12
bottom = 6
if not m-x-min*(n-y-1) >= 12:
top = m-x-min*(n-y-1)
if not m-x-max*(n-y-1) <= 6:
bottom = m-x-max*(n-y-1)
next = uniform(bottom, top)
x += next
y += 1
L.append(next)
return L
print flag(100, 10, 6, 12)
print sum(flag(100, 10, 6, 12))
优点是，我得出下⼀位数永远时即时运算的，它不是得出⼀个既定的组合，然后再分配给每⼀个⼈。⽽是根据前⾯的情况，即时产⽣下⼀个结果。在具体⽤户上，当然是没有区别，但我在思考红包这个玩意的时候，也很⾃然觉得要是提前分好⼀个模式给我，那其实下⼀个数是什么早有了定论，程序员log⼀下就能知道是什么，那样就不好玩了。另外红包派不完的情况下，我⽆需去记录已经分配好的模
式⼜在过期后对它进⾏删除的操作。这⾥在随机前进⾏判断来缩⼩区间，⽐随即后判断是否满⾜条件要好那是因为，选择出来的数符合逐渐变⼩的区间可能性会越来越低，结果在数据规模更⼤时，性能会下降严重。⽽先判断出上下区间则保证整个计算过程长度不变，都是常数级。
缺点是，如果不作另外的解释和运算，根本不知道上⾯这是在算什么，思路也不明了。
=================
更新，有评论提到越后抽越多money的问题，是的：
这个是因为⼈均10元，下限6元⽐平均低4元，上限12元才⾼2元，不对称同时⾦额分10⼈最⾼只有12这个空间“拉得很紧”，所以前三个都是100%在6~12所以⽆问题，后⾯就出问题了。这样有⼀个问题，就是出现了明显的规律，越后⾯越可能⼤。
毕竟这⾥均值达到10，每抽到1个⼈抽到6就需要2个⼈抽到12来弥补，所以要么让它更为集中到10，要么分散到2端，同时后⾯那端要⽐前者的⾼很多，⽽均匀分布是不可能的。因为这⾥涉及到红包，红包分定额和随机两种。集中分布可以说是固定⾦额的近似值，所以⼀定要做两端分布，两端分布可以在区间随机前对区间进⾏权重选择再随机就能操控，另外，也可以每次随机都⽣成10次数据，然后再从中抽取⼀个出来，其他删掉，第⼆个⼈抽再根据第⼀个数据⽣成第⼆个数列⼀直到结束，就能做到“分布均匀”，但题⽬中的数据限制还是很多⼈会抽到很⼤的数，的确在所难免。
集中化只要为每个数据根据它的位置乘上相关系数解决。或者直接设为10，然后设定“随机抖动”= = 。
因为数学的好处所以这个性能完全是常数级的，执⾏步数每次都是⼀样的，不存在要把⾃⼰的算法的性能也连同⼀起和所需⽣成的数据⼀起来随机玩概率的问题。所以想要两端分布同时随机分布这⾥可以在最后⽣成的答案⾥加上随机选⼀个就能达到效果。但算法之外是这个抢红包的问题，到底是集中还是分散分布？或许很多⼈抢时最后的红包才⼤还是好事情，抢早了，红包⼩了，迟了，被抢光了，最后⼀个是最危险的也是概率上⾦额最⼤的那⼀个，有意思不？或者说，我喜欢平均⼀点，既要和某⼈玩随机⾦额才刺激，还要避免某⼈抽得太⼩⽽尴尬？所以最后还得看实际需求怎样才能决定。
PS：看到题主的评论，题主的思路有⼈提到是随机到6块这种的概率很低，假如真的如此（偷懒没试过），那算法直觉就是集中化趋势的过程了。没有好坏，只是看需求如何。
<?php
// 1.初始化，平均分配每⼈$initAvgMoney（根据限制条件随机产⽣）
// 2.每⼈随机拿出⼀定⾦额到共享资⾦池中，进⾏重新分配
// 限制条件：$initAvgMoney应满⾜条件："⼩宝"⼀分钱也不放⼊共享资⾦池（"特⾃私"），其余九⼈拿出尽可能多的钱到共享资⾦池（每⼈只留6元）的情况下，共享资⾦池平均分配后⼩宝的钱也不超过
12块    header("Content-type:text/html;charset=utf-8");
$minInitAvgMoney = 600;
// ($maxInitAvgMoney - 600) * 9 / 10 + $maxInitAvgMoney <= 1200;
$maxInitAvgMoney = floor(1740 / 1.9);