【面试题043】n个骰子的点数

【面试题043】n个骰子的点数
题目:
    把n个骰子扔在地上,所有骰子朝上一面的点数之和为s,
输入n,打印出s的所有可能的值出现的概率。
 
n个骰子的总点数,最小为n,最大为6n,根据排列组合的知识,那个骰子,所有点数的排列数为6^n。
我们先统计每一个点数出现的次数,然后把每一个点数出现的次数除以6^n,就能求出每个点数出现的概率。
 
思路一:
    基于递归求骰子点数,时间效率不够高。
  • 先把骰子分成两堆,第一堆只有一个,第二堆有n-1个,
  • 单独的那一个可能出现1到6的点数,我们需要计算从1-6的每一种点数和剩下的n-1个骰子来计算点数和。
  • 还是把n-1个那部分分成两堆,上一轮的单独骰子点数和这一轮的单独骰子点数相加,然后再和剩下的n-2个骰子来计算点数和。

不难发现这是一种递归的思路。

    定义一个长度为6n-n+1的数组,和为s的点数出现的次数保存到数组的第s-n个元素里。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
#include <iostream>
#include <cstdio>

using namespace std;

int g_maxValue = 6;

void Probability(int original, int current, int sum, int *pProbabilities)
{
    if (current == 1)
    {
        pProbabilities[sum - original]++;
    }
    else
    {
        for (int i = 1; i <= g_maxValue; ++i)
        {
            Probability(original, current - 1, i + sum, pProbabilities);
        }
    }
}

void Probability(int number, int *pProbabilities)
{
    for (int i = 1; i <= g_maxValue; ++i)
    {
        Probability(number, number, i, pProbabilities);
    }
}

void PrintProbability(int number)
{
    if (number < 1)
    {
        return;
    }
    int maxSum = number * g_maxValue;
    int *pProbabilities = new int[maxSum - number + 1];
    for (int i = number; i <= maxSum; ++i)
    {
        pProbabilities[i - number] = 0;
    }

Probability(number, pProbabilities);

int total = pow( (double)g_maxValue, number);
    for (int i = number; i <= maxSum; ++i)
    {
        double ratio = (double)pProbabilities[i - number] / total;
        printf("%d: %e\n", i, ratio);
    }
    delete[] pProbabilities;
}

int main()
{
    PrintProbability(6);
    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之和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
#include <iostream>
#include <cstdio>

using namespace std;

int g_maxValue = 6;

void PrintProbability(int number)
{
    if (number < 1)
    {
        return ;
    }
    int *pProbabilities[2];
    pProbabilities[0] = new int[g_maxValue * number + 1];
    pProbabilities[1] = new int[g_maxValue * number + 1];
    for (int i = 0; i < g_maxValue; ++i)
    {
        pProbabilities[0][i] = 0;
        pProbabilities[1][i] = 0;
    }

int flag = 0;
    for (int i = 1; i <= g_maxValue; ++i)
    {
        pProbabilities[flag][i] = 1;
    }

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

for (int i = k; i <= g_maxValue * k; ++i)
        {
            pProbabilities[1 - flag][i] = 0;
            for (int j = 1; j <= i && j <= g_maxValue; ++j)
            {
                pProbabilities[1 - flag][i] += pProbabilities[flag][i - j];
            }
        }
        flag = 1 - flag;
    }
    double total = pow( (double)g_maxValue, number);
    for (int i = number; i <= g_maxValue * number; ++i)
    {
        double ratio = (double)pProbabilities[flag][i] / total;
        printf("%d: %e\n", i, ratio);
    }
    delete[] pProbabilities[0];
    delete[] pProbabilities[1];
}

int main()
{
    PrintProbability(6);
    return 0;
}

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
上一篇:win7 64位 python3.4&opencv3.0配置安装


下一篇:centos换源