蒙特卡洛算法C++代码

以下是一个简单的蒙特卡洛算法的C++代码示例，用于计算圆周率的近似值：

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
    srand(time(0)); // 初始化随机数种子

    int n = 1000000; // 模拟次数
    int inside = 0; // 圆内点数

    for (int i = 0; i < n; i++)
    {
        double x = (double)rand() / RAND_MAX; // 生成[0,1]之间的随机数
        double y = (double)rand() / RAND_MAX;

        if (x * x + y * y <= 1) // 判断是否在圆内
        {
            inside++;
        }
    }

    double pi = (double)inside / n * 4; // 计算圆周率的近似值
    cout << "Pi is approximately " << pi << endl;

    return 0;
}

该代码通过生成随机的点，判断这些点是否在圆内，从而计算出圆周率的近似值。

相关问题

亚马逊棋蒙特卡洛代码c++

以下是一个基于蒙特卡洛树搜索算法的亚马逊棋 AI 代码，使用 C++ 实现：

#include <bits/stdc++.h>
using namespace std;
const int N = 10, M = 100000;
const int dir[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
struct Move {
    int x, y, nx, ny, cnt;
};
int n, m, t, a[N][N], f[N][N][N][N], vis[N][N], st[N][N];
int q[N * N][2], hh, tt, dx[M], dy[M], cnt[M];
int dist(int x, int y, int nx, int ny) {
    if (x == nx && y == ny) return 0;
    if (x == nx || y == ny || abs(x - nx) == abs(y - ny)) return max(abs(x - nx), abs(y - ny));
    return 2 * max(abs(x - nx), abs(y - ny));
}
int get(int x, int y) { return x * m + y; }
vector<Move> get_moves(int player) {
    vector<Move> res;
    memset(vis, 0, sizeof vis);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (a[i][j] == player) {
                for (int k = 0; k < 8; ++k) {
                    int nx = i + dir[k][0], ny = j + dir[k][1];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m || a[nx][ny]) continue;
                    memset(st, 0, sizeof st);
                    int hh = 0, tt = -1;
                    q[++tt][0] = i, q[tt][1] = j, st[i][j] = 1;
                    while (hh <= tt) {
                        int x = q[hh][0], y = q[hh++][1];
                        for (int l = 0; l < 8; ++l) {
                            int nx = x + dir[l][0], ny = y + dir[l][1];
                            if (nx < 0 || nx >= n || ny < 0 || ny >= m || st[nx][ny]) continue;
                            int d = dist(i, j, nx, ny);
                            if (d >= t) continue;
                            if (a[nx][ny] == 3 - player) {
                                tt = -1;
                                break;
                            }
                            q[++tt][0] = nx, q[tt][1] = ny, st[nx][ny] = 1;
                        }
                    }
                    if (tt == -1) continue;
                    for (int l = 0; l <= tt; ++l)
                        if (!vis[q[l][0]][q[l][1]]) {
                            vis[q[l][0]][q[l][1]] = 1;
                            res.push_back({i, j, q[l][0], q[l][1], tt + 1});
                        }
                }
            }
    return res;
}
int dfs(int player, int depth) {
    if (depth == 0) return 0;
    auto moves = get_moves(player);
    int res = -1;
    for (auto move : moves) {
        int x = move.x, y = move.y, nx = move.nx, ny = move.ny, cnt = move.cnt;
        a[nx][ny] = player, a[x][y] = 0;
        int t = dfs(3 - player, depth - 1);
        a[x][y] = player, a[nx][ny] = 0;
        if (t == -1) return -1;
        res = max(res, cnt - t);
    }
    return res;
}
void init() {
    memset(f, -1, sizeof f);
    queue<int> q;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (a[i][j] != 0) {
                f[i][j][i][j] = 0;
                q.push(get(i, j));
            }
    while (q.size()) {
        int t = q.front();
        q.pop();
        int x = t / m, y = t % m;
        for (int k = 0; k < 8; ++k) {
            int nx = x + dir[k][0], ny = y + dir[k][1];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (f[x][y][nx][ny] == -1) {
                f[x][y][nx][ny] = f[x][y][x][y] + 1;
                q.push(get(nx, ny));
            }
        }
    }
}
int eval() {
    vector<int> p1, p2;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (a[i][j] == 1)
                p1.push_back(i * m + j);
            else if (a[i][j] == 2)
                p2.push_back(i * m + j);
    int res = 0;
    for (int i = 0; i < p1.size(); ++i)
        for (int j = 0; j < p2.size(); ++j)
            res += f[p1[i] / m][p1[i] % m][p2[j] / m][p2[j] % m];
    return res;
}
int dfs2(int player, int depth, int lf, int rf) {
    if (depth == 0) return eval();
    auto moves = get_moves(player);
    if (moves.empty()) return lf - rf;
    int res = -1e9;
    vector<int> cnts;
    for (auto move : moves) {
        int x = move.x, y = move.y, nx = move.nx, ny = move.ny, cnt = move.cnt;
        a[nx][ny] = player, a[x][y] = 0;
        cnts.push_back(cnt);
        res = max(res, -dfs2(3 - player, depth - 1, -rf, -lf));
        a[x][y] = player, a[nx][ny] = 0;
        lf = max(lf, res - cnt);
        if (lf >= rf) break;
    }
    return res;
}
void MCTS(int player, int depth) {
    auto moves = get_moves(player);
    if (moves.empty()) return;
    int ucnt = moves.size();
    int sum = 0;
    for (int i = 0; i < ucnt; ++i) {
        int x = moves[i].x, y = moves[i].y, nx = moves[i].nx, ny = moves[i].ny, cnt = moves[i].cnt;
        a[nx][ny] = player, a[x][y] = 0;
        int t = dfs(3 - player, depth - 1);
        a[nx][ny] = 0, a[x][y] = player;
        if (t != -1) cnts[i] += cnt - t, sum += cnt - t;
    }
    double mx = -1e9;
    int idx = -1;
    for (int i = 0; i < ucnt; ++i) {
        double val = 1.0 * cnts[i] / sum + sqrt(log(cnt[i]) / cnts[i]);
        if (val > mx) mx = val, idx = i;
    }
    int x = moves[idx].x, y = moves[idx].y, nx = moves[idx].nx, ny = moves[idx].ny;
    a[nx][ny] = player, a[x][y] = 0;
}
int main() {
    cin >> n >> m >> t;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) cin >> a[i][j];
    init();
    int depth = 0;
    while (1) {
        auto moves = get_moves(1);
        if (moves.empty()) {
            puts("Black loses");
            break;
        }
        if (depth >= 3) {
            memset(cnt, 0, sizeof cnt);
            for (int i = 0; i < M; ++i) cnt[i] = 1;
            for (int i = 0; i < 100; ++i) {
                int t = dfs2(1, 3, -1e9, 1e9);
                if (t > 0) break;
                int idx = rand() % moves.size();
                int x = moves[idx].x, y = moves[idx].y, nx = moves[idx].nx, ny = moves[idx].ny;
                a[nx][ny] = 1, a[x][y] = 0;
            }
        } else {
            for (int i = 0; i < 10000; ++i) MCTS(1, 5);
            int mx = -1e9, idx = -1;
            for (int i = 0; i < moves.size(); ++i)
                if (cnts[i] > mx) mx = cnts[i], idx = i;
            int x = moves[idx].x, y = moves[idx].y, nx = moves[idx].nx, ny = moves[idx].ny;
            a[nx][ny] = 1, a[x][y] = 0;
        }
        ++depth;
        auto moves2 = get_moves(2);
        if (moves2.empty()) {
            puts("White loses");
            break;
        }
        int idx = rand() % moves2.size();
        int x = moves2[idx].x, y = moves2[idx].y, nx = moves2[idx].nx, ny = moves2[idx].ny;
        a[nx][ny] = 2, a[x][y] = 0;
    }
    return 0;
}

该代码实现了亚马逊棋的基本算法，包括：

- 蒙特卡洛树搜索算法；
- 最短路算法；
- 评估函数。

其中，`get_moves` 函数用于获取当前玩家所有合法的移动方式；`dfs` 函数用于在搜索树上搜索指定深度的节点，并返回该节点的得分（如果该节点无法到达终局状态，则返回 -1）；`init` 函数用于预处理出最短路；`eval` 函数用于评估当前局面的得分；`dfs2` 函数用于在搜索树上搜索指定深度的节点，并返回该节点的得分；`MCTS` 函数用于执行一次蒙特卡洛树搜索，并更新访问次数和得分。

蒙特卡洛算法应用于矩阵乘法，请给出c++代码，样本数设计为1000

蒙特卡洛算法是一种统计模拟方法，常用于计算难以直接求解的问题。它通过随机采样的方式逼近复杂函数的期望值。对于大规模矩阵乘法，虽然不是最高效的传统方法（如Kroncker积），但在某些特定场景下，比如需要估算大矩阵的乘积但无法直接处理时，可以采用此方法。

下面是一个简单的C++示例，演示了如何使用蒙特卡洛方法来估计两个矩阵相乘的结果。这个例子假设我们有两大型矩阵A和B，由于它们太大而不能直接相乘，我们采样1000次小规模的随机矩阵来近似原矩阵乘法的平均结果。请注意，这仅作为教学示例，实际应用中可能需要更复杂的并行化处理和错误控制。

#include <iostream>
#include <vector>
#include <random>

// 生成指定维度的小矩阵
std::vector<std::vector<double>> generateRandomMatrix(int rows, int cols) {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_real_distribution<> dis(0., 1.); // 随机数在[0, 1]之间

    std::vector<std::vector<double>> matrix(rows, std::vector<double>(cols));
    for (int i = 0; i < rows; ++i)
        for (int j = 0; j < cols; ++j)
            matrix[i][j] = dis(gen);

    return matrix;
}

// 使用单个小矩阵估计总乘积
double estimateProduct(std::vector<std::vector<double>> a, std::vector<std::vector<double>> b) {
    double result = 0;
    for (int i = 0; i < a.size(); ++i)
        for (int j = 0; j < b[0].size(); ++j)
            result += a[i][j] * b[i][j];
    return result;
}

// 主函数
int main() {
    const int largeRows = ...; // 大矩阵的行数
    const int largeCols = ...; // 大矩阵的列数
    const int sampleSize = 1000;

    std::vector<std::vector<double>> A(largeRows, generateRandomMatrix(largeRows, largeCols));
    std::vector<std::vector<double>> B(largeRows, generateRandomMatrix(largeCols, largeCols));

    double estimatedProduct = 0;
    for (int i = 0; i < sampleSize; ++i) {
        std::vector<std::vector<double>> smallA = A;
        std::vector<std::vector<double>> smallB = B;
        estimatedProduct += estimateProduct(smallA, smallB);
    }

    // 输出估计的矩阵乘积
    double approximation = estimatedProduct / sampleSize;
    std::cout << "Estimated product using " << sampleSize << " samples: " << approximation << "\n";

    return 0;
}

注意：上述代码只是一个基本示例，实际应用中需要对样本大小、误差分析以及性能优化等因素进行详细考虑。同时，如果你只是想计算实际的矩阵乘法，应该使用标准库中的`std::matrix`或者第三方库如Eigen等进行操作。