假设我有一个n侧加载的模具,当我滚动它时,每个侧面k都有一些概率p k.我很好奇是否存在静态存储此信息的良好算法(即,对于一组固定的概率),以便我可以有效地模拟模具的随机滚动.
目前,我有一个针对此问题的O(lg n)解决方案.想法是存储所有k的前k个边的累积概率的表,它们生成范围[0,1)中的随机实数并且对表执行二元搜索以获得其累积的最大索引值不大于所选值.我更喜欢这个解决方案,但运行时没有考虑概率似乎很奇怪.特别是,在一方总是出现或值均匀分布的极端情况下,可以使用朴素的方法在O(1)中生成滚动的结果,尽管我的解决方案仍然需要采用多个步骤的对数.
有没有人对如何以某种方式在运行时"自适应"的方式解决这个问题有任何建议？
编辑:基于这个问题的答案,我写了一篇文章,描述了这个问题的许多方法,以及他们的分析.看起来Vose的别名方法的实现给出了Θ(n)预处理时间和每次掷骰的O(1)时间,这确实令人印象深刻.希望这是对答案中包含的信息的有用补充!
language-agnostic random algorithm probability data-structures
假设我正在写一个简单的运气游戏 - 每个玩家按Enter键,游戏会在1-6之间为他分配一个随机数.就像一个立方体.在游戏结束时,数量最多的玩家获胜.
现在,让我们说我是骗子.我想写游戏,所以玩家#1(将是我)的概率为90%得到6,而2%得到每个剩下的数字(1,2,3,4,5).
如何随机生成数字,并设置每个数字的概率？
我有一大堆的项目比范围的大小从1-10。
我想根据物件的百分比或机会确定该物件的大小。
例如：
物品成为大小的 机会1 = 50% 机会
物品成为大小的 机会5 = 20% 机会
物品成为大小的 机会10 = 5% 机会
我知道我当然需要为此使用Random发电机。
但是只是想知道你们中的某些人将如何使用C＃进行逻辑处理？