日志
經(jīng)常使用的小程序
||
聲明：摘自牛客
輸出隨機(jī)數(shù)：從0...n-1中等概率隨機(jī)輸出m個不重復(fù)的數(shù)字，并且假設(shè)n遠(yuǎn)大于m
knuth(int n, int m)
{
srand((unsigned int)time(0));
for (int i = 0; i < n; i++) {
if (rand () % (n - i) < m) {
cout << i << endl;
m--;
}
}
}
由這個for循環(huán)循環(huán)n次，且在滿足條件時才輸出i,可知，輸出m個不同值的要求已滿足，因為每次輸出的都是i值，而i值每次都是不一樣的，m--保證了程序在輸出了m個值后就停止循環(huán)。
在i=0時，rand()%(n-i)的取值范圍為0到n-1，共n個數(shù)，此時要輸出0只需要rand()%(n-i)小于m，故i=0被輸出的概率為m/n;
在i=1時，rand()%(n-i)的取值范圍為0到n-2，共n-1個數(shù)，若i=0沒有被輸出，則m--未被執(zhí)行，此時i=1被輸出的概率為m/(n-1)，若i=0已經(jīng)被輸出了，則m變?yōu)閙-1，此時i=1被輸出的概率為(m-1)/(n-1)；由概率論的知識，可知此時i=1被輸出的概率為
P=(1-m/n)*(m/(n-1))+m/n*((m-1)/(n-1))=m/n；以此類推，可知每個數(shù)被輸出的概率都為m/n
