Re: [心得] 亂數不重複的方法
假設要從十張裡面抽出三張
我們就知道每張牌被抽出來的機率是 3/10
所以就可以這樣寫
for ( size_t i=0; i<10; ++i ) {
if ( rand() % 10 < 3 ) { // 小於 3 代表被選中
cout << i ;
}
}
但是這樣有個問題是，被選出來的不一定是三張，
可能是 0 張，也可能是 10 張，雖然說平均是 3 張沒錯。
所以我們要在這個過程控制一下，試考慮一個狀況：
當我第一張的 rand()%10 就小於 3 被選中，
那剩下的 9 張裡面其實只能有兩張被選中，
所以之後的每張牌其實機率就不是 rand()%10 < 3，
而是 rand()%9 < 2，因為剩下的九張牌裡面每個人中獎的機會是 2/9。
又，假設繼續選選選選到第 9 張，總共有兩張被選中，
還有一張沒出來，那最後一張被選中的機率就一定會是 1/1。
利用這種機率控制的方法，就可以讓抽完的牌數一定是 3。
所以我們需要記住兩個值，
1. 已選出多少牌：n
2. 還剩下多少牌：這個可以用 10 - i 得到
for ( size_t i=0; i<10; ++i ) {
if ( rand() % (10-i) < (3-n) ) {
++ n ;
cout << i ;
}
}
空間複雜度 O(1)，時間複雜度 O(總牌數)。
當總牌數遠大於要抽出牌數的話，這個方法就不適用。
--
To iterate is human, to recurse, divine.
遞迴只應天上有, 凡人該當用迴圈. L. Peter Deutsch
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.45.107.213
推
02/13 08:31, , 1F
02/13 08:31, 1F
→
02/13 10:41, , 2F
02/13 10:41, 2F
推
02/13 11:05, , 3F
02/13 11:05, 3F
推
02/13 12:05, , 4F
02/13 12:05, 4F
→
02/13 12:06, , 5F
02/13 12:06, 5F
推
02/13 12:48, , 6F
02/13 12:48, 6F
→
02/15 14:01, , 7F
02/15 14:01, 7F
→
02/16 19:01, , 8F
02/16 19:01, 8F
討論串 (同標題文章)
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
