网站打不开怎么解决,快速建站模板自助建站,北京快三开奖走势图一定牛,html5手机网站调用微信分享波动均分算法by leeenx on 2018-01-11「波动」和「均分」大部分读者朋友是知道的#xff0c;但看到「波动均分」应该是一头雾水的。其实#xff0c;这个名词是笔者拼凑出来的。什么是「波动均分」#xff1f;把指定的数值 A#xff0c;分成 N 份#xff0c;此时每份的数值…波动均分算法by leeenx on 2018-01-11「波动」和「均分」大部分读者朋友是知道的但看到「波动均分」应该是一头雾水的。其实这个名词是笔者拼凑出来的。什么是「波动均分」把指定的数值 A分成 N 份此时每份的数值在一个固定的区间 [max, min] 内。 从视觉上看每份的数量在平均线上下波动并带有随机性这种分配不是严格意义上的「均分」但它却跟「均分」很相似按笔者的理解给这个算法取个名字 —— 「波动均分」。波动均分算法应该具备的特征如下分配数量波峰高度波谷深度随机分配组合全面前三个特征是提供对外配置的接口保证算法的使用者可以指定分配的数量和定制波动的波峰和波谷(尽管大部分情况下波峰 波谷)「随机分配」表示算法的结果是随机的「 组合全面」表示算法的结果是可以覆盖所有可能的结果。接下来笔者将介绍两种实现「波动均分」的算法穷举法快速分配备注本文算法中使用到的平均值是0穷举法「穷举法」顾名思义就是列举所有可能出现的组合再随机抽取一个组合作为输出结果。下面是一个「波动均分」任务有一张 10x10 的表格需要对格子上5种颜色并要求每种颜色的数量在区间 [18, 22] 内。由上述可得每种颜色都会有5种分配结果(18, 19, 20, 21, 22)。穷举这些颜色分配数量的组合其实就是建设一棵高度为 6 的 5 叉树的过程。第 6 层的叶子数就是「所有可能出现的组合」的总数。换而言之从树的第六层的一片叶子到第二层节点的路径即是一种分配组合。以下是「穷举法」的代码实现function exhaustWave(n 5, crest 4, trough 4) { let root {parent: null, count: null, subtotal: 0}; // 根节点let leaves [root]; // 叶子(数组)let level 0; // 层数 // 检查当前组合是否合法let isOK subtotal {if(level n - 1) {if(-subtotal (n - level) * crest || subtotal (n - level) * trough) return true; }else if(subtotal 0) return true; else return false; }// 生成组合树 while(level n) { let newLeaves []; // 存储最新叶子leaves.forEach(node {for(let count -trough; count crest; count) {let subtotal node.subtotal count; isOK(subtotal) newLeaves.push({parent: node, count: count, subtotal: subtotal}); }}); leaves newLeaves, level; }// 随机取一片叶子let leaf leaves[Math.random() * leaves.length 0]; let group [leaf.count]; for(let i 0; i 4; i) { leaf leaf.parent; group.push(leaf.count); }return group; }穷举法的局限「无穷集合」不适用穷举算法效率低下由于「穷举法」的这两个致命限制所以它不是适用于业务。事实上笔者主要是使用「穷举法」校验「快速分配」方案的全面性。快速分配「快速分配」方案的思路获取可分配波动范围在波动范围内随机取值代码的实现过程如下function quickWave(n 5, crest 4, trough 4, isInteger true) { let list []; // 无法进行波动均分直接返回完全平分if(crest (n - 1) * trough || trough (n - 1) * crest) {return new Array(n).fill(0); }let base 0; // 最少需要消除的高度let wave 0; // 波动量let high crest; // 高位let low -trough; // 低位let sum 0; // 累计量 let count n; // 剩余数量 while(--count 0) { // 动态当前的波动量if(crest count * trough - sum) {high count * trough - sum; }if(trough count * crest sum) {low -sum - count * crest; }base low; wave high - low; let rnd; // 随机波动量 if(count 0) {rnd base Math.random() * (wave 1); // 随机波动} else {rnd -sum; }if(isInteger true) {rnd Math.floor(rnd); } sum rnd; list.push(rnd); }return list; }波动均分的「快速分配」方案在算法效率上是高效的并且「快速分配」适用于「无穷集合」。如何使用「穷举法」校验「快速分配」的全面性「穷举法」能直接返回分配组合的总数而「快速分配」只能随机返回一次组合笔者是通过大数量地调用「快速分配」算法并累积不重复组合来验证「快速分配」的全面性。代码如下console.log(exhaustWave(5, 4, 4)); // 组合总数: 3951let res {}, count 0, len 10000; for(let i 0; i len; i) { let name quickWave(5, 4, 4).join(_); res[name] ! true (res[name] true, count); }console.log(count); // len次快速分配后的组合总数通过调整变量 len 可以发现当 len 越来越大输出的结果就越逼近 3951当到达一定量级后输出的结果就是 3951。结语可能网上有类似的算法存在不过笔者学识太浅没有找到对应的算法所以自己生造了这个算法如果有何不妥之处欢迎指正。希望本文能帮助到您点赞转发让更多的人也能看到这篇内容(收藏不点赞都是耍流氓-_-)关注 我享受文章首发体验每周重点攻克一个前端技术难点。更多精彩前端内容私信 我 回复“教程”原文链接https://aotu.io/notes/2018/01/11/waveaverage/作者凹凸实验室
