n个骰子点数和及各自出现的概率

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

这道算法题可采取动态规划法来求解。鉴于《剑指Offer》中对该题的解法晦涩难懂,尤其是代码,也没有指明其解题的思路本质上就是动态规划,所以提出自己的理解和答案。

动态规划法简介: 动态规划法求解的总体过程就是将问题分为多个不同的阶段的问题,根据最开始阶段已知的问题的解逐步推导出最终解。即动态规划算法通常基于一个递推公式及一个或多个初始状态。

过程细化为: 第一步,确定问题的解的表达式,称之为状态。 第二步,将最终问题的构造成上一阶段问题的解(可能被拆分为多个子问题的解),即根据当前阶段问题的解求出下一阶段问题的解方法,即递推公式,称之为状态转移方程。

已知初始状态的解,有了状态和状态转移方程,逐步递推,即可求出最终的解。

动态规划法求解过程可以使用递归来实现,也可以使用迭代来实现。递归的优势就是代码简洁明了,但是递归有时会对不同阶段的子问题重复求解,所以效率低于迭代。

解题思路: 第一步,确定问题解的表达式。可将f(n, s) 表示n个骰子点数的和为s的排列情况总数。 第二步,确定状态转移方程。n个骰子点数和为s的种类数只与n-1个骰子的和有关。因为一个骰子有六个点数,那么第n个骰子可能出现1到6的点数。所以第n个骰子点数为1的话,f(n,s)=f(n-1,s-1),当第n个骰子点数为2的话,f(n,s)=f(n-1,s-2),…,依次类推。在n-1个骰子的基础上,再增加一个骰子出现点数和为s的结果只有这6种情况!那么有:

f(n,s)=f(n-1,s-1)+f(n-1,s-2)+f(n-1,s-3)+f(n-1,s-4)+f(n-1,s-5)+f(n-1,s-6) ,0< n<=6n f(n,s)=0, s< n or s>6n

上面就是状态转移方程,已知初始阶段的解为: 当n=1时, f(1,1)=f(1,2)=f(1,3)=f(1,4)=f(1,5)=f(1,6)=1。

代码实现: 递归版本:

#include <stdio.h>
#include <string.h>

#include <iostream>
using namespace std;

/****************************
func:获取n个骰子指定点数和出现的次数
para:n:骰子个数;sum:指定的点数和
return:点数和为sum的排列数
****************************/
int getNSumCount(int n, int sum){
    if(n<1||sum<n||sum>6*n){
        return 0;
    }
    if(n==1){
        return  1;
    }
    int resCount=0;
    resCount=getNSumCount(n-1,sum-1)+getNSumCount(n-1,sum-2)+
             getNSumCount(n-1,sum-3)+getNSumCount(n-1,sum-4)+
             getNSumCount(n-1,sum-5)+getNSumCount(n-1,sum-6);
    return resCount;
}

//验证
int main(){
    int n=0;
    while(true){
        cout<<"input dice num:";
        cin>>n;
        for(int i=n;i<=6*n;++i)
            cout<<"f("<<n<<","<<i<<")="<<getNSumCount(n,i)<<endl;
    }
}

当输入骰子的个数为3时,实验结果如下:

下面给出非递归,即迭代版本: 迭代版本:

/****************************************
func:给定骰子数目n,求所有可能点数和的种类数
para:n:骰子个数;count:存放各种点数和的种类数,下标i表示点数和为(i+n)
return:出错返回-1,成功返回0
****************************************/
int getNSumCountNotRecusion(int n, int* count){
    if(n<1)
        return -1;
    //初始化最初状态
    count[0]=count[1]=count[2]=count[3]=count[4]=count[5]=1;
    if(n==1) return 0;

    for(int i=2;i<=n;++i){
        for(int sum=6*i;sum>=i;--sum){
            int tmp1=((sum-1-(i-1))>=0?count[sum-1-(i-1)]:0); //上一阶段点数和sum-1的排列总数
            int tmp2=(sum-2-(i-1)>=0?count[sum-2-(i-1)]:0);
            int tmp3=(sum-3-(i-1)>=0?count[sum-3-(i-1)]:0);
            int tmp4(sum-4-(i-1)>=0?count[sum-4-(i-1)]:0);
            int tmp5=(sum-5-(i-1)>=0?count[sum-5-(i-1)]:0);
            int tmp6=(sum-6-(i-1)>=0?count[sum-6-(i-1)]:0);
            count[sum-i]=tmp1+tmp2+tmp3+tmp4+tmp5+tmp6;
        }
    }
    return 0;
}

//验证
int main(){
    int n;
    while(true){
        cout<<"iteration input dice num:";
        cin>>n;
        int* count=new int[5*n+1];
        memset(count,0,(5*n+1)*sizeof(int));
        getNSumCountNotRecusion(n,count);
        int allCount=0;
        for(int i=0;i<5*n+1;++i){
            cout<<"f("<<n<<","<<i+n<<")="<<count[i]<<endl;
            allCount+=count[i];
        }
        delete[] count;
    }
}

当输入骰子个数为3时,所有可能的点数和的排列情况如下图:

小结 实验至此,给定n个骰子,求各个点数和出现的概率就不难求,只需要除以总的排列数6n6^n就可以了。参考如下代码:

    int total = pow((float)6, n);   
    for(int i = n; i <=6*n; ++i){   //n:骰子数目
        float ratio = (float)getNSumCount(n,i)/total;  
        printf("%d: %f/n", i, ratio);  
    }  

参考文献

[1]剑指Offer.何海涛.电子工业出版社. [2]求n个骰子各点数和出现的概率-动态规划. [3]解题笔记(18)__n个骰子的点数.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏生信宝典

R语言可视化学习笔记之ggridges包

作者:严涛 浙江大学作物遗传育种在读研究生(生物信息学方向)伪码农,R语言爱好者,爱开源。

1774
来自专栏企鹅号快讯

输验证码输到崩溃?教你15分钟黑掉全球最流行的验证码插件

大数据文摘作品 编译:Katrine Ren、朝夕、钱天培 验证码这种东西真的是反人类。虽然它在保证账号安全、反作弊以及反广告有着至关重要的作用,但对于普通用户...

2748
来自专栏算法修养

文本分类学习 (十)构造机器学习Libsvm 的C# wrapper(调用c/c++动态链接库)

前言: 对于SVM的了解,看前辈写的博客加上读论文对于SVM的皮毛知识总算有点了解,比如线性分类器,和求凸二次规划中用到的高等数学知识。然而SVM最核心的地方应...

982
来自专栏AI研习社

自动文本摘要

摘要的主要思想是找到包含整个集合的“信息”的数据子集。这种技术在今天的工业中被广泛使用。搜索引擎就是一个例子;其他的例子包括文档、图像集合和视频的汇总。文档摘要...

3801
来自专栏人工智能LeadAI

机器学习实战 | 第一章:sklearn常用工具介绍

写在前面: 花了大力气学了很多的理论,也用Python实现了其中大部分的算法.接下来开始就进入实战阶段了. 实战阶段有三个重点: 1.选择合适的机器学习框...

29510
来自专栏何俊林

OpenGL ES总结(一)OpenGL 初识

导读:OpenGL是在图形图像中,非常优秀的渲染库,文中Demo下载地址:https://github.com/hejunlin2013/OpenGL31,看下...

3548
来自专栏数据小魔方

sparklines迷你图系列4——Evolution(Area)

今天接着分享Evolution图表类型中的Area图表。 其实就是我们常见的区域图(或者叫面积图),它与折线图(昨天讲到的)都是用来呈现时间序列中的趋势走向和波...

2834
来自专栏Python攻城狮

Python数据科学(六)- 资料清理(Ⅰ)1.Pandas1.资料筛选2.侦测遗失值3.补齐遗失值

成功爬取到我们所需要的数据以后,接下来应该做的是对资料进行清理和转换, 很多人遇到这种情况最自然地反应就是“写个脚本”,当然这也算是一个很好的解决方法,但是,p...

1373
来自专栏人人都是极客

【免费教学】Tensorflow Lite极简入门

边缘计算时代离我们越来越近,当前嵌入式设备的智能框架还是 TensorFlow Lite比较成熟,这里我准备用一系列免费课程和大家一起讨论下 TensorFlo...

2492
来自专栏marsggbo

LaTeX IEEE模板

网上有很多LaTeX软件,在线编辑器推荐Overleaf。但是我个人还是更喜欢离线写东西,所以尝试过各种编辑器,例如VSCode等等,这些编辑器都需要自己搭环境...

3342

扫码关注云+社区

领取腾讯云代金券