标签搜索

目 录CONTENT

文章目录

n个骰子的点数.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 6 阅读 / 4,089 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

n个骰子的点数

@[toc]

一、题目描述

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

二、分析

  •  骰子一共有6个面,每个面都有一个点数,对应的是1-6的数字,所以 n个骰子的最小点数之和是n,最大点数之和是6n
  •  根据排列组合的知识,n个骰子所有点数的排列一共有6^n
  •  这道题求和为s的所有可能的值出现的概率,所以我们需要先统计每个点数出现的次数,然后把每个点数出现的次数再分别除以6^n次方,即可求每个点数出现的概率

方法一:基于递归,效率低

  •  现在我们考虑如何统计每一个点数出现的次数。
  •  想要求n个骰子的点数和,我们可以 把n个骰子分为两堆,一堆只有一个骰子,另一堆有n - 1个骰子
  •  只有一个骰子的那一堆可能出现点数为1~6的点数,我们就需要分别计算从1到6的每一种情况和另一堆剩下n - 1个骰子来计算点数和
  •  接下来还是 把n - 1个骰子分为两堆,一堆只有一个骰子,另一堆有n - 2个骰子
  •  我们把上一轮单独的骰子和这一轮单独的骰子的点数相加,然后再和剩下的n - 2个骰子来计算点数
  •  到这里,我们就发现这是一个递归的问题:由小问题逐渐求得大问题;那么base case 就是当骰子个数为1的时候
  •  那么我们可以定义一个长度为6n - n + 1(6n是所有骰子最大的和,- n是因为不可能出现比骰子个数n还小的总和,所以节省n个空间)的数组用来保存相应总和点数的出现的次数,和为s的点数出现的次数保存在数组的第s - n(从0号位置开始)个元素

代码一:

#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

//为了可拓展性,把骰子的最大面值定义一个变量
int g_maxValue = 6;

//original:代表骰子的总个数
//index:代表当前是那个骰子
//curSum:当前总和
//pProbability:保存结果每个总和s出现的次数
void Probability(int original,int index,int curSum,vector<int>&  pProbability)
{
	//等于0,就代表把n个骰子不断的分为【1,n - 1】、【1,n - 2】直到【2,1】,
	//即只剩下一个骰子,直接++即可,代表这是和为curSum - original一种
    if(index == 0)
    {
    	//curSum为总和
    	//original代表骰子的个数,即把和为curSum的出现次数+1
        pProbability[curSum - original] += 1;
        return;
    }
    
    //枚举一个骰子的面值情况,递归进行
    for(int i = 1;i <= g_maxValue;i++)
        Probability(original,index - 1,curSum + i,pProbability);
}

//n代表骰子的个数
void PrintProbability(int n)
{
    if(n < 1)
        return;
        
    //最大的和
    int maxSum = n * g_maxValue;
    
    //保存结果
    vector<int> pProbability(n * 6 - n + 1,0);
    
    int curSum = 0;
    Probability(n,n,curSum,pProbability);
 
 	//总的出现所有次数
    int total = pow((double)g_maxValue,n);
    
    for(int i = n;i <= maxSum;i++)
    {
        double ratio = (double)pProbability[i - n] / total;
        cout<<i<<":"<<pProbability[i - n]<<" "<<ratio<<" "<<endl;
    }
}
 
int main()
{
    int number;
    while(cin>>number)
    {
    	PrintProbability(number);
    }  
    return 0;
}

在这里插入图片描述

方法二:基于循环,性能好

  •  换一种思路,我们用两个数组来存储骰子点数的每一个总数出现的次数
  •  在本次循环中,第一个数组的第n个数字表示骰子和为n出现的次数
  •  在下一次循化中,我们在上一次循环的基础上加一个新的骰子,此时和为n的出现的次数就因该等于和为n - 1,n - 2,n - 3,n - 4,n - 5,n - 6的次数总和
  •  所以我们把另一个数组的第n个数字设为前一个数组的第n - 1,n - 2,n - 3,n - 4,n - 5,n - 6之和

代码二:

#include <iostream>
#include <math.h>
using namespace std;
 
int g_maxValue = 6;
void PrintProbability(int n)
{
    if(n < 1)
        return;
 
 	//定义两个数组
    int* pProbability[2];
    pProbability[0] = new int[g_maxValue * n + 1];
    pProbability[1] = new int[g_maxValue * n + 1];
 
 	//初始化
    for(int i = 0;i <= g_maxValue * n;i++)
    {
        pProbability[0][i]=0;
        pProbability[1][i]=0;
    }
 
 	//用来控制两个数组的交替使用
    int flag = 0;
	
	//第一个骰子只可能出现1,2,3,4,5,6的情况,所以在对应的位置值为1
    for(int i = 1;i <= g_maxValue;i++)
        pProbability[flag][i] = 1;
 
 	//从第二个骰子开始判断
    for(int k = 2;k <= n;k++)
    {
        for(int i = 0;i < k;i++)
            pProbability[1 - flag][i] = 0;
            
        for(int i = k;i <= g_maxValue * k;i++)
        {
            pProbability[1 - flag][i] = 0;
            for(int j = 1;j <= i && j <= g_maxValue;j++)
                pProbability[1 - flag][i] += pProbability[flag][i - j];
        }
        //交换两个数组
        flag=1 - flag;
    }
 
    int total = pow((double)g_maxValue,n);
    for(int i = 0;i <= g_maxValue * n;i++)
    {
        double ratio=(double)pProbability[flag][i] / total;
		cout<<i<<":"<<pProbability[flag][i]<<" "<<ratio<<" "<<endl;
    }

    delete[] pProbability[0];
    delete[] pProbability[1];
}
 
int main()
{
    int n;
    while(cin>>n)
    {
    	PrintProbability(n);
    }
    return 0;
}

方法三:动规

上面两种都是《剑指offer》里面的解法,都比较难懂,现在将一种动规的简单些

  •  首先该问题具备DP的两个特征:最优子结构性质和子问题的重叠性
  •  具体的表现在:(1)n个骰子的点数依赖于n-1个骰子的点数,相当于在n-1个骰子点数的基础上再进行投掷。(2)求父问题的同时,需要多次利用子问题。
  •  由此定义状态转移方程为dp(𝑛,𝑘)表示𝑛个骰子点数和为𝑘时出现的次数
    dp(𝑛,𝑘)=dp(𝑛−1,𝑘−1)+dp(𝑛−1,𝑘−2)+dp(𝑛−1,𝑘−3)+dp(𝑛−1,𝑘−4)+dp(𝑛−1,𝑘−5)+dp(𝑛−1,𝑘−6)
  •  base case:第一轮的dp(1),dp(2),dp(3),dp(4),dp(5),dp(6)均等于1.
    𝑓(1,1)=𝑓(1,2)=𝑓(1,3)=𝑓(1,4)=𝑓(1,5)=𝑓(1,6)=1

代码三:

#include<iostream>
#define MAX_NUM 100
using namespace std;
 
void FindSum(int n)
{
    if(n <= 0)
        return;
        
    int sum = 0;
    int arr[n + 1][6 * n + 1];
    memset(arr,0,sizeof(arr));
    
    for(int i = 1; i <= 6; i++)//初始状态:base case
        arr[1][i] = 1;
        
    for(int i = 2; i <= n; i++)//状态转移方程
    {
        for(int j = i; j <= 6 * i; j++)//注意j的范围受i影响
        {
            arr[i][j] += (arr[i - 1][j - 1] + arr[i - 1][j - 2] 
            + arr[i - 1][j - 3] + arr[i - 1][j - 4] + 
            + arr[i - 1][j - 5] +arr[i - 1][j - 6]);
                         
        }
    }
    
    //输出结果
    for(int i = n; i <= 6 * n; i++)
    {
        sum += arr[n][i];
    }

    for(int i = n; i <= 6 * n; i++)
    {
        cout<<i<<":"<<arr[n][i]<<" "<<(arr[n][i] * 1.0 / sum)<<endl;
    }
}

int main()
{
    int n;
    while(cin>>n)
    {
        FindSum(n);
    }
    return 0;
}
0

评论区