我有一個六面骰子，如何投儘可能少的次數內模擬一個二十面骰子?

再次修改
/*允許對得到的數運算，或者定義規則，比如(比如)擲出六可以再來一次。擲出某些特殊數組作廢重擲。&
原本的題目對次數的描述不合理，已改。歡迎補充*/
//投5個均勻六面骰子，如何隨機取得20以內的整數?
//推廣到n個x面骰子，取得k以內的隨機數

我看了目前所有的6個回答，似乎答者都沒有資訊理論的背景，所以沒有給出最優解。

首先給出一般問題「多少個n面骰子能模擬k面骰子」的精確值：

如果要求為整數，需要知道一共需要模擬多少個k面骰子。假如一共需要m個k面骰子，需要n面骰子的次數是

其中是向上取整函數，， , 。

這個公式是香農資訊理論裏來的。對應的資訊理論問題是"一個k進位的隨機數發生器產生的信息量等價於多少個n進位的隨機數發生器"。

理由如下：

根據信息量的定義

當i取值範圍是0到n-1，且每個取值等概出現的時候

因此，

一個均勻的n面骰子每次給出的結果的信息量為 bit

確定一個0到(k-1)的隨機數需要 bit。

所以個n面骰子提供的信息量等於一個k面骰子拋擲一次得到的信息量。

有了理想值，下面就是具體實現。實現過程需要使用k進位數和n進位數相互轉換。為表示方便，先以6面骰子模擬20面骰子為例。然後再進行推廣。

先算得，理想值

，

也就是說，一個20面篩子理論上需要1.672個6面骰子。m個20面骰子等價於m*log2（20）/log2（6）個6=1.672m個面骰子。

第一步：拋擲個6面骰子，或拋擲一個6面骰子次。

用L來表示骰子的拋擲次數，即

得到的6面骰子的數記為

然後直接拼接成一個L長的6進位數。下標表示進位。

將從6進位轉換為20進位，將會得到一個長度不大於m+1的20進指數，計為。m個20面骰子的結果為的後m位。位數不足開頭補0。

實例1

用6面骰子模擬3個20面骰子的結果

計算得，共需要次拋擲

假設6次拋擲結果是2 6 4 1 3 3，先轉化為0~5，得到（每個數減一)1 5 3 0 2 2.

合併成六進指數 =153022

六進指數轉十進位（如果會六進指數轉20進位可略過次步驟直接轉換）得到

再把轉20進位:

除以20得745餘18 所以第一個模擬的20面骰子的結果是18+1=19（因為餘數取值是0--19）

745除以20得 37餘5 所以第二個模擬的骰子結果是5+1=6

37除以20得1餘17 所以第三個模擬的骰子的結果是17+1=18

最終用6個6面骰子的結果 6 4 1 3 3模擬了3個20面骰子的拋擲結果19 6 18。

先扔一個a，如果a為6就重來。這樣a是1到5的等概率分佈。

再扔一個b，如果b為5或6就重來，這樣b是1到4的等概率分佈。

顯然a和b獨立，這樣4a+b-4即為1到20的等概率分佈

一個骰子和n個骰子沒什麼區別，一個骰子拋n次等價於n個骰子。這題本質上是由一個分佈生成另一個分佈，用簡單的拒絕採樣即可。

對於模擬20面骰子的方法，連續拋兩次骰子，有36種等可能的結果，我們事先約定11 12 ... 16 21 22 ... 26 ... 36 41 42這二十種結果是有效結果，對應於二十面骰子的1 2 ... 20，如果拋出另外十六種結果，則結果無效。重複上述過程，相當於你在拋一個20面的骰子。

可以推廣到K面骰子的情況，只要滿足6^n&>K，取最小的n作為拋骰子的次數即可。

該方法不保證次數最少，但是簡單普適。

關於採樣的邏輯，可以看一下這兩篇博客，不涉及任何複雜的數學知識。

《漫談MCMC與Gibbs採樣（一）—— 採樣背後的邏輯》https://blog.csdn.net/weixin_43661031/article/details/94399339

《漫談MCMC與Gibbs採樣（二）—— 拒絕採樣》https://blog.csdn.net/weixin_43661031/article/details/94399263

是 ①5個骰子按順序依次投擲，還是 ②5個骰子一起投擲且我們無法對骰子做出區分？

如果是①，答主加了【能廢除】，從總排列數中，廢除一部分，直到排列數變為20的倍數，再隨意分配（暫時沒考慮是否有簡便方法）。

如果是②，值得思考一番。

投n次m面色子，換算成m進位的小數，然後乘以k+1取整。能平均分就會平均分，不能平均分的話其他方法也分不了。

1/6來生成1/20，有限次肯定是不可能的

1/6通過加法乘法有限次生成的元素是固定的

這個問題的提法很不清晰，甚至可以認為有問題，希望題主能夠澄清一下。

關鍵問題是，5個骰子的擲法是怎樣的？

每個骰子只能擲一次嗎？如果只能擲一次，那麼一共有6^5種排列，這個排列數是不被20整除的，也就無法做到等概率。

每個骰子可以擲多次嗎？如果這樣，那麼和一個骰子並沒有區別，等價於一個骰子擲多次。

不知道是不是最少，（A）4×（B）5=20，第一次投A，反覆投到1~4，如果出現5、6就重新投①；第二次投B，反覆投到1~5；5A+B-5，得結果。

①當特殊情況連續兩次投出A=5或6無效值的時候，以2進位思想兩次結果可以轉化為1~4：55=1；56=2；65 = 3；66=4

投A：至多需要2次。需要1次的概率是4/6, 需要2次的概率是2/6。

投B：5/6的概率1次出結果，需要2次的概率是1/6*5/6，需要3次的概率是1/36 * 5/6，需要4次的概率忽略不計

那麼模擬20面投資，扔2次的概率是20/36=55.555%，扔3次的概率是5/18 + 5/54=37.037%，扔4次及之內的概率已經非常接近100%

淘寶9塊9包郵能買d4到d20一套，有的還加送x10d10一粒讓你一次就能直接投d100，何必那麼費勁用普通骰子模擬d20

現在題目修改了，給出一種方法。

兩個骰子，一次只擲一個。這樣能夠區分出骰子1和2。

我們讓骰子1的數值為，骰子2的數值為。現在，我們計算的值。如果這個值大於20，那麼就從頭開始。否則這個值就是最終生成的隨機數。

如果要求20以內的所有正整數（1-20）等概率出現的話，是不可能的。原因是五個骰子最終組成的可能情況數是6的5次方（7776），而這個數不是一個20的倍數，所以無法把五個骰子的所有可能情況分成20個大小相同的組，所以就不能實現。即使改變骰子的數量，也不可能實現6面骰子生成20以內的均勻分佈正整數（因為6不是5的倍數而20是5的倍數，6的任何正整數次方都不可能是5的倍數，更不可能是20的倍數）。

通過n個x面骰子，取得k以內的均勻分佈的隨機正整數是有可能的當且僅當x^n是k的倍數。如果有一個x面骰子可以擲任意多次，那麼當且僅當x包含了k所有的質因子時，可以取得1-k的均勻分佈。（這裡的包含是k中的每一個質因子都要在x中出現，但即使k中出現多次，x中也只需要出現至少一次。）

在這裡，我們假設每一個骰子都有一個特點使得它與其他骰子不同（例如，每一個骰子都有它專屬的顏色）。

如果不要求所有生成的數值概率相等，那麼會簡單很多，但基本上也失去了意義。