作者csihcs (非天夜翔)
看板C_and_CPP
標題Re: [心得] 亂數不重複的方法
時間Sat Feb 13 11:03:16 2010
※ 引述《yoco315 (眠月)》之銘言：
: 假設要從十張裡面抽出三張
: 我們就知道每張牌被抽出來的機率是 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
還需要多少牌：k
: 2. 還剩下多少牌：這個可以用 10 - i 得到
: for ( size_t i=0; i<10; ++i ) {
: if ( rand() % (10-i) < (3-n) ) {
if ( rand() % (10-i) < k ) { // replace
: ++ n ;
-- k ; // replace
: cout << i ;
if( k == 0 ) break; // add
: }
: }
: 空間複雜度 O(1)，時間複雜度 O(總牌數)。
O(總需求數) <<<< 我講錯了。
: 當總牌數遠大於要抽出牌數的話，這個方法就不適用。
--
渴望飛翔在
自由的
風中，
期望逃離這拘束的
現實，
一切都讓他隨著
風而去，
獨自躲在
黑暗的
空氣中，
舔舐被狠狠撕裂的
傷口。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 211.74.9.2
→ s3748679:可以的話把k寫成常數，然後把所有的10改成k@@ 02/13 11:07
→ s3748679:n不就是紀錄已經抽幾張了@@，那條件直接寫k==n應該比較好 02/13 11:10
我的方式是用 k 而沒有 n
→ jhchou:時間複雜度一樣是O(總牌數) 02/13 11:11
多謝指教，原來是我的認知有錯。 m(_@_)m
推 s3748679:至少程式學聰明了些@@，不過還是可能要跑到總牌數。 02/13 11:18
※ 編輯: csihcs 來自: 211.74.9.2 (02/13 11:33)
→ FRAXIS:這問題有個有趣的延伸 如果總牌數是未知的該如何取? 02/13 12:50