如何用一個1-8隨機生成器製作一個1-7隨機數生成器？

using namespace std;

int Rand8()
{
int n =1 + rand()%8;
return n;
}
int Rand7()
{
int n;
do
{
n = Rand8();
} while (n&>7);

return 1+n%7;
}
int main()
{
int result[] = {0,0,0,0,0,0,0};
int before[] = {0,0,0,0,0,0,0,0};
for (int i = 0 ; i &< 10000; i++) { before[Rand8()-1] += 1; } for(int i = 0; i&< 8; i++) { cout&<&< "num:"&<&

一萬次實驗：Rand8，次數都在1200多左右，random7次數都在1400左右。

@崔恩馳

個人覺得，在8的 n次方的空間上，大概不存在對1～7的均勻映射。

（見評論區）

還有 @小科的答案：

如果一定要是嚴格等概率分布的話，本質上都要靠出現8時重新產生隨機數直到產生1-7之間的，不可能保證在給定步數內結束，因為產生n次1-8隨機數的sigma域里沒有概率為1/7的事件。

從信息的角度來說，我們每次使用rand8()，獲得的信息量都是3bit，或者說8種狀態中的一種，那麼n次的狀態總量是8的n次方，或者說3n bit。以這樣的一個空間，大概沒有什麼優雅的方案可以均勻的映射到一個每次都是7種狀態的空間的。

int rand7()
{
static int sum;
sum+=rand8();
if(sum&>7)sum-=7;
return (sum%7 + 1);
}


此種演算法有知友驗證了從概率來說，7個數字產生概率都是相同的，但是數字之間的獨立性卻會有很大問題。

這個簡單來說，假設當前sum＝0，那麼下次rand7返回值中，1會是2/8，其他是1/8。數據的獨立性會有問題。但是每個數字的概率是相同的——其實如果你依次返回1-7，概率也是相同的，但顯然這不能算是啥隨機數。

如果要獨立性好，但對性能沒有要求，則可以用如下的方法：

int rand7()
{
int temp=rand8();
if(temp==8)return rand7();
else return temp;
}


這個很好理解，如果等於8則再取一次。但是理論上存在一長串8，導致效率低下，並且原理上是可能會有無限個連續的8出現以至於沒有結果。

int rand7()
{
static int sum;
int temp=rand8();

sum+=rand8();
if(sum&>7)sum-=7;
if(temp==8)return (sum%7 + 1);
else return temp;
}


這個方法是，一方面記錄總和，如果rand8返回的是8，那利用sum對7取餘數來得到隨機值。這個方案的隨機性我還沒去驗證，不過至少可以避免上一種方法的極端情況，但是還是犧牲了隨機性的。

更高級的解法大概是要等數學專業的人來做解答了，大概這應該可以對應到數論或者某個數學現成的猜想或者命題。

@Eidosper 的求和只寫了一次，應該是typo吧……

……這個逼是我掉的我裝完就走……

證明：因為每次累加都使得有一個數的概率比其它6個數高一點，第1次累加後這個數為1，第2次累加後這個數為2，依此類推。第一次累加時高出的部分是1/8，由歸納法，若第n-1次時高出的部分是，即

while ((r = randN()) &>= M) {}


當然，這樣對於N比M大得多時這樣會導致必須調用很多次randN函數，這時可以利用下面的代碼:

int k = N / M;

while (true) {
int tmp = randN();
if (tmp &> k * M) continue;
return tmp % M;
}


就相當於對取M的同餘數，對於多出來的部分直接丟掉。

• f(N) = k*N,其中k = ,這時生成的序列為(0, k , 2k,...,kN)，我們需要連續的數字，我們必須補齊0, k中的數，

• 如果k&<=N,那麼我們只需要再加上randk(),即可，也就是k * randN() + randK(),這樣就生成了(0, 1, ...,kN+k-1)這個序列。

• 如果k &> N, 那麼繼續步驟1,最終需要構造一個連續的序列(0,1,...P)其中P&>M,然後由randP()生成randM();

例如: 由rand5()構造rand7(),由於=2 ，則生成了（0, 2, 4, 6, 8），這個序列，只需要再加上rand2()就可以構造出(0, 1, 2, .., 9)這個序列,也就是rand10().

首先用隨機用rand8() 生成rand7() 是沒有固定步數內的映射方案。原因是，8^n不可能被7整除，導致無法你不可能通過rand8()找到一種有限步驟內的組合，使得映射到rand7()的概率是均勻分布的。

所以唯一的方法就是獲取一次rand8()，如果得到的是8，那麼重新獲取。

反過來討論一種情況，就是用rand7()如何生成rand8()。

int ret = random8();

抽到 8 重抽。

這個方法有人指出這種 rejection sampling「不能保證有限步數內結束」。

於是有個改進方案：

首先題目肯定要求的是隨機分布。

import random
random.seed(int("".join([str(rand8()) for i in xrange(8)])))
rand7 = lambda: random.randint(0, 7)


當然是用從低質量隨機源生成高質量隨機數的一般方法啊（光速逃