以前想过一个类似问题,就是没有每个人最大、最小的得钱数的限制,以前的问题可以很好用随机数解决。
于是这个问题也被以前的思想带坑里了,把突破口完全放在了如何处理每个人的随机数上。
于是在面试时间就没有解决这个问题,直到面试结束自己安静下来,仔细想想,发现思路错了。
我认为正确的思路是:每个人先得6块钱,这样剩下40块钱,之后每次拿出一块钱,随机分配给一个人,如果某个人的钱数达到了上限,那么这个人下次就没有了再得到钱的资格了。这样直到剩下钱都分配完。
当然在接口的实际处理上可以做些优化,例如剩下的钱每次随机分配的钱可以是随机的(当然这个随机要做一些限制,以免一下就分配超额了),然后如果某个人钱+这次随机分配的钱>每个人的上限,那么他就没有资格得到这个钱了。
随机分配也好实现,先算有几个人有资格得到这笔钱,随即一个数,决定给第几个符合资格
的人。
我的思路就是这样,大家如果有更好的思路,请告知。谢谢。
PHP中文网2017-04-11 09:56:50
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
PHP中文网2017-04-11 09:56:50
这个问题很简单,100块给10个人,那么平均数就是10,先随机一个6到12的数,如果小于10,那么剩下的钱除以9肯定平均数大于10,那就在10到12随机一个数,然后把剩下的钱除以8,如果平均数大于10继续在10到12里面随机,如果小于10,那么就在6到10之间随机,由此类推得到10个随机数。然后把这10个随机数打乱分给10个人。
天蓬老师2017-04-11 09:56:50
我从题目中获取的信息是这样的:
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
伊谢尔伦2017-04-11 09:56:50
100元,给10人;范围6-12元
1,每人先发6元。 剩下每人最多还能分到6元。 剩下40元
2,如果按照整元分; 那么等价于40元分到60个槽。。。
3,如果要精确到分, 那么等价于40 00 分 分到 60 * 100个槽。。。
阿神2017-04-11 09:56:50
根据楼主我实现一种
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;
}
}
怪我咯2017-04-11 09:56:50
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);
此算法的特征是每个人分得比较均衡。
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
)
迷茫2017-04-11 09:56:50
<?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));
?>
整个算法时间复杂度比较稳定
大家讲道理2017-04-11 09:56:50
<?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();
}
按照平均法求出X和Y
X+10Y = 100;
X+Y<=12;
故X的值为20/9
(借鉴了上一位回答者的回答)
天蓬老师2017-04-11 09:56:50
数学模型为:取随机数 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的生成器可以简单的实现:
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
大家讲道理2017-04-11 09:56:50
相当于生成 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)