假設我有一個n面加載的模具，其中每邊k 滾動時都有幾率p k上升。我很好奇是否有一個好的算法可以靜態地存儲此信息（例如，針對一組固定的概率），以便可以有效地模擬骰子的隨機滾動。目前，我有一個O（lg n）解決方案。這個想法是存儲一張表，存儲所有k的前k個邊的累積概率，它們在[0，1）范圍內生成一個隨機實數，并對該表執行二進制搜索以獲取最大的索引，該索引的累積值不大于所選值。我寧愿喜歡這種解決方案，但運行時沒有考慮這些可能性似乎很奇怪。特別地，在極端情況下，一側總是出現或值均勻分布，盡管我的解決方案仍將采取對數步的許多方法，但可以通過樸素的方法在O（1）中生成滾動結果。有人對運行時以某種“自適應”方式解決此問題有任何建議嗎？編輯：基于對這個問題的回答，我寫了一篇文章，描述了解決這個問題的許多方法以及它們的分析?？雌饋鞻ose對別名方法的實現為每個模具輥提供了Θ（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)
該解決方案的優點是實現起來非常簡單，但是仍然具有很好的復雜性。
慕娘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且精度就足夠了。
添加回答
舉報
0/150
提交
取消