Maison > Questions et réponses > le corps du texte
以前想过一个类似问题,就是没有每个人最大、最小的得钱数的限制,以前的问题可以很好用随机数解决。
于是这个问题也被以前的思想带坑里了,把突破口完全放在了如何处理每个人的随机数上。
于是在面试时间就没有解决这个问题,直到面试结束自己安静下来,仔细想想,发现思路错了。
我认为正确的思路是:每个人先得6块钱,这样剩下40块钱,之后每次拿出一块钱,随机分配给一个人,如果某个人的钱数达到了上限,那么这个人下次就没有了再得到钱的资格了。这样直到剩下钱都分配完。
当然在接口的实际处理上可以做些优化,例如剩下的钱每次随机分配的钱可以是随机的(当然这个随机要做一些限制,以免一下就分配超额了),然后如果某个人钱+这次随机分配的钱>每个人的上限,那么他就没有资格得到这个钱了。
随机分配也好实现,先算有几个人有资格得到这笔钱,随即一个数,决定给第几个符合资格
的人。
我的思路就是这样,大家如果有更好的思路,请告知。谢谢。
巴扎黑2017-04-11 09:56:50
如题,首先要获取大于6小于12的随机数,那么只要我们随机出0-6的随机数,并且加上6,就是符合要求的。
然后这个是红包,按照微信红包的需求来设计,那么随机数是有两位有效小数的。那么我们需要随机出0-600的随机数,然后除以100。
因为这种设计,所以随机出来的数值一定大于6,所以6这边边际问题,就解决了,只需要考虑12的情况。
随机出来一个数字,只要确保后面的n位数字的平均值不大于600就可以。
$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)); //重新打乱数组,并输出
算法就是这样,结果一定是正确的。
算法中添加的$factor_start和$factor_end变量,就是为了提高算法效率。
假设前面的随机数都很小,那么后面的随机数就要大起来。这个时候就需要增大$factor_start,减少后面while循环次数,提高算法效率。
假设前面的随机数特别大,让后面的数,无法满足0,到600的随机,那么就通过$factor_end来控制。
黄舟2017-04-11 09:56:50
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));
借鉴了楼主思路 英文不好 变量命名不是很标准 别喷~ 期待更好随机性解析代码
怪我咯2017-04-11 09:56:50
答案真多,也没仔细看, 不知道有没有和我一样想法的。
我的总体思路是这样的:先均分6块;再分析每个人得钱的随机范围;每个人依次得钱直至分完,一次就分完了。
1、每人至少6块,所以先分出60,剩下40。那剩下人的每个人能得到的初看是[0~6];
2、反推。从最后一个人(第10个人)推起,到他时,剩下的钱必定是<=6,继续往前推一个,到他时,剩下的钱必定是<=12,然后依次类推(最好在纸上写一下)。这么推我们可以得出到第5个人得钱时,剩下的钱必定是<=36, 那么前4个人必须要分掉至少4块钱,以此再推,前5个人必定要分掉至少10块钱,至最后一个至少得分掉34块钱。这样通过找规律我们得出了每个人得钱的随机范围的第一个值。
3、虽然我们得出了每个人随机范围的第一个值,但并不是每一个人的随机范围的第二个值都是 6,因为当前面的几个人已经把大部分钱都分了的时候,后面的人就没得分了。这次,我们从第一个人开始往后推,当到第N个人时剩下的钱$R<6时,这个人所能分得的钱的随机范围第二个值就是剩下的钱$R,然后他后面的人所能分得的钱的随机范围的第二个值还是$R;
说明完毕,也不知道有没有说明白,还是直接上代码吧:
$R = 40; //剩余钱数
$add_max = 12 - 6;
$arr = array(6, 6, 6, 6, 6, 6, 6, 6, 6, 6);
for($i = 0; $i<10; $i++) {
//默认随机数是 0~6
$rand = mt_rand(0, $add_max);
//反推过程可以得出从第4个人开始,rand要么是以$diff为初始值,要么就是上一行的$rand;而随机范围第二个值由剩余钱$R决定。
if($i > 2) {
if($R <= 0) break;
$diff = $R - (10 - $i - 1) * $add_max;
$rand_end = $R < 6 ? $R : $add_max;
$diff > 0 && ($rand = mt_rand($diff, $rand_end));
}
$arr[$i] += $rand;
$R -= $rand;
}
var_dump($arr,array_sum($arr));
这里得出的都是整型的,如果要得到浮点数,把rand函数替换成获得浮点数的随机函数就行。这是稍微精简后的,通俗过程:
$R = 40;
$add_max = 12 - 6;
$arr = array(6, 6, 6, 6, 6, 6, 6, 6, 6, 6);
for($i = 0; $i<10; $i++) {
//根据反推,前三个是不用考虑随机范围的,从第4个人开始才需要考虑随机范围
if($i < 3) {
$rand = mt_rand(0, 6);
} else if($i == 3) {
//留给第5个人的不能超过36。当$rand_start不为0时,说明钱还很充足的。充足到第$i个人必须抽走一些钱才行。
$rand_start = $R - 36 ? $R - 36 : 0;
$rand = mt_rand($rand_start, 6);
} else if($i == 4) {
//留给第6个人的不能超过30.
$rand_start = $R - 30 ? $R - 30 : 0;
$rand = mt_rand($rand_start, 6);
} else if($i == 5) {
//留给第6个人的不能超过24.到现在为止,钱一定还是充足的,所以不用考虑第二个值。
$rand_start = $R - 24 ? $R - 24 : 0;
$rand = mt_rand($rand_start, 6);
}
//...
else if($i == 6) {
//通过上面得出留给下一个人的不能超过 (10-$i-1)*6; 然后到第7个人时,假设前面每个人都得到了6块,即只剩下4块钱时,随机范围第二个数就不再是6了,而是剩余数$R
$rand_start = $R - 24 ? $R - 24 : 0;
$rand_end = $R > 6 ? 6 : $R;
$rand = mt_rand($rand_start, $rand_end);
}
//...
$arr[$i] += $rand;
$R -= $rand;
}
困死了,不写了
PHP中文网2017-04-11 09:56:50
作为热门问题 前端人员表示想过来贴个 JavaScript版
// 100 10 max 12 min 6
var count = 0;
function getAmount(totalAmount,number,max,min){
count++;
var usedAmount = 0;
var amountList = [];
for(var i = 0; i< number-1; i++){
var amount = parseFloat((Math.random()*(max-min)).toFixed(2));
amountList[i] = amount;
usedAmount += amount;
}
var balance = totalAmount - min*number - usedAmount;
amountList[9] = balance;
if(balance > (max-min) || balance < 0){
getAmount(totalAmount,number,max,min);
}else{
usedAmount = 0;
for(var i = 0; i< number; i++){
redPacket[i] = (6 + amountList[i]).toFixed(2);
usedAmount += parseFloat(redPacket[i]);
}
// 确认总额是否是100
console.warn(usedAmount.toFixed(2));
// 打印每个红包金额
console.info(redPacket);
console.info('计算次数:' + count);
}
}
getAmount(100,10,12,6);
伊谢尔伦2017-04-11 09:56:50
楼主的方法只能处理整数问题吧,题目中并没有交代一定是整数。
每次取随机的范围都是变化的
下限从6和(剩余钱数-12*(剩余人数-1))中取大的
上限从12和(剩余钱数-6*(剩余人数-1))中取小的
贴Java代码
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();
}
}
某次运行截图
怪我咯2017-04-11 09:56:50
import random
def pocket(total=100,num=10,min=6,max=12):
result = []
while num > 1:
rand_num = round(random.uniform(min,max),2)
left_money = total - rand_num
if left_money > min * (num-1) and left_money < max * (num-1):
result.append(rand_num)
num -= 1
total -= rand_num
result.append(round(total,2))
return result
result = pocket()
print result
print sum(result)
PHPz2017-04-11 09:56:50
function markPacket($money=100,$people=10,$min=6,$max=12){
$cash = $money-$people*$min;
$packet_arr = [$min,$min,$min,$min,$min,$min,$min,$min,$min,$min];
$i = 0;
while($cash > 0){
$people_rand = rand(0,($people-1));
$money_rand = rand(0,($max-$min)*100)/100;
$people_money = $packet_arr[$people_rand] + $money_rand;
if($people_money > 12){
continue;
}
if($money_rand > $cash){
$people_money = $packet_arr[$people_rand] + $cash;
}
$packet_arr[$people_rand] = $people_money;
$cash -= $money_rand;
$i++;
}
var_dump($packet_arr,array_sum($packet_arr),$i);
}