当前位置：首页 » Project Euler » 详细页

Dice Game 题号：205 难度： 15 中英对照

Peter has nine four-sided (pyramidal) dice, each with faces numbered 1, 2, 3, 4.
Colin has six six-sided (cubic) dice, each with faces numbered 1, 2, 3, 4, 5, 6.

Peter and Colin roll their dice and compare totals: the highest total wins. The result is a draw if the totals are equal.

What is the probability that Pyramidal Pete beats Cubic Colin? Give your answer rounded to seven decimal places in the form 0.abcdefg

Solution

由题意知,这是一道概率求解问题。 Peter 有九颗 four-sided 骰子，Colin有六颗 six-sided 骰子，他们二人骰子抛掷点数的和的最大值$Max$均为36，所以可按以下思路解答： - 分别为Peter 和Colin 构建长度为$Max$ 的数组 $peterCount$ 和 $colinCount$ ，用来保存他们二人抛掷骰子可能出现的点数和，其中数组 $peterCount$ 和 $colinCount$ 的$index$表示抛掷骰子的点数和，$peterCount[index]$ 和$colinCount[index]$ 的值表示能抛掷出该点数事件出现的次数； - 使用 $peterTotal$ 和 $colinTotal$ 分别表示两人抛掷骰子的全体事件； - 创建长度为Max 的数组 $peterProb$ 和 $colinProb$ ，分别保存两人出现点数和为$index$的概率，即 $$ peterProb[index] = peterCount[index]/peterTotal $$ 和 $$ colinProb[index] = colinCount[index]/colinTotal $$ - 要求peter 获胜的概率即是求Peter 抛掷骰子的点数和大于Colin抛掷的点数和，用 $X_p$ 表示Peter抛掷的点数和，用 $X_c$ 表示Colin抛掷的点数和，用 $P(X_p)$ 和$ P(X_c)$ 分别表示Peter 和Colin 抛掷对应点数和的概率，则Peter 获胜的概率为： $$ P_w = \sum P(X_p)*P(X_c < X_p) $$ - 最后使用Java 中![str2double](https://ooo.0o0.ooo/2017/05/07/590ed1071d54a.png) 将double数据保留题目要求的小数位数，再用 $Double.parseDouble(s)$ 将前面的 $String$ 类型数据转化为 $Double$ 类型，即完成了问题的求解。 *总结：解答本题的关键点是理解Peter 和Colin 抛掷骰子点数和的事件分析与获得该点数的概率的计算，其次就在于找到Peter 获胜时满足的概率条件，理清该思路再编程解答就很简单。*

Code 

public class p205 {

    public static void main(String[] args) {
        long start = System.nanoTime();
        double result = run();
        long end = System.nanoTime();
        System.out.println(result);
        System.out.println((end - start) / 1000000 + "ms");
    }


    private  static int MAX = 37; // 骰子最大掷出点数为36

    private static double run() {


        int[] peterCount = new int[MAX];
        int[] colinCount = new int[MAX];


        //get peter's possible totals for all possible rolls of the dice
        for (int d1 = 1; d1 <= 4; d1++)
            for (int d2 = 1; d2 <= 4; d2++)
                for (int d3 = 1; d3 <= 4; d3++)
                    for (int d4 = 1; d4 <= 4; d4++)
                        for (int d5 = 1; d5 <= 4; d5++)
                            for (int d6 = 1; d6 <= 4; d6++)
                                for (int d7 = 1; d7 <= 4; d7++)
                                    for (int d8 = 1; d8 <= 4; d8++)
                                        for (int d9 = 1; d9 <= 4; d9++) {
                                            peterCount[d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9]++;
                                        }

        //get colin's possible totals for all possible rolls of the dice
        for (int d1 = 1; d1 <= 6; d1++)
            for (int d2 = 1; d2 <= 6; d2++)
                for (int d3 = 1; d3 <= 6; d3++)
                    for (int d4 = 1; d4 <= 6; d4++)
                        for (int d5 = 1; d5 <= 6; d5++)
                            for (int d6 = 1; d6 <= 6; d6++) {
                                colinCount[d1 + d2 + d3 + d4 + d5 + d6]++;
                            }

        //how many possible throws are there?
        int peterTotal = power(4,9);
        int colinTotal = power(6,6);


        //what are the probabilities of throwing a certain total?
        double[] peterProb = new double[MAX];
        double[] colinProb = new double[MAX];

        for (int i = 0; i < MAX; i++) {
            peterProb[i] = (double) peterCount[i] / peterTotal;
            colinProb[i] = (double) colinCount[i] / colinTotal;
        }


        //the probability that peter wins is:
        // probability that colin throws a number * prob that peter throws a higher number
        double peterWins = 0;
        for (int n = 1; n < peterCount.length; n++) {
            peterWins += colinProb[n - 1] * arraySum(peterProb, n, peterCount.length);
        }

        // 保留小数位数
        peterWins = Double.parseDouble(String.format("%.7f", peterWins));
        return peterWins;
    }
    
    private static double arraySum(double[] a, int start, int end) {

        double sum = 0;

        for (int i = start; i < end; i++)
            sum += a[i];
        return sum;
    }

    private static int power(int x,int n){
        int prod = 1;
        for(int i = 0;i<n;i++){
            prod *= x;
        }
        return  prod;
    }


}

0.5731441
22ms