假設(shè)我有一個(gè)n面加載的模具，其中每邊k 滾動(dòng)時(shí)都有幾率p k上升。我很好奇是否有一個(gè)好的算法可以靜態(tài)地存儲(chǔ)此信息（例如，針對(duì)一組固定的概率），以便可以有效地模擬骰子的隨機(jī)滾動(dòng)。目前，我有一個(gè)O（lg n）解決方案。這個(gè)想法是存儲(chǔ)一張表，存儲(chǔ)所有k的前k個(gè)邊的累積概率，它們?cè)赱0，1）范圍內(nèi)生成一個(gè)隨機(jī)實(shí)數(shù)，并對(duì)該表執(zhí)行二進(jìn)制搜索以獲取最大的索引，該索引的累積值不大于所選值。我寧愿喜歡這種解決方案，但運(yùn)行時(shí)沒有考慮這些可能性似乎很奇怪。特別地，在極端情況下，一側(cè)總是出現(xiàn)或值均勻分布，盡管我的解決方案仍將采取對(duì)數(shù)步的許多方法，但可以通過樸素的方法在O（1）中生成滾動(dòng)結(jié)果。有人對(duì)運(yùn)行時(shí)以某種“自適應(yīng)”方式解決此問題有任何建議嗎？編輯：基于對(duì)這個(gè)問題的回答，我寫了一篇文章，描述了解決這個(gè)問題的許多方法以及它們的分析?？雌饋鞻ose對(duì)別名方法的實(shí)現(xiàn)為每個(gè)模具輥提供了Θ（n）預(yù)處理時(shí)間和O（1）時(shí)間，這確實(shí)令人印象深刻。希望這是對(duì)答案中包含的信息的有用補(bǔ)充！
3 回答
月關(guān)寶盒
TA貢獻(xiàn)1772條經(jīng)驗(yàn) 獲得超5個(gè)贊
使用平衡的二叉搜索樹（或數(shù)組中的二叉搜索）并獲得O（log n）復(fù)雜度。每個(gè)骰子結(jié)果只有一個(gè)節(jié)點(diǎn)，并且鍵是觸發(fā)該結(jié)果的間隔。
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)
該解決方案的優(yōu)點(diǎn)是實(shí)現(xiàn)起來非常簡(jiǎn)單，但是仍然具有很好的復(fù)雜性。
慕娘9325324
TA貢獻(xiàn)1783條經(jīng)驗(yàn) 獲得超4個(gè)贊
我正在考慮對(duì)您的桌子進(jìn)行細(xì)化處理。
您可以創(chuàng)建一個(gè)長(zhǎng)度為xN的整數(shù)數(shù)組，而不是使用每個(gè)模具值的累加表，其中x最好是一個(gè)較大的數(shù)字，以提高概率的準(zhǔn)確性。
使用索引（由xN歸一化）作為累積值填充此數(shù)組，并在該數(shù)組中的每個(gè)“插槽”中存儲(chǔ)該索引出現(xiàn)時(shí)將要擲出的骰子。
也許我可以舉一個(gè)例子來解釋一下：
使用三個(gè)骰子：P（1）= 0.2，P（2）= 0.5，P（3）= 0.3
創(chuàng)建一個(gè)數(shù)組，在這種情況下，我將選擇一個(gè)簡(jiǎn)單的長(zhǎng)度，例如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之間的數(shù)字隨機(jī)化，然后簡(jiǎn)單地訪問該索引即可。
此方法可能會(huì)降低精度，但是增加x且精度就足夠了。
添加回答
舉報(bào)
0/150
提交
取消