Sinh ngẫu nhiên trong C++

Xét đoạn code sinh ngẫu nhiên \(10^7\) số sau:

#include <bits/stdc++.h>
using namespace std;

signed main(){
    long long sum = 0;
    for (int i = 1; i <= 10000000; i++){
        sum += rand() % 1000000;
    }

    cout << "Average value is: " << sum / 10000000 << endl; // 16382
}

Sinh \(10^7\) ngẫu nhiên trong khoảng \([1, 10^6]\), đáp án có lẽ sẽ nằm trong khoảng \(5 \times 10^5\). Tuy nhiên, khi chạy trên Codeforces, ta nhận được kết quả như sau:

16382

Đây là một con số quá nhỏ so với đáp án chúng ta mong muốn. Vậy chuyện gì đã xảy ra?

Khi mới làm quen với sinh số ngẫu nhiên trong C++, hầu hết mọi người sẽ tìm đến hàm rand() đầu tiên. Nếu tra trên C++ Documentation, bạn sẽ thấy rằng hàm này có thể sinh ra một số ngẫu nhiên trong đoạn \([0, RAND\_MAX]\) với \(RAND\_MAX\) là một hằng số cho trước. Cũng trong C++ Documentation, ta được biết \(RAND\_MAX\) là một hằng số có giá trị phụ thuộc vào trình biên dịch, với đảm bảo giá trị đó nhỏ nhất là \(32767\). Đây là một giá trị quá nhỏ, sẽ rất dễ khiến chương trình chạy không đúng. Đây là một ví dụ của một chương trình sử dụng hàm rand() gây ra kết quả không đúng: https://codeforces.com/contest/1039/submission/42526311

Giải pháp

Ta có thể sử dụng mt19937 sử dụng thuật toán Mersenne Twister dựa trên số nguyên tố \(2^{19937}-1\).

Ngoài ra, trong C++ có hàm uniform_int_distribution sẽ giúp cân bằng tỉ lệ sinh ra của các số trong đoạn

#include <bits/stdc++.h>
using namespace std;

mt19937 rng(time(0));

signed main(){
    long long sum = 0;
    for (int i = 1; i <= 10000000; i++){
        sum += uniform_int_distribution<int>(0, 1000000)(rng);
    }

    cout << "Average value is: " << sum / 10000000 << endl; // 499775
}

Ở đoạn code trên, time(0) chính là seed, đây là seed có độ chính xác lên đến giây (tức nếu code chạy trong thời gian giống nhau thì sẽ cho kết quả giống nhau). Để tăng tính ngẫu nhiên và giúp code của mình tránh bị hack như trường hợp ở bên trên, ta có thể sử dụng một seed có độ chính xác mili giây.

#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

signed main(){
    long long sum = 0;
    for (int i = 1; i <= 10000000; i++){
        sum += uniform_int_distribution<int>(0, 1000000)(rng);
    }

    cout << "Average value is: " << sum / 10000000 << endl;
}

random_shuffle và shuffle

Ta cần lưu ý rằng, hàm random_shuffle() để tráo một mảng cũng sử dụng hàm rand() nên việc sử dụng hàm này cũng sẽ dễ làm mất tính ngẫu nhiên. Thay vào đó ta có thể sử dụng hàm shuffle và truyền mt19937 vào hàm.

#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

signed main(){
    vector<int> val(10);
    iota(val.begin(), val.end(), 1);

    shuffle(val.begin(), val.end(), rng);

    for (auto v : val) cout << v << " "; // 5 6 4 10 1 7 9 2 8 3 
}

Lời kết

Qua bài viết này, ta đã học được một cách thay thế hàm rand() để sinh số ngẫu nhiên. Hàm rand() chỉ đủ tốt nếu ta cần sinh ra những số rất nhỏ, với những số to nếu sử dụng rất dễ khiến chương trình chạy sai và bạn sẽ mất rất nhiều điểm cho bài tập. Thay vào đó, sử dụng mt19937 cùng với seed chrono::steady_clock::now().time_since_epoch().count() và hàm uniform_int_distribution sẽ là lựa chon an toàn và tối ưu nhất để giải quyết bài toán sinh ngẫu nhiên. Hi vọng mọi người có thể áp dụng những gì học được qua bài viết này để tự áp dụng vào chính các bài tập của mình nhé.

Xem  thêm các kiến thức thú vị tại: https://www.facebook.com/codedreamedu và https://codedream.edu.vn/hoc-thuat-toan/