收录一些连续随机数生成的问题。

1. 指定数字之和

生成 n 个有序的非负实数，它们之和为 s。

思路是生成 $n - 1$ 个 $[0, s]$ 的实数，再加入 0 和 s，排序后求差分数组。这个思路很像组合数学里的隔板操作（球盒模型，球之间没有区别，盒子之间有区别）。

不知道有没有复杂度 $O(n)$ 的方法。

如何证明？我不太会计算高维概率，但是可以证明每个数的概率密度都是正确的，估计这个方法应该是合理的吧。

#include <bits/stdc++.h>

double randf() { return (double)rand() / RAND_MAX; }

std::vector<double> randNumsOfSum(int n, double s) {
    std::vector<double> a, res;
    a.push_back(0);
    for (int i = 0; i < n - 1; i++) {
        a.push_back(randf() * s);
    }
    a.push_back(s);
    std::sort(a.begin(), a.end());
    for (int i = 0; i < n; i++) {
        res.push_back(a[i + 1] - a[i]);
    }
    return res;
}

int main() {
    std::vector<double> a = randNumsOfSum(4, 4);
    for (auto i : a) {
        printf("%f ", i);
    }
    return 0;
}

更新：复杂度是 $O(n)$ 的方法是存在的，因为实际上我们求的是 n 维空间的一个正多边形上一点，那么可以套用下文三角形内一点。

2. 线性概率密度

生成概率密度 $f(x)=\dfrac{2x}{t}, x\in[0,t]$ 的随机浮点数。

事实上令上一题的 $n=3,s=t$，然后取 3 个数的第一个，再用 t 减一下就可以了。

当然这个过程简化后就是生成两个 $[0, t]$ 的浮点数，取较大值。

#include <bits/stdc++.h>

double randf() { return (double)rand() / RAND_MAX; }

double linearProbability(int t) {
    return std::max(randf(), randf()) * t;
}

int main() {
    for (int i = 0; i < 20; i++) {
        printf("%f\n", linearProbability(10));
    }
    return 0;
}

3. 三角形内一点

给出二维平面内三角形的三个顶点，随机生成三角形内部的一点。

首先得解决一个更弱的问题，怎么生成三角形 $(0, 0)(1, 0)(0, 1)$ 内一点？这个问题相当于求 $x+y\le 1$，其实就是求 $x+y+z=1$，又可以被“指定数字之和”那题的做法完美解决。

double randf() { return (double)rand() / RAND_MAX; }

void randPoint(double &x, double &y) {
    x = randf();
    y = randf();
    if (x > y) {
        std::swap(x, y);
    }
    y -= x;
}

那么回到原问题。我们知道一个二维空间经过线性变换后，各个部分面积之比是不变的（线性的本质）。而所有三角形都能被 $(0, 0)(1, 0)(0, 1)$ 三角形通过线性变换得到。

这样问题就轻松解决了。

#include <bits/stdc++.h>

double randf() { return (double)rand() / RAND_MAX; }

void randPoint(double x1, double y1,
               double x2, double y2,
               double x3, double y3,
               double &x, double &y) {
    double sx = randf();
    double sy = randf();
    if (sx > sy) {
        std::swap(sx, sy);
    }
    sy -= sx;
    x = x1 + (x2 - x1) * sx + (x3 - x1) * sy;
    y = y1 + (y2 - y1) * sx + (y3 - y1) * sy;
}

int main() {
    for (int i = 0; i < 20; i++) {
        double x, y;
        randPoint(0, 1, -1, -1, 1, -1, x, y);
        printf("%f %f\n", x, y);
    }
    return 0;
}

根据这个思路，三棱锥内一点也是没问题的。

4. 圆内一点

一个圆，圆心是原点，半径是 r，随机圆内的一点。

正经人是这么生成的：试错法，生成$[-r, r]$ 范围的两个浮点数，然后计算到原点的距离，不在圆内就重新生成。

这样当然很好，不过这里要讲一个非试错法的方法。

（性能不好，实用性小于装逼成分）

先确定辐角，然后确定到原点的距离。距离显然不在 $[0, r]$ 均匀，而是线性概率密度，因此和前面某题一样的做法就行了。

#include <bits/stdc++.h>

double randf() { return (double)rand() / RAND_MAX; }

void randPoint(double r, double &x, double &y) {
    static const double PI = acos(-1);
    double theta = randf() * PI * 2;
    double sr = std::max(randf(), randf()) * r;
    x = cos(theta) * sr;
    y = sin(theta) * sr;
}

int main() {
    for (int i = 0; i < 20; i++) {
        double x, y;
        randPoint(1, x, y);
        printf("%f %f\n", x, y);
    }
    return 0;
}

5. 球面一点以及球内一点

一个球，球心是原点，半径是 r，随机球面的一点 / 球内的一点。

球内一点和上一题一样，正经人都是试错法。而球面一点只要将球内一点的向量延长至长度为 r 即可。

那么非试错法该怎么做？

球面一点并不是一个复杂的问题。众所周知，球面的点在某个坐标上均匀的，因此 z 轴直接生成即可。另外两个轴按圆上一点来生成。

球内一点可以通过球面一点来求，即先确定半径，然后生成该半径为球的表面的一点。而半径的分布，很显然是二次方概率密度，只要生成 3 个随机数取最大值即可。

#include <bits/stdc++.h>

double randf() { return (double)rand() / RAND_MAX; }

void randPoint(double r, double &x, double &y, double &z) {
    static const double PI = acos(-1);
    // r = std::max({randf(), randf(), randf()}) * r; // 不加是球面一点，加了是球内一点
    z = randf() * r * 2 - r;
    double theta = randf() * PI * 2;
    double sr = sqrt(r * r - z * z);
    x = cos(theta) * sr;
    y = sin(theta) * sr;
}

int main() {
    for (int i = 0; i < 20; i++) {
        double x, y, z;
        randPoint(1, x, y, z);
        printf("%f %f %f\n", x, y, z);
    }
    return 0;
}