【剑指Offer】n个骰子的点数

Posted on | In ,

题目

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

基于递归求骰子点数，时间效率不够高

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
public void PrintProbability(int number) {
    if (number < 1)
        return;

    int[] prob = new int[6*number-number+1];

    for (int i = 1; i <= 6; i++)
        probability(prob, number, number, i);

    print(prob, number);
}

private void probability(int[] prob, int number, int current, int sum) {
    if (current == 1) {
        prob[sum-number]++;
        return;
    }

    for (int i = 1; i <= 6; i++)
        probability(prob, number, current - 1, sum + i);
}

private void print(int[] prob, int number) {
    double total = Math.pow(6, number);

    for (int i = 0; i < prob.length; i++)
        System.out.println(i+number + ": " + prob[i] / total);
}

基于循环求骰子点数，时间性能好

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
public void PrintProbability(int number) {
    if (number < 1)
        return;

    int[][] prob = new int[2][6*number+1];
    int flag = 0;

    for (int i = 1; i <= 6; i++)
        prob[flag][i] = 1;

    //f(i,n) = f(i-1,n-1) + f(i-1,n-2) + f(i-1,n-3) + f(i-1,n-4) + f(i-1,n-5) + f(i-1,n-6)

    for (int i = 2; i <= number; i++) {
        flag = 1 - flag;

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

    print(prob[flag], number);
}

private void print(int[] prob, int number) {
    double total = Math.pow(6, number);

    for (int i = number; i <= 6 * number; i++)
        System.out.println(i + ": " + prob[i] / total);
}