Shopee 算法一面手撕
投色子，n次，输出float数组，代表每种和的概率，C++
#include <iostream>
#include <vector>
#include <cmath> // 用于计算pow
#include <iomanip> // 用于格式化输出
using namespace std;
// 计算n次投骰子后，各点数和的概率，返回float数组
vector<float> calculateDiceProbability(int n) {
// 边界条件：n必须大于0
if (n <= 0) {
return {};
}
// 动态规划数组：dp[i][j] 表示i个骰子和为j的组合数
// 为了简化，用二维vector，i从1到n，j从1到6n
vector<vector<long long>> dp(n + 1, vector<long long>(6 * n + 1, 0));
// 初始化：1个骰子的情况
for (int j = 1; j <= 6; ++j) {
dp[1][j] = 1;
}
// 状态转移：计算i个骰子的情况（i从2到n）
for (int i = 2; i <= n; ++i) {
// i个骰子的和范围：[i, 6i]
for (int j = i; j <= 6 * i; ++j) {
// 第i个骰子的点数k：1~6，且j-k >= i-1（i-1个骰子的最小和）
for (int k = 1; k <= 6; ++k) {
if (j - k >= i - 1) { // 确保i-1个骰子的和合法
dp[i][j] += dp[i-1][j - k];
}
}
}
}
// 总组合数：6^n
long long total = pow(6, n);
// 点数和的范围是[n, 6n]，共5n+1个值
vector<float> probabilities;
for (int j = n; j <= 6 * n; ++j) {
// 组合数 / 总组合数 = 概率，转换为float
probabilities.push_back(static_cast<float>(dp[n][j]) / total);
}
return probabilities;
}
// 测试函数：输出n次投骰子的各和值及对应概率
void printProbability(int n) {
vector<float> probs = calculateDiceProbability(n);
if (probs.empty()) {
cout << "n必须大于0！" << endl;
return;
}
cout << "投掷" << n << "次骰子，各点数和的概率：" << endl;
int sum = n; // 初始和为n
for (float p : probs) {
cout << "和为" << sum << "：" << fixed << setprecision(6) << p << endl;
sum++;
}
}
int main() {
// 测试用例：投掷2次骰子
int n = 2;
printProbability(n);
// 你可以修改n的值测试，比如n=3
// int n = 3;
// printProbability(n);
return 0;
}