iT邦幫忙

2

【c/c++學習筆記】利用rand()產生隨機數,教你模擬不公平的骰子

c++

哈囉~ 大家好,
今天教大家如何用函式庫<stdlib.h>裡面的rand()函數產生隨機數,
rand()的效果可以產生從0~RAND_MAX(int的最大值)之間的隨機整數,
譬如說這支程式可以產生十個隨機數:

#include <iostream>
#include <stdlib.h>
using namespace std;

int main() {
    for(int i = 0 ; i < 10 ;i++){
        cout << rand() << endl;
    }
    return 0;
}

結果:

1804289383
846930886
1681692777
1714636915
1957747793
424238335
719885386
1649760492
596516649
1189641421

每次執行程式的結果都一樣?

神奇的事情發生了,
你會發現,你每次重新執行程式的時候,
都一樣是產生這十個數字,
咦咦? 既然都產生固定的數字,這數字一點也不隨機呀?
不是預期每次重新執行程式的隨機數都要不一樣嗎?

原因是這樣的

由於電腦實際上並沒有辦法自己產生「真正的亂數」,只能透過複雜的數學演算法模擬出類似亂數的數值資料,而在模擬亂數時,需要設定一個亂數種子,電腦會根據這個亂數種子來計算出一連串的亂數,相同的亂數種子就會產生相同的亂數序列,所以如果要讓產生的亂數每次都不同,就要設定不同的亂數種子。
(參考資料: C/C++ 使用 rand 函數產生隨機亂數教學與範例程式碼)

所以如果要讓每次執行程式的結果都不一樣的話,
必須要設定不同的亂數種子
設定亂數種子的函數為srand(int);

一般來說,會在程式加上srand( time(NULL));這一行,
讓亂數種子以現在的時間做設定,
這樣每次執行程式的結果就不同了

#include <iostream>
#include <cstdlib> /* 亂數相關函數 */
#include <ctime>   /* 時間相關函數 */
using namespace std;

int main() {
    srand( time(NULL));
    for(int i = 0 ; i < 10 ;i++){
        cout << rand() << endl;
    }
    return 0;
}

另外,教大家如果是要任意浮點數範圍或是任意整數範圍的隨機數怎麼寫

0~1之間的隨機浮點數

double x = (double) rand() / (RAND_MAX + 1.0);

a~b之間的隨機浮點數

double x = (b - a) * rand() / (RAND_MAX + 1.0) + a;

a~b之間的隨機整數

int x = rand() % (b - a + 1) + a;

以上可以從指定的範圍機率大概均等的取出一個數,
那如果是要模擬不公平的骰子怎麼辦呢?
比如說希望擲出1點的機率是擲出2~6點的2倍之類的。

這邊正好有一道題適合練習。

leetcode- 528. Random Pick with Weight

參考題目: leetcode- 528. Random Pick with Weight
題意: 給你一個陣列,陣列裡的每個數表示indexi出現的比例。
譬如說input = [1,2,2],那你產生的隨機數就要有1:2:2的機率產生0,1,2。

參考程式:
首先我們先做機率的累加,
譬如說input是[a,b,c]好了,
累加機率就是[a,a+b,a+b+c]
思路就是產生一個[0,a+b+c)區間的隨機數,
若隨機數落在[0,a)就回傳0
隨機數落在[a,a+b)就回傳1
隨機數落在[a+b,a+b+c)就回傳2
(多個隨機數的情形再自行類推)

c++ 程式: 584ms, AC

class Solution {
public:
    vector<int> accu_prob;
    Solution(vector<int>& w){
        accu_prob.resize(w.size());
        accu_prob[0]= w[0];
        for(int i=1 ;i<w.size();i++){
            accu_prob[i]= accu_prob[i-1]+w[i];
        }
    }
    
    int pickIndex() {
        int R = rand() % accu_prob.back();
        for(int i =0 ; i<accu_prob.size();i++){
            if(R<accu_prob[i]){
                return i;
            }
        }
        return accu_prob.size()-1;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */

但是這支程式目前還有很大的優化空間,
若是要查詢隨機數落在哪個區間,
用for迴圈慢慢搜實在太耗時了,
建議搭配「二分查找」的技術

c++ 程式(二分查找): 180ms, AC

class Solution {
    //函數功能: 回傳在排序陣列中,第一個大於目標值的位置
    int firstGreaterEqual(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) 
                left = mid + 1;
            else
                right = mid;
        }
        return right;
    }
public:
    vector<int> accu_prob;
    Solution(vector<int>& w){
        accu_prob.resize(w.size());
        accu_prob[0]= w[0];
        for(int i=1 ;i<w.size();i++){
            accu_prob[i]= accu_prob[i-1]+w[i];
        }
    }
    
    int pickIndex() {
        int R = rand() % accu_prob.back();
        return firstGreaterEqual(accu_prob, R);
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */

尚未有邦友留言

立即登入留言