更多
 当前上元教育宁波校 其它分校: 慈溪校 无锡校 常州校 南京校 上海校 绍兴校 南通校   (建议使用IE浏览本网站/分辨率1024*768px)    
宁波培训学校 宁波培训学校
 位置: 邦元教育 >> 机电培训 >> 应用案例 >> 正文
 

佛系红包算法,了解一下?

作者:Admin  更新时间:2018/05/06  点击次数:

三年前微信红包爆火的时候,脑补了下背后的分配原理,并用C写了个demo,如今回想觉得当时的解法有一定的趣味性,遂丰富完整了下,用js重写了一遍。

红包算法需满足的规则如下:

  1. 所有人抢到金额之和等于红包金额,不能超过,也不能少于;

  2. 所有人抢到金额的几率相等;

  3. 每个人抢到的金额均大于0。

我脑补的第一画面就是:排排坐,分果果

于是分配原理如下:

众人们先按抢红包的顺序依次入座,围成圆环,将金额均分到每个人,然后每人同时将自己手中的金额随机抽出部分给左右临近的2个人,但保证手头至少剩余1单位的金额,完成分配。

  • 由于在总金额的基础上进行交换分配,故满足规则一;

  • 由于在金额均分的基础上再进行同等条件的随机金额交换,故满足规则二;

  • 由于随机分配中保证了至少保留1单位的金额,故满足规则三。

接下来开始实现上述过程

1、获取分配总额

由于弱类型语言可变换莫测的入参,在拿到总金额数字的时候必须抖个机灵做下过滤,这里使用了jonschlinkert大神写的is-number函数,用于判断入参是否是数字,否则置它为0;

另外,为了规避js中小数运算的精度问题,该算法中只使用整数进行加减,即将小数放到位整数(乘倍数),运算后再缩小回原来倍数(除倍数)。

classRandomSplit{ constructor(num){ // 实际总数 this.num =this.getNum(num); // 放大倍数 try{ this.multiple =this.num.toString().split('.')[1].length; }catch(e){ this.multiple =0; } // 用于整数运算的总数 this.calcNum =this.num *Math.pow(10,this.multiple); } // 判断是否为number(取用至“is-number”) isNumber(num){ letnumber= +num; if((number-number) !==0){ returnfalse; } if(number=== num){ returntrue; } if(typeofnum ==='string'){ if(number===0&& num.trim() ===''){ returnfalse; } returntrue; } returnfalse; } // 获取数字 getNum(num, defaultNum =0){ returnthis.isNumber(num) ? (+num) : defaultNum; }}

2、环形入座,将总数按份数均分

看“环形”二字,仿佛需要使用双向循环链表,为节省代码,这里只用一维数组模拟其效果,在数组首尾做数据衔接即可。

在该算法中,所有用于分配交换的数字的原子单位都是整数1,所以均分也需要均分为整数,例如总数15均分为6份,先每份分到2(Math.floor(15/6)===2),还余3(15%6===3),为了使后面用于计算的概率尽可能平均,我们需要把这余下的3个单位均匀洒落到那6份里面,类似过程如下图:

onerror=javascript:errorimg.call(this); src="http://p1.pstatp.com/large/pgc-image/15255890177859fe02039ca" extra='{"origin_web_uri": "pgc-image/15255890177859fe02039ca"}' img_height="243" img_width="640">

同理,若想要均分地更加精确,可提供精度的位数,然后将总数按该位数放大,整数均分后每份再按该精度位数缩小。

于是均分函数如下:

// 均分份数, 均分精度, 是否直接返回放大后的整数average(n, precision, isInt){ precision =Math.floor(this.getNum(precision,0)); n =Math.floor(this.getNum(n)); letcalcNum =this.calcNum *Math.pow(10, precision<0?0: precision); // 份数超过放大后的计算总数,即不够分的情况 if(n > calcNum){ return[]; }else{ letindex =0; // 平均数 letavg =Math.floor(calcNum / n); // 剩余数 letrest = calcNum % n; // 剩余数填充间隔 letgap =Math.round((n-rest) / rest) +1; // 原始平均数组 letresult =Array(n).fill(avg); // while(rest >0) { index = (--rest) * gap; result[index>=n ?(n-1) : index]++; } // 返回放大后的结果数组 if(isInt){ returnresult; } // 返回处理完符合精度要求的结果数组 returnresult.map((item) =>{ return(item /Math.pow(10,this.multiple + precision)); }); }}

测试效果如下:

onerror=javascript:errorimg.call(this); src="http://p3.pstatp.com/large/pgc-image/15255890178656d31e8e486" extra='{"origin_web_uri": "pgc-image/15255890178656d31e8e486"}' img_height="548" img_width="588">

3、相邻随机交换

得到均分数额后,每个位置先随机出将要给出的数额,该数额大于等于0且小于自己的初始数额,再将该数额随机划分为两份,分别给到相邻的左右位置。

// 随机划分的份数, 划分精度split(n, precision){ n =Math.floor(this.getNum(n)); precision =Math.floor(this.getNum(precision,0)); // 均分 letarr =this.average(n, precision,true); letarrResult = arr.concat(); for(leti =0; i < arr.length; i++) { //给出的总额 letnum =Math.floor(Math.random() * arr[i]); // 给左邻的数额 letnumLeft =Math.floor(Math.random() * num); // 给右邻的数额 letnumRight = num - numLeft; // 首尾index处理 letiLeft = i===0? (arr.length-1) : (i-1); letiRight = i===(arr.length-1) ?0: (i+1); arrResult[i] -= num; arrResult[iLeft] += numLeft; arrResult[iRight] += numRight; } // 缩小至原尺度 returnarrResult.map((item) =>{ return(item /Math.pow(10,this.multiple + precision)); });}

测试效果如下:

onerror=javascript:errorimg.call(this); src="http://p1.pstatp.com/large/pgc-image/1525589017876485846704b" extra='{"origin_web_uri": "pgc-image/1525589017876485846704b"}' img_height="222" img_width="640">

整体结果测试

使用Echarts绘制随机分配结果,将100数额划分为10份,精度为1,横坐标为顺序位置,纵坐标为分配到的数额:

onerror=javascript:errorimg.call(this); src="http://p1.pstatp.com/large/pgc-image/152558901782313e7053985" extra='{"origin_web_uri": "pgc-image/152558901782313e7053985"}' img_height="342" img_width="640">

那每个位置获得数额的概率是否相等呢?下图是随机分配100次的结果,并将每个位置的在这100次分配中所得的平均数用红色标出:

onerror=javascript:errorimg.call(this); src="http://p3.pstatp.com/large/pgc-image/152558901782737cf055292" extra='{"origin_web_uri": "pgc-image/152558901782737cf055292"}' img_height="347" img_width="640">

那分配1000次呢?

onerror=javascript:errorimg.call(this); src="http://p3.pstatp.com/large/pgc-image/1525589017844408975b797" extra='{"origin_web_uri": "pgc-image/1525589017844408975b797"}' img_height="352" img_width="640">

由此可见,随机分配次数越多,每个顺序位置得到的平均数额会稳定在平均分配的数额左右,公平性得到了印证;同时,因为每个位置只能得到相邻两个位置的数额交换,所以分配结果中任意位置的数额不会超过平均数额的3倍(即自己一毛不拔,同时又得到相邻者的倾力相助),这样便可以控制随机分配结果中的最高金额不至于过高。

脑洞来了,要是并不是左右相邻进行交换呢?改变交换规则会怎样?

  • 和除自己外的随机位置的两位进行随机数额交换?从概率上讲,和之前等价...

  • 只和自己左右或者右边的位置进行随机数额交换?分配结果依然公平,但最高数额不会超过平均数额的2倍

  • 每个位置随机左右一边然后进行随机数额交换?又双叒随机,还是公平的,最高数额还是少于平均数额的3倍(感觉貌似可以替代之前的方案,还能顺便降一倍的线性复杂度,我文章要重写了?! (°ー°〃))

  • 谁说只能挑2个进行交换?3个4个5个一起来行不行?行... 挑选位置公平的话,分配结果就公平,但是最大数额与交换数量正相关,但越高的数额,能得到的概率会急剧减小。

打住打住,再细想下去,我的坑怕是要填不完了 _(:з」∠)_

那这个东西除了可以分红包还能干嘛?

我用它写过一个没有后端数据的进度条,一抖一抖增加长短不一还仿佛真的在帮你加载一样...

其他...望君发挥想象力

最后 ( ˙-˙ )

onerror=javascript:errorimg.call(this); src="http://p1.pstatp.com/large/pgc-image/152558901784159f6d26ca6" extra='{"origin_web_uri": "pgc-image/152558901784159f6d26ca6"}' img_height="284" img_width="505">

上一篇: 反向代理服务器的工作原理 下一篇: 没有了
相关文章
 ·反向代理服务器的工作原理
 ·刚入门的Java程序员的就业前景怎么样?宁波上元教育让
 ·用信鸽来解释 HTTPS
 ·Java并发编程:阻塞队列
 ·从零讲JAVA ,给你一条清晰地学习道路!该学什么就学什
 ·java的适合人群,Java的就业薪资咋样
 ·学习软件编程基础入门
网上报名
姓名:  性别:
电话: 
地址:
课程:
最新课程 更多
 ·佛系红包算法,了解一下?
 ·5月22号,宁波上元教育,教你做一个
 ·反向代理服务器的工作原理
 ·前端开发转型产品经理,靠谱吗?
 ·刚入门的Java程序员的就业前景怎么
 ·集合系列—LinkedHashMap源码分析
 ·APP测试重点总结
 ·WEB测试重点总结
 ·如何制定web成长学习计划
 ·如何更好的做好web前端!
推荐课程 更多
 ·佛系红包算法,了解一下?
 ·5月22号,宁波上元教育,教你做一个
 ·反向代理服务器的工作原理
 ·前端开发转型产品经理,靠谱吗?
 ·刚入门的Java程序员的就业前景怎么
 ·集合系列—LinkedHashMap源码分析
 ·APP测试重点总结
 ·WEB测试重点总结
 ·如何制定web成长学习计划
 ·如何更好的做好web前端!
热门课程 更多
 ·佛系红包算法,了解一下?
 ·5月22号,宁波上元教育,教你做一个
 ·反向代理服务器的工作原理
 ·前端开发转型产品经理,靠谱吗?
 ·刚入门的Java程序员的就业前景怎么
 ·集合系列—LinkedHashMap源码分析
 ·APP测试重点总结
 ·WEB测试重点总结
 ·如何制定web成长学习计划
 ·如何更好的做好web前端!
网站首页| 友情链接| 最新开课| 会计培训| 电脑培训| 外语培训| 建筑培训| 信息技术| 才艺培训| 职业资格| 关于我们| 网上报名| 网站地图| 后台管理
联系地址:宁波市海曙区中山东路137号7楼
联系电话:0574-87327805、87323725、87324192、87325693、87325823、87326973、87329343、87329353、87042056