「学习笔记」随机数据

超、凢脫俗 2024-03-23 22:01 67阅读 0赞

### 前置知识——随机函数[\#][Link 1] ###

我们日常用的随机函数为 `rand()`，虽然比较慢，但已经足够用了，它会随机生成一个范围在 \[0,231−1\]\[0,231−1\] 中的一个数。

使用时要用随机种子 `seed`，可以使用 `srand(seed)` 来设置、更改随机种子，当然，不初始化也是可以的，只是同一个程序用相同的 `seed`、相同的机器、相同的编译器下，随机的结果将会是一样的。

`mt19937` 是一个随机数生成器类，效用同 `rand()`，随机数的范围同 `unsigned int` 类型的取值范围。

其优点是随机数质量高（一个表现为，出现循环的周期更长；其他方面也都至少不逊于 `rand()`），且速度比 `rand()` 快很多。

### 随机树[\#][Link 2] ###

#### 并查集构造随机树[\#][Link 3] ####

const int N = 1e5 + 1;
    
    int n;
    
    struct union_find_set {
        int fa[N], siz[N];
    
        int &operator [] (const int& x) {
            return fa[x];
        }
    
        void reset() {
            for (int i = 1; i <= n; ++ i) {
                fa[i] = i;
                siz[i] = 1;
            }
        }
    
        int find(int x) {
            return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
        }
    
        void Union(int x, int y) {
            int fx = find(x), fy = find(y);
            if (siz[fx] <= siz[fy]) {
                swap(fx, fy);
            }
            fa[fy] = fx;
            siz[fx] += siz[fy];
        }
    } ufs;
    
    int main() {
        srand(time(0));
        n = rand() % 10 + 1;
        cout << n << '\n'; // 有多少个点
        int cnt = 0;
        ufs.reset(); // 并查集初始化
        while (cnt != n - 1) {
            int x = rand() % n + 1, y = rand() % n + 1;
            if (ufs.find(x) != ufs.find(y)) {
                cout << x << ' ' << y << '\n'; // 边
                ufs.Union(x, y); // 并查集合并
                ++ cnt;
            }
        }
        return 0;
    }

#### 连向编号更小的节点[\#][Link 4] ####

int main() {
        srand(time(0));
        int n = rand() % 10 + 1;
        cout << n << '\n'; // 有多少个点
        for (int i = 2; i <= n; ++ i) {
            int x = rand() % (i - 1) + 1;
            cout << x << ' ' << i << '\n';
        }
        return 0;
    }

### 随即图[\#][Link 5] ###

pair<int, int> e[N << 2];
    map<pair<int, int>, bool> mp;
    
    int main() {
        mt19937 rnd(time(0));
        int n = rnd() % 20 + 2;
        int m = (n + rnd() % n + 1);
        cout << n << ' ' << m << '\n'; // 有多少个点和边
        int cnt = 0;
        for (int i = 2; i <= n; ++ i) { // 先构造一棵树
            int x = rnd() % (i - 1) + 1;
            ++ cnt;
            e[cnt] = {x, i};
            mp[{x, i}] = 1;
        }
        for (int i = n; i <= m; ++ i) { // 再随机剩下的边
            int x, y;
            do {
                x = rnd() % n + 1, y = rnd() % n + 1;
            } while (x == y || mp[{x, y}]); // 判重
            e[++ cnt] = {x, y};
            mp[{x, y}] = 1;
        }
        random_shuffle(e + 1, e + m + 1); // 打乱顺序
        for(int i = 1; i <= m; ++i)
        cout << e[i].first << ' ' << e[i].second << '\n';
        return 0;
    }

### 随机子区间[\#][Link 6] ###

int l = rand() % n + 1, r = rand() % n + 1;
    if (l > r)  swap(l, r);
    cout << l << ' ' << r << '\n';

[Link 1]: https://www.cnblogs.com/yifan0305/p/17617875.html#%E5%89%8D%E7%BD%AE%E7%9F%A5%E8%AF%86%E9%9A%8F%E6%9C%BA%E5%87%BD%E6%95%B0
[Link 2]: https://www.cnblogs.com/yifan0305/p/17617875.html#%E9%9A%8F%E6%9C%BA%E6%A0%91
[Link 3]: https://www.cnblogs.com/yifan0305/p/17617875.html#%E5%B9%B6%E6%9F%A5%E9%9B%86%E6%9E%84%E9%80%A0%E9%9A%8F%E6%9C%BA%E6%A0%91
[Link 4]: https://www.cnblogs.com/yifan0305/p/17617875.html#%E8%BF%9E%E5%90%91%E7%BC%96%E5%8F%B7%E6%9B%B4%E5%B0%8F%E7%9A%84%E8%8A%82%E7%82%B9
[Link 5]: https://www.cnblogs.com/yifan0305/p/17617875.html#%E9%9A%8F%E5%8D%B3%E5%9B%BE
[Link 6]: https://www.cnblogs.com/yifan0305/p/17617875.html#%E9%9A%8F%E6%9C%BA%E5%AD%90%E5%8C%BA%E9%97%B4