面試問題：發一個隨機紅包，100塊錢給10個人。每個人最多12塊錢，最少6塊錢。怎么分？

yexiaobai 發布于2019-06-27 14:05 / 1011人閱讀

這問題是@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塊錢個人服務器幾十塊錢一個月的云服務器

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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