题目描述

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

题目解读

• 剑指Offer 294

代码 C++

• 思路一、递归实现

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

class Solution {
public:
    void getprobability(int n){
        vector<int> result(6*n - n +1, 0);
        
        for(int i=1; i <= 6; i++){
            probability(n, n, i, result);
        }
        
        int total = pow(6, n);
        for(int i=0; i < result.size(); i++){
            cout<<i+n<<" 概率为: "<<(double)result[i]/total<<endl;
        }
    }

    void probability(int n, int current, int sum, vector<int>& result){
        if(current == 1){
            result[sum - n]++;
        }
        else{
            for(int i=1; i <= 6; i++){
                probability(n, current-1, sum+i, result);
            }
        }
    }
};

int main(){
    Solution ss;
    
    int n = 6; // n 代表骰子个数
    ss.getprobability(n);
}

• 思路二、循环实现

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

class Solution {
public:
    void getprobability(int n){
        int number = 6;
        int temp[2][number*n + 1];
        int flag = 0;

        for(int i=0; i< number*n+1; i++){
            temp[0][i] = 0;
            temp[1][i] = 0;
        }

        for(int i=1; i <= number; i++){
            temp[flag][i] = 1;
        }

        for(int k=2; k <= n; k++){
            for(int i=0; i < k; i++){
                temp[1-flag][i] = 0;
            }

            for(int i=k; i <= number*k; i++){
                temp[1-flag][i] = 0;
                for(int j=1; j<=i && j<=number; j++){
                    temp[1-flag][i] += temp[flag][i-j]; 
                }
            }
            flag = 1 - flag;
        }

        int total = pow(6, n);
        for(int i=n; i <= n*number; i++){
            cout<<i<<" 概率为: "<<temp[flag][i]<<"/"<<total<<endl;
        }
    }
};

int main(){
    Solution ss;
    
    int n = 2; // n 代表骰子个数
    ss.getprobability(n);
}

总结展望