ホームページ >バックエンド開発 >PHPチュートリアル >面接の質問: 100 元の赤い封筒を 10 人にランダムに送ります。 1人当たりの最高料金は12元、最低料金は6元です。分割方法は?

面接の質問: 100 元の赤い封筒を 10 人にランダムに送ります。 1人当たりの最高料金は12元、最低料金は6元です。分割方法は?

WBOY
WBOYオリジナル
2016-08-04 09:20:103714ブラウズ

私は以前、同様の問題について考えました。つまり、各人が取得できる最大および最小の金額に制限はありません。前の問題は乱数を使用して簡単に解決できます。

つまり、この問題も以前の考え方に囚われており、その打開策は完全に全員の乱数をどう扱うかに焦点が当てられていました。

だから私は面接中にこの問題を解決できなかったのですが、面接が終わるまで落ち着いてよく考えてみたら、自分の考えが間違っていたことが分かりました。

正しい考えは次のとおりです。最初に全員が 6 元を獲得し、残りが 40 元になるようにします。その後、毎回 1 元を取り出し、ランダムに誰かに分配します。誰かのお金が上限に達したら、その人が勝ちます。次回お金を受け取る資格はありません。これは、残りのお金がすべて分配されるまで行われます。

もちろん、インターフェイスの実際の処理でいくつかの最適化を行うことができます。たとえば、残りのお金を毎回ランダムに割り当てることができます (もちろん、一度に過剰な割り当てを避けるために、このランダム性にはいくつかの制限が適用されます)。そして、誰かがお金を持っている場合 + 今回ランダムに配布されたお金> 各人の上限であれば、その人はこのお金を受け取る資格はありません。

ランダムな分配も簡単に実装できます。まず、お金を受け取る資格がある人の数を計算し、次にその人数を数えて、どの

人に渡すかを決定します。 符合资格

これは私のアイデアです。もっと良いアイデアがあれば、ぜひ教えてください。ありがとう。

返信内容:

私は以前、同様の問題について考えました。つまり、各人が取得できる最大および最小の金額に制限はありません。前の問題は乱数を使用して簡単に解決できます。

つまり、この問題も以前の考え方に囚われており、その打開策は完全に全員の乱数をどう扱うかに焦点が当てられていました。

だから私は面接中にこの問題を解決できなかったのですが、面接が終わるまで落ち着いてよく考えてみたら、自分の考えが間違っていたことが分かりました。

正しい考えは次のとおりです。最初に全員が 6 元を獲得し、残りが 40 元になるようにします。その後、毎回 1 元を取り出し、ランダムに誰かに分配します。誰かのお金が上限に達したら、その人が勝ちます。次回お金を受け取る資格はありません。これは、残りのお金がすべて分配されるまで行われます。

もちろん、インターフェイスの実際の処理でいくつかの最適化を行うことができます。たとえば、残りのお金を毎回ランダムに割り当てることができます (もちろん、一度に過剰な割り当てを避けるために、このランダム性にはいくつかの制限が適用されます)。そして、誰かがお金を持っている場合 + 今回ランダムに配布されたお金> 各人の上限であれば、その人はこのお金を受け取る資格はありません。

ランダムな分配も簡単に実装できます。まず、お金を受け取る資格がある人の数を計算し、次にその人数を数えて、どの

人に渡すかを決定します。

符合资格これは私のアイデアです。もっと良いアイデアがあれば、ぜひ教えてください。ありがとう。

リーリー リーリー

リーリー

書くのは難しいかもしれませんが、これが突然頭に浮かびます。

より単純で粗雑なものもありますが、それらも効率的です。

リーリー

最後の方法は、ユニットに分割できるほど正確です。上記の方法はどちらもこの方法で変更できます。人数を除くすべての数量は、100 倍され、100 で割られます。

リーリー

こんなに書いたのに、理由も言わずに批判を受けました。状況はどうですか?

私は全く異なる考えで何かを書きました。 。 。少し面倒に感じますが、効率性と拡張性は許容範囲内です。

アイデア: 各割り当ての後、残りのお金が妥当な範囲内であることを確認します。

妥当な場合は、次の割り当てを実行します。

そうでない場合は、この割り当てを再度実行します。
リーリー
実行結果:


面接の質問: 100 元の赤い封筒を 10 人にランダムに送ります。 1人当たりの最高料金は12元、最低料金は6元です。分割方法は?

私のアイデアは、再帰を使用してそれを実現することです。コードは次のとおりです:

リーリー

最終的に生成された結果は次のとおりです:

リーリー

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请不要吐槽,位数采用默认的很多位小数,根据实际情况再进行削减)

<code>#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))

</code>

优点是,我得出下一位数永远时即时运算的,它不是得出一个既定的组合,然后再分配给每一个人。而是根据前面的情况,即时产生下一个结果。在具体用户上,当然是没有区别,但我在思考红包这个玩意的时候,也很自然觉得要是提前分好一个模式给我,那其实下一个数是什么早有了定论,程序员log一下就能知道是什么,那样就不好玩了。另外红包派不完的情况下,我无需去记录已经分配好的模式又在过期后对它进行删除的操作。这里在随机前进行判断来缩小区间,比随即后判断是否满足条件要好那是因为,选择出来的数符合逐渐变小的区间可能性会越来越低,结果在数据规模更大时,性能会下降严重。而先判断出上下区间则保证整个计算过程长度不变,都是常数级。

缺点是,如果不作另外的解释和运算,根本不知道上面这是在算什么,思路也不明了。

=================

更新,有评论提到越后抽越多money的问题,是的:

这个是因为人均10元,下限6元比平均低4元,上限12元才高2元,不对称同时金额分10人最高只有12这个空间“拉得很紧”,所以前三个都是100%在6~12所以无问题,后面就出问题了。这样有一个问题,就是出现了明显的规律,越后面越可能大。

毕竟这里均值达到10,每抽到1个人抽到6就需要2个人抽到12来弥补,所以要么让它更为集中到10,要么分散到2端,同时后面那端要比前者的高很多,而均匀分布是不可能的。因为这里涉及到红包,红包分定额和随机两种。集中分布可以说是固定金额的近似值,所以一定要做两端分布,两端分布可以在区间随机前对区间进行权重选择再随机就能操控,另外,也可以每次随机都生成10次数据,然后再从中抽取一个出来,其他删掉,第二个人抽再根据第一个数据生成第二个数列一直到结束,就能做到“分布均匀”,但题目中的数据限制还是很多人会抽到很大的数,的确在所难免。

集中化只要为每个数据根据它的位置乘上相关系数解决。或者直接设为10,然后设定“随机抖动”= = 。

因为数学的好处所以这个性能完全是常数级的,执行步数每次都是一样的,不存在要把自己的算法的性能也连同一起和所需生成的数据一起来随机玩概率的问题。所以想要两端分布同时随机分布这里可以在最后生成的答案里加上随机选一个就能达到效果。但算法之外是这个抢红包的问题,到底是集中还是分散分布?或许很多人抢时最后的红包才大还是好事情,抢早了,红包小了,迟了,被抢光了,最后一个是最危险的也是概率上金额最大的那一个,有意思不?或者说,我喜欢平均一点,既要和某人玩随机金额才刺激,还要避免某人抽得太小而尴尬?所以最后还得看实际需求怎样才能决定。

PS:看到题主的评论,题主的思路有人提到是随机到6块这种的概率很低,假如真的如此(偷懒没试过),那算法直觉就是集中化趋势的过程了。没有好坏,只是看需求如何。

就是每个人都减去6块钱,这样问题就转变成40块分给10个人,没人不多于6块钱。这样做的核心是,把两个限制变成了一个限制,因为分到的钱一定是正数,所以大于0这个限制变得简单了。

剩下的分,在总钱数大于6块的时候,只要做一个0到6的随机就可以,小于6块的时候,做0到这个总数的随机就可以,最后一个人拿剩下的。

当剩余红包金额小于等于12 * 剩余红包个数且大于等于6 * 剩余红包个数,则将随机数加入到结果中.

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

print_r(makeSeq());
print_r(array_sum(makeSeq()));</code>

7.20更新高新能版

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

面接の質問: 100 元の赤い封筒を 10 人にランダムに送ります。 1人当たりの最高料金は12元、最低料金は6元です。分割方法は?

一个do while循环就能解决的问题,搞那么复杂。

<code class="php"><?php

$money  = 40;
$people = array_fill(0, 10, 6);

do {

    $lucky_index = mt_rand(0, 9);
    $lucky_money = floatval(substr(mt_rand() / mt_getrandmax(), 0, 4));

    if($people[$lucky_index]+$lucky_money >= 12)
        continue;

    if($money < 1) {
        $m = $money;
    } else {
        $m = $lucky_money;
    }

    $people[$lucky_index] += $m;
    $money -= $m;

} while($money > 0);

print_r($people);

?>

                            
            </p>
<p class="answer fmt" data-id="1020000006002198">
                                    </p>
<p>你的想法基本靠谱,我认为可以这样分:<br>1.先每人分6元,还剩下40元。<br>2.起一个循环,每人分0-(12-他已有的钱)元随机,直到钱分完为止。<br>没有题主讲的这么麻烦的。</p>
                            
            <p class="answer fmt" data-id="1020000006003348">
                                    </p>
<pre class="brush:php;toolbar:false"><code>$arr = [];
for ($i=0; $i < 9; $i++) { 
    $arr[] = mt_rand(6,12);
}
array_push($arr, 100 - array_sum($arr));
var_dump($arr);
var_dump(array_sum($arr));</code>

先每个人分6分,然后把剩下的钱再分
这个时候取10个随机值(0-9)随意,然后取各个值在随机值总和的百分比,分别乘以剩下的10000-60;Math.ceil或者Math.floor都可以
最后一个值防止取ceil时溢出,直接用10000-60-前面九个数的和即可
然后分别加上6,换算即可

<code> <?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);
    echo("maxInitAvgMoney:");var_dump($maxInitAvgMoney);
    
    $initAvgMoney = mt_rand($minInitAvgMoney, $maxInitAvgMoney) ;
    echo("initAvgMoney:");var_dump($initAvgMoney);
    
    $maxMinus = $initAvgMoney - 600;
    echo("maxMinus:");var_dump($maxMinus);
    
    
    $moneyArr = array();
    for($i = 0; $i < 10; $i ++){
        $randMinusArr[$i] = mt_rand(0, $maxMinus / 10) * 10;
        // echo("randMinusArr-{$i}");var_dump($randMinusArr[$i]);
        $moneyArr[$i] = $initAvgMoney - $randMinusArr[$i];
    }
    
    
    $randMinusSum = 10000 - $initAvgMoney * 10 + array_sum($randMinusArr);
    
    $avgAddMoney = $randMinusSum / 10;
    
    for($i = 0; $i < 10; $i ++){
        $moneyArr[$i] = ($moneyArr[$i] + $avgAddMoney) / 100;
    }
    
    echo "最终结果:";var_dump($moneyArr);
    echo "结果验证:";var_dump(array_sum($moneyArr));
    // 感觉还有可以完善的地方,先这样吧
</code>

<code>min = 6;
max = 12;
total = 100;
pe = 10;
maxTotal = max*pe - total;

list = array();
for (0<pe)
    if(maxTotal>0)
        temp = random(0,maxTotal>=6?6:maxTotal);
        maxTotal-=temp;
        list.push(12-temp);
        
if(maxTotal>0)
    pre = maxTotal/pe;
    for (0<pe)list[temp2]+=pre;
 
shuffle(list);
</code>

此方法是错误的,没有强迫症,不修改了

半夜看到这个问题,忽然想到二分法那种模式,于是搞了一个解决方案,先讲思路。
1.先将人分为两半,左半人分的总金额最少是左半人数x最少金额总金额-右半人数x最多金额两个数字中较大的;
2.左半人分的总金额最多是左半人数x最多金额总金额-右半人数x最少金额两个数字中较小的;
3.在这个范围内取随机数作为分给左半人的金额,然后将问题递归为左半人分钱和右半人分钱。
py代码(直接以分为单位,数字都是整数):

<code>import random

def deliver(sum_of_money,num_of_people,min_of_money,max_of_money):
    if num_of_people==1:
        arr = [sum_of_money]
        return arr
    else:
        half = num_of_people>>1
        border_left = max(min_of_money*half,(sum_of_money-(num_of_people-half)*max_of_money))
        border_right = min(max_of_money*half,(sum_of_money-(num_of_people-half)*min_of_money))
        sum_of_left = random.randint(border_left,border_right)
        arr_left = deliver(sum_of_left,half,min_of_money,max_of_money)
        arr_right = deliver(sum_of_money-sum_of_left,num_of_people-half,min_of_money,max_of_money)
        return arr_left+arr_right
        
list = deliver(10000,10,600,1200)
print list</code>

根据题主的思路写了这样的一个答案

<code class="javascript">function faHongBao(money, pe, min, max) {
    var sum = money,
        result = [];

    for(var i=0; i<pe; i++) {
        result.push(min);
        sum -= min;
    }

    while(sum > 0) {
        var ran = Math.floor( Math.random() * (pe - 1) );
        if(result[ran] < max) {
            result[ran]++;
            sum--;
        }
    }

    return result;
}</code>

面接の質問: 100 元の赤い封筒を 10 人にランダムに送ります。 1人当たりの最高料金は12元、最低料金は6元です。分割方法は?

<code>
static void Main(string[] args)
        {
            int all = 100;//总金额
            int person = 10;//人数
            double min = 8;//最小金额
            double max = 12;//最大金额

            double[] array = new double[person];//分配结果集
            int i = 0;//第几人
            Random ran = new Random();

            //默认分配最小值
            for (i = 0; i < person; i++)
            {
                array[i] = min;
            }

            double yet = min * person;//已分配金额

            int whileTimes = 0;//记录循环次数
            while (yet < all)
            {
                double thisM = Math.Round((ran.NextDouble() * (max - min - 1)), 2);
                i = ran.Next(0, person);
                if (yet + thisM > all)
                {
                    thisM = all - yet;
                }

                if (array[i] + thisM < max)//判断是否超出最大金额
                {
                    array[i] += thisM;
                    yet += thisM;
                }
                whileTimes++;
            }


            Console.Write("共循环{0}次\r\n", person + whileTimes);
            yet = 0;
            for (i = 0; i < person; i++)
            {
                yet += array[i];
                Console.Write("第{0}人=>分配{1}元,合计分配{2}元\r\n", i + 1, array[i], yet);
            }
            Console.Read();

        }
</code>

<code>function roundmoney()
    {
        $cash=100;
    
        for ($i = 0; $i < 10; $i++) {
            $people[$i]=rand(6,12);
            $cash=$cash-$people[$i];
            if($cash==0&&$i==9)
            {
                return $people;
            }
        }
        return false;
    
    }
    while(true)
    {
        if(($res=roundmoney())!=false)
        {
            var_dump($res);
            break;
        }
    
    }</code>

感觉有点粗暴,就是完全让计算机随机分,什么时候刚好分够10个人并且每个人不少于6不大于10 就停止

<code>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</code>

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

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

<code>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</code>

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

根据楼主我实现一种

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

面接の質問: 100 元の赤い封筒を 10 人にランダムに送ります。 1人当たりの最高料金は12元、最低料金は6元です。分割方法は?

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

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

<code>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
)</code>

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

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

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

按照平均法求出X和Y
X+10Y = 100;
X+Y<=12;
故X的值为20/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的生成器可以简单的实现:

<code>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</code>

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

如果用 Python,可以这样实现:

<code class="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)</code>

如题,首先要获取大于6小于12的随机数,那么只要我们随机出0-6的随机数,并且加上6,就是符合要求的。
然后这个是红包,按照微信红包的需求来设计,那么随机数是有两位有效小数的。那么我们需要随机出0-600的随机数,然后除以100。
因为这种设计,所以随机出来的数值一定大于6,所以6这边边际问题,就解决了,只需要考虑12的情况。

随机出来一个数字,只要确保后面的n位数字的平均值不大于600就可以。


<code>$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));                //重新打乱数组,并输出</code>

算法就是这样,结果一定是正确的。
算法中添加的$factor_start和$factor_end变量,就是为了提高算法效率。
假设前面的随机数都很小,那么后面的随机数就要大起来。这个时候就需要增大$factor_start,减少后面while循环次数,提高算法效率。

假设前面的随机数特别大,让后面的数,无法满足0,到600的随机,那么就通过$factor_end来控制。

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

借鉴了楼主思路  英文不好 变量命名不是很标准 别喷~ 期待更好随机性解析代码</code>

楼主的方法只能处理整数问题吧,题目中并没有交代一定是整数。
每次取随机的范围都是变化的
下限从6和(剩余钱数-12*(剩余人数-1))中取大的
上限从12和(剩余钱数-6*(剩余人数-1))中取小的
贴Java代码

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

某次运行截图
面接の質問: 100 元の赤い封筒を 10 人にランダムに送ります。 1人当たりの最高料金は12元、最低料金は6元です。分割方法は?

这么多人会,就我不会

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。