为了账号安全,请及时绑定邮箱和手机立即绑定

加载的骰子的数据结构?

加载的骰子的数据结构?

九州编程 2020-02-04 15:53:24
假设我有一个n面加载的模具,其中每边k 滚动时都有几率p k上升。我很好奇是否有一个好的算法可以静态地存储此信息(例如,针对一组固定的概率),以便可以有效地模拟骰子的随机滚动。目前,我有一个O(lg n)解决方案。这个想法是存储一张表,存储所有k的前k个边的累积概率,它们在[0,1)范围内生成一个随机实数,并对该表执行二进制搜索以获取最大的索引,该索引的累积值不大于所选值。我宁愿喜欢这种解决方案,但运行时没有考虑这些可能性似乎很奇怪。特别地,在极端情况下,一侧总是出现或值均匀分布,尽管我的解决方案仍将采取对数步的许多方法,但可以通过朴素的方法在O(1)中生成滚动结果。有人对运行时以某种“自适应”方式解决此问题有任何建议吗?编辑:基于对这个问题的回答,我写了一篇文章,描述了解决这个问题的许多方法以及它们的分析。看起来Vose对别名方法的实现为每个模具辊提供了Θ(n)预处理时间和O(1)时间,这确实令人印象深刻。希望这是对答案中包含的信息的有用补充!
查看完整描述

3 回答

?
月关宝盒

TA贡献1772条经验 获得超5个赞

使用平衡的二叉搜索树(或数组中的二叉搜索)并获得O(log n)复杂度。每个骰子结果只有一个节点,并且键是触发该结果的间隔。


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)

该解决方案的优点是实现起来非常简单,但是仍然具有很好的复杂性。


查看完整回答
反对 回复 2020-02-04
?
慕娘9325324

TA贡献1783条经验 获得超4个赞

我正在考虑对您的桌子进行细化处理。


您可以创建一个长度为xN的整数数组,而不是使用每个模具值的累加表,其中x最好是一个较大的数字,以提高概率的准确性。


使用索引(由xN归一化)作为累积值填充此数组,并在该数组中的每个“插槽”中存储该索引出现时将要掷出的骰子。


也许我可以举一个例子来解释一下:


使用三个骰子:P(1)= 0.2,P(2)= 0.5,P(3)= 0.3


创建一个数组,在这种情况下,我将选择一个简单的长度,例如10。(即x = 3.33333)


arr[0] = 1,

arr[1] = 1,

arr[2] = 2,

arr[3] = 2,

arr[4] = 2,

arr[5] = 2,

arr[6] = 2,

arr[7] = 3,

arr[8] = 3,

arr[9] = 3

然后要获得概率,只需将0到10之间的数字随机化,然后简单地访问该索引即可。


此方法可能会降低精度,但是增加x且精度就足够了。


查看完整回答
反对 回复 2020-02-04
  • 3 回答
  • 0 关注
  • 502 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信