wordpress 图片整理,知乎seo优化,做毕业设计网站需要的工具,wordpress菜单栏不显示不出来举个例子#xff0c;游戏中玩家推倒了一个boss#xff0c;会按如下概率掉落物品#xff1a;10%掉武器 20%掉饰品 30%掉戒指 40%掉披风。现在要给出下一个掉落的物品类型#xff0c;或者说一个掉落的随机序列#xff0c;要求符合上述概率。 一般人会想到的两种解法 第一种算…举个例子游戏中玩家推倒了一个boss会按如下概率掉落物品10%掉武器 20%掉饰品 30%掉戒指 40%掉披风。现在要给出下一个掉落的物品类型或者说一个掉落的随机序列要求符合上述概率。 一般人会想到的两种解法 第一种算法构造一个容量为100(或其他)的数组将其中10个元素填充为类型1武器20个元素填充为类型2饰品...构造完毕之后在1到100之间取随机数rand取到的array[rand]对应的值即为随机到的类型。这种方法优点是实现简单构造完成之后生成随机类型的时间复杂度就是O(1)缺点是精度不够高占用空间大尤其是在类型很多的时候。 第二种就是一般的离散算法通过概率分布构造几个点[10, 30, 60, 100]没错后面的值就是前面依次累加的概率之和是不是像斐波那契数列。在生成1~100的随机数看它落在哪个区间比如50在[30,60]之间就是类型3。在查找时可以采用线性查找或效率更高的二分查找时间复杂度O(logN)。 下面是第二种算法使用二分查找的实现: ?php
class DiscreteSample
{private $cdf;private $cnt;public function init($pdf){$this-cnt count($pdf);if($this-cnt 0)die(pdf size is empty);if(abs(array_sum($pdf) - 1) 0.00001)die(pdf sum not equal 1, sum:.array_sum($pdf));$this-_pdf2cdf($pdf);}private function _pdf2cdf($pdf){$this-cdf $pdf;for ($i1; $i $this-cnt; $i){ $this-cdf[$i] $this-cdf[$i - 1];}//因为浮点型精度问题最后一个值强制为1$this-cdf[$this-cnt - 1] 1;}public function next_rand(){$left 0;$right $this-cnt;$random mt_rand() / mt_getrandmax();while ($left $right - 1) {$mid intval(($left $right)/2);if($mid - 1 $this-cnt) break;if($random $this-cdf[$mid - 1])$left $mid;else$right $mid;}return $left;}
}
? Alias Method别名方法 别名算法最终的结果是要构造拼装出一个每一列合都为1的矩形若每一列最后都要为1那么要将所有元素都乘以4概率类型的数量 此时会有概率大于1的和小于1的接下来就是构造出某种算法用大于1的补足小于1的使每种概率最后都为1注意这里要遵循一个限制每列至多是两种概率的组合。 最终我们得到了两个数组一个是在下面原始的prob数组[0.4,0.8,0.6,1]另外就是在上面补充的Alias数组其值代表填充的那一列的序号索引如果这一列上不需填充那么就是NULL[3,4,4,NULL]。当然最终的结果可能不止一种你也可能得到其他结果。 等等这个问题还没有解决得到这两个数组之后随机取其中的一列比如是第三列让prob[3]的值与一个随机小数f比较如果f小于prob[3]那么结果就是3否则就是Alias[3]即4。 我们可以来简单验证一下比如随机到第三列的概率是1/4得到第三列下半部分的概率为1/4*3/5记得在第一列还有它的一部分那里的概率为1/4*(1-2/5)两者相加最终的结果还是3/10符合原来的pdf概率。这种算法初始化较复杂但生成随机结果的时间复杂度为O(1)是一种性能非常好的算法。 代码示例 ?php
class AliasMethod
{private $length;private $prob_arr;private $alias;public function __construct ($pdf){$this-length 0;$this-prob_arr $this-alias array();$this-_init($pdf);}private function _init($pdf){$this-length count($pdf);if($this-length 0)die(pdf is empty);if(array_sum($pdf) ! 1.0)die(pdf sum not equal 1, sum:.array_sum($pdf));$small $large array();for ($i0; $i $this-length; $i) { $pdf[$i] * $this-length;if($pdf[$i] 1.0)$small[] $i;else$large[] $i;}while (count($small) ! 0 count($large) ! 0) {$s_index array_shift($small);$l_index array_shift($large);$this-prob_arr[$s_index] $pdf[$s_index];$this-alias[$s_index] $l_index;$pdf[$l_index] - 1.0 - $pdf[$s_index];if($pdf[$l_index] 1.0)$small[] $l_index;else$large[] $l_index;}while(!empty($small))$this-prob_arr[array_shift($small)] 1.0;while (!empty($large))$this-prob_arr[array_shift($large)] 1.0;}public function next_rand(){$column mt_rand(0, $this-length - 1);return mt_rand() / mt_getrandmax() $this-prob_arr[$column] ? $column : $this-alias[$column];}
}
? 转载于:https://www.cnblogs.com/mmmzh/p/10140992.html
