以前想过一个类似问题,就是没有每个人最大、最小的得钱数的限制,以前的问题可以很好用随机数解决。于是这个问题也被以前的思想带坑里了,把突破口完全放在了如何处理每个人的随机数上。后来仔细想想,发现思路错了。
设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;
}