Re: [心得] 亂數不重複的方法
※ 引述《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
→
02/13 11:07, , 1F
02/13 11:07, 1F
→
02/13 11:10, , 2F
02/13 11:10, 2F
我的方式是用 k 而沒有 n
→
02/13 11:11, , 3F
02/13 11:11, 3F
多謝指教，原來是我的認知有錯。 m(_@_)m
推
02/13 11:18, , 4F
02/13 11:18, 4F
※ 編輯: csihcs 來自: 211.74.9.2 (02/13 11:33)
→
02/13 12:50, , 5F
02/13 12:50, 5F
→
02/13 12:50, , 6F
02/13 12:50, 6F
討論串 (同標題文章)