面试问题:发一个随机红包,100块钱给10个人。每个人最多12块钱,最少6块钱。怎么分?
于是这个问题也被以前的思想带坑里了,把突破口完全放在了如何处理每个人的随机数上。
于是在面试时间就没有解决这个问题,直到面试结束自己安静下来,仔细想想,发现思路错了。
我认为正确的思路是:每个人先得6块钱,这样剩下40块钱,之后每次拿出一块钱,随机分配给一个人,如果某个人的钱数达到了上限,那么这个人下次就没有了再得到钱的资格了。这样直到剩下钱都分配完。
当然在接口的实际处理上可以做些优化,例如剩下的钱每次随机分配的钱可以是随机的(当然这个随机要做一些限制,以免一下就分配超额了),然后如果某个人钱+这次随机分配的钱>每个人的上限,那么他就没有资格得到这个钱了。
随机分配也好实现,先算有几个人有资格得到这笔钱,随即一个数,决定给第几个符合资格
的人。
我的思路就是这样,大家如果有更好的思路,请告知。谢谢。
回复内容:
以前想过一个类似问题,就是没有每个人最大、最小的得钱数的限制,以前的问题可以很好用随机数解决。
于是这个问题也被以前的思想带坑里了,把突破口完全放在了如何处理每个人的随机数上。
于是在面试时间就没有解决这个问题,直到面试结束自己安静下来,仔细想想,发现思路错了。
我认为正确的思路是:每个人先得6块钱,这样剩下40块钱,之后每次拿出一块钱,随机分配给一个人,如果某个人的钱数达到了上限,那么这个人下次就没有了再得到钱的资格了。这样直到剩下钱都分配完。
当然在接口的实际处理上可以做些优化,例如剩下的钱每次随机分配的钱可以是随机的(当然这个随机要做一些限制,以免一下就分配超额了),然后如果某个人钱+这次随机分配的钱>每个人的上限,那么他就没有资格得到这个钱了。
随机分配也好实现,先算有几个人有资格得到这笔钱,随即一个数,决定给第几个符合资格
的人。
我的思路就是这样,大家如果有更好的思路,请告知。谢谢。
$cash = 40;
$user_arr = array(6,6,6,6,6,6,6,6,6,6);
while($cash>0){
$user_id = rand(0, 9);
if($user_arr[$user_id]
性能篇
$arr1=range(2,6);
shuffle($arr1);
$arr2=range(2,6);
shuffle($arr2);
$user_arr = array(6,6,6,6,6,6,6,6,6,6);
for ($i=0;$i
$value) {
if ($diff > 0) {
$value--;
if ($value >= 6) {
$result[$key] = $value;
break;
}
} elseif ($diff
可能写复杂了,突然想到的就这样了。
还有更简单粗暴的,效率也还行。
最后就是精确到分为单位的,上面两种方法都可以这么改造。除了人数所有数量乘以一百,运算完之后再除以一百。
写这么多还被踩,也不给个理由。什么情况?
我写了个思路迥异的。。。感觉有点麻烦,不过效率和可扩展性还凑合。
思路:每次分配后,都确定剩余的金钱在合理范围。
若合理,进行下次分配
否则,重新进行此次分配。
$restPeople * $max || $restMoney
运行结果:
我的想法是采用递归来实现,代码如下:
//rem,当前递归层次还有多少个数没有生成,$total生成总量,在这个项目中为40,$must必须达到的数据,$arr,临时变量用来保存和传递用
//返回类型,$arr,即生成的随机数组
function test($rem, $total, $must, $arr)
{
if($rem>=2)
{
$rem -= 1;
//$min本轮生成随机数的最小值是多少
$min = round($must - $rem * 6 , 2);
if($min 6) ? 6 : $must;
$rand = round(mt_rand($min*100, $max*100)/100 , 2);
$arr[] = $rand;
$must = $must - $rand;
echo "生成rand数值:".$rand;
echo "--剩余随机次数:".$rem."----必须达成数据:".$must;
echo "
";
return test($rem, $total, $must, $arr);
}else{
$arr[] = $must;
return $arr;
}
}
$arr = array();
$brr = test(10, 40, 40,$arr);
//以后如果我想得到5个人分20块钱,也可以直接调用
//test(5,20,20,$arr)即可
print_r($brr);
最后生成的结果如下 :
生成rand数值:0.41--剩余随机次数:9----必须达成数据:39.59
生成rand数值:0.81--剩余随机次数:8----必须达成数据:38.78
生成rand数值:5.72--剩余随机次数:7----必须达成数据:33.06
生成rand数值:2.51--剩余随机次数:6----必须达成数据:30.55
生成rand数值:1.25--剩余随机次数:5----必须达成数据:29.3
生成rand数值:5.34--剩余随机次数:4----必须达成数据:23.96
生成rand数值:5.98--剩余随机次数:3----必须达成数据:17.98
生成rand数值:5.99--剩余随机次数:2----必须达成数据:11.99
生成rand数值:6--剩余随机次数:1----必须达成数据:5.99
Array ( [0] => 0.41 [1] => 0.81 [2] => 5.72 [3] => 2.51
[4] => 1.25 [5] => 5.34 [6] => 5.98 [7] => 5.99 [8] => 6 [9] => 5.99 )
X为已经抽取的数值
Y为已经抽取的人数
思路:
因为100块分10个人,可选范围是6到12。所以可以随机地在6~12分给全部人就可以了。但可能会出现派不完或者不够分的情况,所以实际上每个人的选择区间不一定是6~12,也取决于先抽到钱的人。假如他们都抽到的金额接近总体平均值,那么这个区间就会保持在6~12,假如连续开头三个人都抽到6,那么第四个人的区间就会缩小,下限会提高。然而一旦她抽到了12,又会让下一位的选择区间变大了一点。但总体来看,越接近尾声,选择区间会缩小,直到最后一个人选择时,他的选择上限和下限是恰好相等的。所以用图来描述这个动态区间,比较有意思的是像一种时间线流动一样,从最底三层都是6~12,6~12,6~12,然后后面会随着具体的数值发生变化,你也永远无法知道下一个数是什么。
这里满足四个条件:
1.剩余金额除以人数不能大于12
2.剩余金额除以人数不能小于6
3.每个人都只能在6~12里选
4.总金额100分为10个人
m为总金额,n为人数,min选择下限,max为选择上限,用方程式
方程式为 min
下面是已经配平的式子,式子分别为上限和下限。上限可大于12时,配成12,否则保留。下限同理。
我不懂php,用python来代替:
(我的代码写得很不pythonic请不要吐槽,位数采用默认的很多位小数,根据实际情况再进行削减)
#encoding=utf8
from random import uniform
def flag(m, n, min, max):
x = 0
y = 0
L = []
for i in range(n):
top = 12
bottom = 6
if not m-x-min*(n-y-1) >= 12:
top = m-x-min*(n-y-1)
if not m-x-max*(n-y-1)
优点是,我得出下一位数永远时即时运算的,它不是得出一个既定的组合,然后再分配给每一个人。而是根据前面的情况,即时产生下一个结果。在具体用户上,当然是没有区别,但我在思考红包这个玩意的时候,也很自然觉得要是提前分好一个模式给我,那其实下一个数是什么早有了定论,程序员log一下就能知道是什么,那样就不好玩了。另外红包派不完的情况下,我无需去记录已经分配好的模式又在过期后对它进行删除的操作。这里在随机前进行判断来缩小区间,比随即后判断是否满足条件要好那是因为,选择出来的数符合逐渐变小的区间可能性会越来越低,结果在数据规模更大时,性能会下降严重。而先判断出上下区间则保证整个计算过程长度不变,都是常数级。
缺点是,如果不作另外的解释和运算,根本不知道上面这是在算什么,思路也不明了。
=================
更新,有评论提到越后抽越多money的问题,是的:
这个是因为人均10元,下限6元比平均低4元,上限12元才高2元,不对称同时金额分10人最高只有12这个空间“拉得很紧”,所以前三个都是100%在6~12所以无问题,后面就出问题了。这样有一个问题,就是出现了明显的规律,越后面越可能大。
毕竟这里均值达到10,每抽到1个人抽到6就需要2个人抽到12来弥补,所以要么让它更为集中到10,要么分散到2端,同时后面那端要比前者的高很多,而均匀分布是不可能的。因为这里涉及到红包,红包分定额和随机两种。集中分布可以说是固定金额的近似值,所以一定要做两端分布,两端分布可以在区间随机前对区间进行权重选择再随机就能操控,另外,也可以每次随机都生成10次数据,然后再从中抽取一个出来,其他删掉,第二个人抽再根据第一个数据生成第二个数列一直到结束,就能做到“分布均匀”,但题目中的数据限制还是很多人会抽到很大的数,的确在所难免。
集中化只要为每个数据根据它的位置乘上相关系数解决。或者直接设为10,然后设定“随机抖动”= = 。
因为数学的好处所以这个性能完全是常数级的,执行步数每次都是一样的,不存在要把自己的算法的性能也连同一起和所需生成的数据一起来随机玩概率的问题。所以想要两端分布同时随机分布这里可以在最后生成的答案里加上随机选一个就能达到效果。但算法之外是这个抢红包的问题,到底是集中还是分散分布?或许很多人抢时最后的红包才大还是好事情,抢早了,红包小了,迟了,被抢光了,最后一个是最危险的也是概率上金额最大的那一个,有意思不?或者说,我喜欢平均一点,既要和某人玩随机金额才刺激,还要避免某人抽得太小而尴尬?所以最后还得看实际需求怎样才能决定。
PS:看到题主的评论,题主的思路有人提到是随机到6块这种的概率很低,假如真的如此(偷懒没试过),那算法直觉就是集中化趋势的过程了。没有好坏,只是看需求如何。
就是每个人都减去6块钱,这样问题就转变成40块分给10个人,没人不多于6块钱。这样做的核心是,把两个限制变成了一个限制,因为分到的钱一定是正数,所以大于0这个限制变得简单了。
剩下的分,在总钱数大于6块的时候,只要做一个0到6的随机就可以,小于6块的时候,做0到这个总数的随机就可以,最后一个人拿剩下的。
当剩余红包金额小于等于12 * 剩余红包个数且大于等于6 * 剩余红包个数,则将随机数加入到结果中.
function makeSeq(){
$n = 10;
$sum = 100;
$result = [];
while ($n > 1) {
// 6n = 6* ($n - 1) && ($sum-$randNum)
7.20更新高新能版
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))
一个do while循环就能解决的问题,搞那么复杂。
= 12)
continue;
if($money 0);
print_r($people);
?>
你的想法基本靠谱,我认为可以这样分:
1.先每人分6元,还剩下40元。
2.起一个循环,每人分0-(12-他已有的钱)元随机,直到钱分完为止。
没有题主讲的这么麻烦的。
$arr = [];
for ($i=0; $i
先每个人分6分,然后把剩下的钱再分
这个时候取10个随机值(0-9)随意,然后取各个值在随机值总和的百分比,分别乘以剩下的10000-60;Math.ceil或者Math.floor都可以
最后一个值防止取ceil时溢出,直接用10000-60-前面九个数的和即可
然后分别加上6,换算即可
min = 6;
max = 12;
total = 100;
pe = 10;
maxTotal = max*pe - total;
list = array();
for (00)
temp = random(0,maxTotal>=6?6:maxTotal);
maxTotal-=temp;
list.push(12-temp);
if(maxTotal>0)
pre = maxTotal/pe;
for (0
此方法是错误的,没有强迫症,不修改了
半夜看到这个问题,忽然想到二分法那种模式,于是搞了一个解决方案,先讲思路。
1.先将人分为两半,左半人分的总金额最少是左半人数x最少金额和总金额-右半人数x最多金额两个数字中较大的;
2.左半人分的总金额最多是左半人数x最多金额和总金额-右半人数x最少金额两个数字中较小的;
3.在这个范围内取随机数作为分给左半人的金额,然后将问题递归为左半人分钱和右半人分钱。
py代码(直接以分为单位,数字都是整数):
import random
def deliver(sum_of_money,num_of_people,min_of_money,max_of_money):
if num_of_people==1:
arr = [sum_of_money]
return arr
else:
half = num_of_people>>1
border_left = max(min_of_money*half,(sum_of_money-(num_of_people-half)*max_of_money))
border_right = min(max_of_money*half,(sum_of_money-(num_of_people-half)*min_of_money))
sum_of_left = random.randint(border_left,border_right)
arr_left = deliver(sum_of_left,half,min_of_money,max_of_money)
arr_right = deliver(sum_of_money-sum_of_left,num_of_people-half,min_of_money,max_of_money)
return arr_left+arr_right
list = deliver(10000,10,600,1200)
print list
根据题主的思路写了这样的一个答案
function faHongBao(money, pe, min, max) {
var sum = money,
result = [];
for(var i=0; i 0) {
var ran = Math.floor( Math.random() * (pe - 1) );
if(result[ran]
static void Main(string[] args)
{
int all = 100;//总金额
int person = 10;//人数
double min = 8;//最小金额
double max = 12;//最大金额
double[] array = new double[person];//分配结果集
int i = 0;//第几人
Random ran = new Random();
//默认分配最小值
for (i = 0; i all)
{
thisM = all - yet;
}
if (array[i] + thisM 分配{1}元,合计分配{2}元\r\n", i + 1, array[i], yet);
}
Console.Read();
}
function roundmoney()
{
$cash=100;
for ($i = 0; $i
感觉有点粗暴,就是完全让计算机随机分,什么时候刚好分够10个人并且每个人不少于6不大于10 就停止
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]0.01){
return randUserMoney($cash_ini);
}
$rand_money = round($rand_point*$cash,2);
$user_money = $user_arr[$user_id]+$rand_money ;
if($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
这个问题很简单,100块给10个人,那么平均数就是10,先随机一个6到12的数,如果小于10,那么剩下的钱除以9肯定平均数大于10,那就在10到12随机一个数,然后把剩下的钱除以8,如果平均数大于10继续在10到12里面随机,如果小于10,那么就在6到10之间随机,由此类推得到10个随机数。然后把这10个随机数打乱分给10个人。
我从题目中获取的信息是这样的:
1、总数是100;
2、10个人分;
3、最小6块;
4、最大12块;
5、红包分完(例如都是6块的情况不存在)。
思路:
先从总数中扣除最小红包,保证每个红包的最小基数,设置一个奖金池,奖金池等于总是减去保底红包;
每个人实际领到的红包 等于 红包基数 加上 从奖金池中获取的随机奖金;
随机奖金会判断当前奖金池数量 与 剩余人数之间的关系,决定最小奖金的大小:minSignal
① restNum * 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
100元,给10人;范围6-12元
1,每人先发6元。 剩下每人最多还能分到6元。 剩下40元
2,如果按照整元分; 那么等价于40元分到60个槽。。。
3,如果要精确到分, 那么等价于40 00 分 分到 60 * 100个槽。。。
根据楼主我实现一种
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
function fhb($money,$num,$min,$max){
$firstUse=$num*$min;
$surplusMoney=$money-$firstUse;
$arr=array();
for($i=1;$i0){
$randUid = rand(0, $num - 1);
if($arr[$randUid]
此算法的特征是每个人分得比较均衡。
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
)
function hongbao($money, $people, $min, $max) {
if($people * $min > $money || $people * $max ($people - $i -1) * $max) {
$rand += 1;
$rand > $max && $rand = $max;
} elseif($restMoney
?>
整个算法时间复杂度比较稳定
$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 0) {
if ($restMoney getMessage();
}
按照平均法求出X和Y
X+10Y = 100;
X+Y故X的值为20/9
(借鉴了上一位回答者的回答)
数学模型为:取随机数 x 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
相当于生成 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]
如题,首先要获取大于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
算法就是这样,结果一定是正确的。
算法中添加的$factor_start和$factor_end变量,就是为了提高算法效率。
假设前面的随机数都很小,那么后面的随机数就要大起来。这个时候就需要增大$factor_start,减少后面while循环次数,提高算法效率。
假设前面的随机数特别大,让后面的数,无法满足0,到600的随机,那么就通过$factor_end来控制。
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_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));
借鉴了楼主思路 英文不好 变量命名不是很标准 别喷~ 期待更好随机性解析代码
楼主的方法只能处理整数问题吧,题目中并没有交代一定是整数。
每次取随机的范围都是变化的
下限从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 money_left - Max*(peopleNum-i-1)?Min:(money_left - Max*(peopleNum-i-1));
upperBound = Max
某次运行截图
这么多人会,就我不会
上一篇: 关于mysql数据库误删除后的数据恢复操作的示例代码分享
下一篇: 神经网络,多输入多输出