转载

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

这问题是@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; }

原文 https://segmentfault.com/a/1190000006018350

正文到此结束