【每日算法Day 98】慈善赌神godweiyang教你算骰子点数概率!

简介: 【每日算法Day 98】慈善赌神godweiyang教你算骰子点数概率!

题目链接

LeetCode 面试题60. n个骰子的点数[1]

题目描述

n 个骰子扔在地上,所有骰子朝上一面的点数之和为 s。输入 n,打印出 s 的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

说明:

  • 1 <= n <= 11

示例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]

题解

令  表示投掷  个骰子,点数为  的方法数。那么可以根据最后一个骰子的点数情况( 到 ),递归进行计算:

当然还得加一些约束,例如  个骰子的点数范围是  ,所以一定有  ,即 。所以综上  的范围是 ,最后的转移方程就是:

但是,考虑到在计算  个骰子时,如果  ,那么  ,也就是  是根本不会被计算的。所以初始化的时候如果都是  ,那么就不用管这个下界了,也就是转移方程为:

此外,因为每次计算只会用到  个骰子的方法数,所以第一个维度可以省去。但是注意计算的时候  就得逆序遍历了,这样才不会覆盖掉  个骰子的方案数,造成后面的计算错误。

最后答案就是  。

代码

动态规划+空间优化(c++)

class Solution {
public:
    vector<double> twoSum(int n) {
        vector<int> dp(6*n+1, 0);
        for (int i = 1; i <= 6; ++i) dp[i] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int s = 6*i; s >= i; --s) {
                dp[s] = 0;
                for (int j = 1; j <= min(6, s-i+1); ++j) {
                    dp[s] += dp[s-j];
                }
            }
        }
        double total = pow(6, n);
        vector<double> res;
        for (int s = n; s <= 6*n; ++s) {
            res.push_back(dp[s]/total);
        }
        return res;
    }
};
相关文章
|
机器学习/深度学习 算法 数据挖掘
【机器学习】算法术语、决策函数、概率模型、神经网络的详细讲解(图文解释)
【机器学习】算法术语、决策函数、概率模型、神经网络的详细讲解(图文解释)
712 1
|
2月前
|
算法 数据安全/隐私保护
基于PSO粒子群优化算法的256QAM星座图的最优概率整形matlab仿真,对比PSO优化前后整形星座图和误码率
本项目基于MATLAB 2022a仿真256QAM系统,采用概率星座整形(PCS)技术优化星座点分布,结合粒子群优化(PSO)算法搜索最优整形因子v,降低误码率,提升传输性能。核心程序包含完整优化流程。
78 0
|
4月前
|
算法 JavaScript 数据安全/隐私保护
基于遗传算法的256QAM星座图的最优概率整形matlab仿真,对比优化前后整形星座图和误码率
本内容展示了基于GA(遗传算法)优化的256QAM概率星座整形(PCS)技术的研究与实现。通过Matlab仿真,分析了优化前后星座图和误码率(BER)的变化。256QAM采用非均匀概率分布(Maxwell-Boltzman分布)降低外圈星座点出现频率,减小平均功率并增加最小欧氏距离,从而提升传输性能。GA算法以BER为适应度函数,搜索最优整形参数v,显著降低误码率。核心程序实现了GA优化过程,包括种群初始化、选择、交叉、变异等步骤,并绘制了优化曲线。此研究有助于提高频谱效率和传输灵活性,适用于不同信道环境。
78 10
|
4月前
|
算法 JavaScript 数据安全/隐私保护
基于遗传算法的64QAM星座图的最优概率整形matlab仿真,对比优化前后整形星座图和误码率
本内容主要探讨基于遗传算法(GA)优化的64QAM概率星座整形(PCS)技术。通过改变星座点出现的概率分布,使外圈点频率降低,从而减小平均功率、增加最小欧氏距离,提升传输性能。仿真使用Matlab2022a完成,展示了优化前后星座图与误码率对比,验证了整形增益及频谱效率提升效果。理论分析表明,Maxwell-Boltzman分布为最优概率分布,核心程序通过GA搜索最佳整形因子v,以蒙特卡罗方法估计误码率,最终实现低误码率优化目标。
83 1
|
机器学习/深度学习 数据采集 存储
一文读懂蒙特卡洛算法:从概率模拟到机器学习模型优化的全方位解析
蒙特卡洛方法起源于1945年科学家斯坦尼斯劳·乌拉姆对纸牌游戏中概率问题的思考,与约翰·冯·诺依曼共同奠定了该方法的理论基础。该方法通过模拟大量随机场景来近似复杂问题的解,因命名灵感源自蒙特卡洛赌场。如今,蒙特卡洛方法广泛应用于机器学习领域,尤其在超参数调优、贝叶斯滤波等方面表现出色。通过随机采样超参数空间,蒙特卡洛方法能够高效地找到优质组合,适用于处理高维度、非线性问题。本文通过实例展示了蒙特卡洛方法在估算圆周率π和优化机器学习模型中的应用,并对比了其与网格搜索方法的性能。
1053 1
|
算法 Java 索引
LeetCode初级算法题:寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149:直线上最多的点数 Java详解
LeetCode初级算法题:寻找数组的中心索引+x的平方根+三个数的最大乘积+Leetcode 149:直线上最多的点数 Java详解
93 0
|
算法 vr&ar 图形学
☆打卡算法☆LeetCode 149. 直线上最多的点数 算法解析
☆打卡算法☆LeetCode 149. 直线上最多的点数 算法解析
|
资源调度 算法 关系型数据库
概率图推断之变量消除算法
事实证明,推理是一项颇具挑战的任务。对于很多我们感兴趣的概率,要准确回答这些问题都是NP难题。至关重要的是,推理是否容易处理取决于描述概率的图的结构。尽管有些问题很难解决,我们仍然可以通过近似推理方法获得有用的答案。
357 0
概率图推断之变量消除算法
|
机器学习/深度学习 算法 机器人
PETS:伯克利大神Sergey Levine指导的概率集成轨迹采样算法
PETS:伯克利大神Sergey Levine指导的概率集成轨迹采样算法
333 0
|
7天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)

热门文章

最新文章