加载骰子的数据结构？
加载骰子的数据结构？
提问于 2018-03-29 01:04:18
假设我有一个n边加载模，其中每边k都有一些概率PK，当我滚动它的时候。我很好奇是否有一个好的算法来静态地存储这个信息(例如，一个固定的概率集)，这样我就可以有效地模拟一个随机的模具辊。
目前，我有一个O(LG N)解决这个问题。其思想是存储所有k的第一个k边的累积概率表，它们在[0，1]范围内生成一个随机实数，并对该表执行二进制搜索，得到累积值不大于所选值的最大索引。我相当喜欢这个解决方案，但运行时没有考虑到这些可能性似乎很奇怪。特别是，在一边总是出现或数值均匀分布的极端情况下，可以使用朴素方法生成O(1)中的滚动结果，尽管我的解决方案仍将采取对数的许多步骤。
有没有人对如何在运行时以某种“自适应”的方式解决这个问题有任何建议？
回答 2
Stack Overflow用户
发布于 2018-03-29 09:06:42
其想法是，使用概率pk数组，并生成三个新的n元素数组，QK、AK和BK。每个QK是介于0到1之间的概率，每个AK和Bk是介于1和n之间的整数。
我们通过产生两个随机数r和s，在0到1之间产生1和n之间的随机数。设I=地板(R)*(N)+1。如果气<s，则返回艾其他返回比。别名方法的工作是研究如何生成QK、AK和BK。
Stack Overflow用户
发布于 2018-03-29 10:06:06
使用平衡的二进位搜索树(或数组中的二进制搜索)并获得O(Logn)复杂度。为每个死掉结果设置一个节点，并将键作为触发该结果的间隔。
function get_result(node, seed):
if seed < node.interval.start:
return get_result(node.left_child, seed)
else if seed < node.interval.end:
// start <= seed < end
return node.result
else:
return get_result(node.right_child, seed)这个解决方案的好处是实现非常简单，但仍然具有很好的复杂性。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/-100007854
复制相关文章
相似问题