剑指Offer60.n个骰子的点数 C++-Toy模板网

这篇具有很好参考价值的文章主要介绍了剑指Offer60.n个骰子的点数 C++。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、题目描述

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
示例 1:
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2:
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

2、VS2019上运行

使用Krahets—动态规划

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector<double> dp(6, 1.0 / 6.0); // 初始化一个大小为6的vector，初始值为骰子点数为1到6的概率

        for (int i = 2; i <= n; i++) {
            //6 * i - i + 1 = 5 * i + 1；  6 * i是最大点数和，i是最小点数和，相减+1是点数和的范围
            vector<double> tmp(5 * i + 1, 0); // 创建一个临时的vector，用于存储更新后的概率
            for (int j = 0; j < dp.size(); j++) {
                for (int k = 0; k < 6; k++) {//k是骰子的点数
                    tmp[j + k] += dp[j] / 6.0; // 更新临时vector中点数和为j+k的概率
                }
            }
            dp = tmp; // 将临时vector赋值给dp，更新当前骰子数量下的概率分布
        }
        return dp;
    }
};

int main() {
    Solution solution;
    int n;
    cout << "请输入骰子的数量：";
    cin >> n;

    vector<double> result = solution.dicesProbability(n);

    cout << "每个点数和的概率：" << endl;
    for (int i = 0; i < result.size(); i++) {
        cout << "点数和 " << i + n << "：" << result[i] << endl;
    }

    return 0;
}

请输入骰子的数量：2
每个点数和的概率：
点数和 2：0.0277778
点数和 3：0.0555556
点数和 4：0.0833333
点数和 5：0.111111
点数和 6：0.138889
点数和 7：0.166667
点数和 8：0.138889
点数和 9：0.111111
点数和 10：0.0833333
点数和 11：0.0555556
点数和 12：0.0277778

3、解题思路

Krahets文章来源地址https://www.toymoban.com/news/detail-670940.html

算法首先初始化一个长度为6的概率向量dp，初始时每个点数的概率均为1/6，这是因为在投掷一个骰子时，每个点数出现的概率都是相同的。
然后，从第2个骰子开始，进行n次循环。在每次循环中，创建一个长度为5*i+1的临时概率向量tmp，用于存储投掷当前骰子后的点数和概率分布。
通过两层嵌套循环，遍历当前的概率向量dp中的每个点数和概率值。对于每个点数和，内层循环遍历骰子的点数1到6，并将当前点数和的概率均匀分配到所有可能的下一个点数和上。
最后，将临时概率向量tmp赋值给dp，以便进行下一次循环。这样，当循环结束时，dp中的概率分布就表示了投掷n次骰子后各种点数和出现的概率。
最后，将dp作为结果返回。

到了这里，关于剑指Offer60.n个骰子的点数 C++的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！