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