红包随机算法的故事-阀值

场景:

最近大佬在做红包,看大佬在那想东西,然后抱着有什么问题可以帮下他也能成长自己的心理,问了一下,然后他给我出了一道题,也不告诉我啥业务,~(~ ̄▽ ̄)~ 好吧,我一开始以为简单的问题,后来发现有3个维度,还是花了1个多小时想出来,给大家分享下吧,挺有意思的。

问题 :

条件1:随机 a-b的随机数        例:3-8

条件2:随机n次                      例:50次

条件3 : n次累加之和等于s   例:250

以上 a,b,n,s  都是变量  求每一次随机的值

再次叙述:随机3到8的随机数 50 次 ,使他们累计之和等于250,求50次每一次的随机

想法:

1、实现最简单的就是 写个循环跳出条件为s,也就是s=250就跳出,循环里面写 随机a-b的随机数随机n次 ,也就是随机3-8的随机数,随机50次,然后累加放到s里,这个成功几率太低了,没准就死循环了= =,直接pass掉。

2 、后来想到了用回溯算法,简单说就是随机到最后,相加不得250 ,或者随机到第30个累加就大于250,等条件,反正确定无解之后就进行回溯,删去上一个已经随机的随机数,然后从新随机,后来想了想,不太可行,因为每次的数字是随机的嘛- – 而且回溯一般都是已知的树状求解,如果把3,4,5,6,7,8拿出来求解,那就没随机性了= =所以也pass掉了

3 、后来又想了一个,能不能把250拆分,写个递归逐步求解之类的,后来也没想好怎么拆,所以也没写出来:-D

最终,当想了好多之前学的算法之后,发现问题在于,随机50次随机数很简单,但是累加之和等于一个值,问题就来了,很有可能随机到某一次就无解了,如随机了40次就已经到230了就算最后10个随机的都是最小的3也无解,总和是260,不满足累和等于250,如何做一个控制,让他每一次既是随机的,又能最后相加一定能得250,二百五哈哈哈。。。。

解:

突然脑袋里冒出里,一个绳子拴着一条狗的图像  =  = 灵感啊! 我想到了阀值,这个名字是我取的 = =

首先声明,用这个算法其实要有一定条件的,如必须有解,必须能整除,我们假设条件是允许的。

好思路是这样的,首先用250除以50 等于5,也就是说随机50次,每次是5 ,最后能得到250,废话= = ,但是5就是阀值,这个是不变的。

还有个变量阀值,这个就向绳子一样,打个比方,第一次随机的数是3,那变量阀值就是-2,如果下次随机到7,那么变量阀值就回变成0,让变量阀值在0左右浮动。

如果随机到第49个,变量阀值是-3 ,那么随机数随机到8,也就是把上一次低于阀值5的3个加上这次该随机的5个就是8个,最后相加等于250.

变量阀值是有范围的,范围是3到-2 ,也就是说不出这个范围,当随机到最后一个数的时候,在3到8中的一个值是可以放上去相加能等于250的,当然随机到第49个的时候第50个数已经确认了。

设置一个阀值,每次判定一下随机数是否在这个阀值内,保证最后一个随机数加起来可以等于250。

总感觉没讲懂 =  = ,上代码吧

代码:

@Test

publicvoidtest2()

{

//测试100次

for(intj=0;j<100;j++){

Randomrdm=newRandom();

intbegin=1;

intend=80;

intcycleTimes=1000;

intsum=40000;

//数组放50个数用

intresult[]=newint[cycleTimes];

 

//阀值

intthreshold=sum/cycleTimes;

//最高阀值

inthigh=end-threshold;

intlow=begin-threshold;

//当前阀值

intthresholdNow=0;

 

////记录一下总的循环次数

intfroNo=0;

myJedisService.del("123456789");

for(inti=0;i<cycleTimes-1;i++){

//随机一个数

Integerrandom=rdm.nextInt(end-begin+1)+begin;

//判断是否在阈值内

intthresholdNowFor=random-threshold+thresholdNow;

if(thresholdNowFor<=high&&thresholdNowFor>=low){

thresholdNow=thresholdNowFor;

result[i]=random;

//记录一下每次成功的数字

myJedisService.hincrBy("123456789",random.toString(),1);

}else{

i=i-1;

}

//记录一下总的循环次数

froNo=froNo+1;

}

result[cycleTimes-1]=threshold-thresholdNow;

Integerasfdsdf=threshold-thresholdNow;

myJedisService.hincrBy("123456789",asfdsdf.toString(),1);

//打印用

intaaa=0;

for(inti=0;i<cycleTimes;i++){

aaa=aaa+result[i];

}

 

Map<String,String>justMap=myJedisService.hgetAll("123456789");

Integerxunhuancishu=0;

for(Map.Entry<String,String>entry:justMap.entrySet()){

System.out.println("数字:"+entry.getKey()+",循环次数"+entry.getValue());

xunhuancishu=xunhuancishu+Integer.valueOf(entry.getValue());

}

System.out.println("总数字数量:"+xunhuancishu.toString());

System.out.println("循环次数:"+froNo);

System.out.println("总:"+aaa);

}
}
注:效率超高,50个数一般就循环70次左右就能找到解,并且解有很大的随机性,良好情况下,循环次数n*1.3。

其他:

后来我又想出一个算法,这个算法比上一个随机性大,而且不容易出错,不过应该性能要求会高点,不适合a和b间隔过大,解过多的,那就是第一次用回溯算出所有的解,然后把解存起来,每一次随机一个解,这样的随机性比较大,适合a,b,n,s不变的,但是第一次效率较低,以后的效率较高。

总结:

其实后来想了一下这个算法的限制很多,虽然良好状态下循环次数n*1.3 但是如果结果太过于极端,比如 3-8 循环50 次  累加和为150 有解太极端,而且没有随机性,都是一个数,就不适合用,当阀值越接近( a+b )/2的时候效果最佳!而第二个适合必较固定的,没有一个万能的算法,只有相对的问题,用对应的解决算法,还是看需求,不过思考思考总是好的,而且阀值这个东西感觉也可以用到别的地放。

发表评论

电子邮件地址不会被公开。 必填项已用*标注