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;
}