《算法第四版》课后练习题1.1.35答案

习题：1.1.35

以下代码能够计算每种两个骰子之和的准确概率分布：

int SIDES = 6;
double[] dist = new double[2 * SIDES + 1];
for (int i = 1; i <= SIDES; i++)
    for (int j = 1; j <= SIDES; j++)
        dist[i + j] += 1.0;
 
for (int k = 2; k <= 2 * SIDES; k++)
    dist[k] /= 36.0;

dist[i] 的值就是两个骰子之和为i的概率。用实验模拟N次掷骰子，并在计算两个1到 6之间的随机整数之和时记录每个值的出现频率以验证它们的概率。N要多大才能够保证你的经验数据和准确数据的吻合程度达到小数点后三位？

要点分析

一. 

 首先我们看到该题要求小数点后三位，Java输出double类型的小数点后几位有很多种方法，这里给出我常用的一种：

public class Test {
    public static void main(String[] args) {
        double i = 1.123456789;
        System.out.println(String.format("%.3f",i));
    }
}

输出：
1.123

二. 

再来解释一下题目中的代码

int SIDES = 6;  //骰子每个面有1~6个点
double[] dist = new double[2 * SIDES+1];  //如果两次掷骰子点数都为6，相加为12，所以需要13个空间
for (int i = 1; i <= SIDES; i++)
    for (int j = 1; j <= SIDES; j++)
        dist[i+j] += 1.0;  //统计掷骰子两次点数之和为i+j的次数
 
for (int k = 2; k <= 2 * SIDES; k++) //掷骰子两次，点数相加的结果为2~12。
    dist[k] /= 36.0;//掷骰子两次之和为i的概率

让我们通过上面的代码输出准确概率分布：

public class Thirty_five {
    public static void main(String[] args) {
        int SIDES = 6;
        double[] dist = new double[2 * SIDES + 1];

        for (int i = 1; i <= SIDES; i++)
            for (int j = 1; j <= SIDES; j++)
                dist[i+j] += 1.0;

        for (int k = 2; k <= 2 * SIDES; k++) {
            dist[k] /= 36.0;
            System.out.println("掷骰子两次点数之和为 " + k + " 的概率为" + String.format("%.3f", dist[k]));
        }

    }
}

输出：
掷骰子两次点数之和为 2 的概率为0.028
掷骰子两次点数之和为 3 的概率为0.056
掷骰子两次点数之和为 4 的概率为0.083
掷骰子两次点数之和为 5 的概率为0.111
掷骰子两次点数之和为 6 的概率为0.139
掷骰子两次点数之和为 7 的概率为0.167
掷骰子两次点数之和为 8 的概率为0.139
掷骰子两次点数之和为 9 的概率为0.111
掷骰子两次点数之和为 10 的概率为0.083
掷骰子两次点数之和为 11 的概率为0.056
掷骰子两次点数之和为 12 的概率为0.028

接下来我们需要自己实现一个模拟掷N次骰子的程序，计算出经验数据的概率，然后和掷两次骰子骰子产生的准确数据的相比较就可以了。

三. 

因为需要我们自己编写模拟掷骰子的程序，每次掷骰子的点数是随机，所以肯定会用到Random类，这里给出Random类的基本用法：

Random类中的nextInt(int n) 方法用于获取一个伪随机的，在0(包括)和指定值(不包括)，从此随机数生成器的序列中取出均匀分布的int值[1] 。但是我们掷骰子，肯定不需要0这个数字，则可以用下面的方法输出1~6这几个随机数

import java.util.Random;

public class Test {
    public static void main(String[] args) {
        Random ran = new Random();
        int N = 6;
        for (int i = 0; i < 20; i++) {
            System.out.print(ran.nextInt(N) + 1+ " "); 
              // N = 6，则生成0~5这几个随机数字，加1则生成1~6这几个数字
              //规律：ran.nextInt(N) + M ，则生成的是，[M，M+N）这个区间内的随机数
        }
    }
}

输出：4 2 4 2 4 1 1 2 6 5 5 1 1 2 4 6 2 4 5 2 

且每一次输出的值不一样

当然除了用Random类，我们也可以用课本标准库中自带的StdRandom方法（课本第18页）。

参考答案

import java.util.Random;

public class Thirty_five {

    public static double[] accurate_data() {  //计算准确概率分布
        int SIDES = 6;
        double[] dist = new double[2 * SIDES + 1];

        for (int i = 1; i <= SIDES; i++)
            for (int j = 1; j <= SIDES; j++)
                dist[i+j] += 1.0;

        for (int k = 2; k <= 2 * SIDES; k++) {
            dist[k] /= 36.0;
        }
        return dist;
    }

    public static Boolean judege(double[] dist, double[] dist2,int N) {  // 判断精度是否符合要求

        for (int i = 2; i <= 12; i++) {
//            double c = ;
//            System.out.println(c);
            if (Math.abs((dist2[i] /= N)  - dist[i]) >= 0.001) {  // 不能写成dist2[i] /= N  - dist[i] ，必须加括号
                //非常重要！张大甲你以后看这里一定要注意这里一定不能写成dist2[i] /= 36*N,并回想自己当初为何做错！
                // 而且结果记得加绝对值
                return false;
            }
        }
        return true;
    }

    public static void dice(double[] dist) { //计算N次掷骰子的结果
        int SIDES = 6;

        Random ran = new Random();
        int N = 10000;
        boolean B = true;
        while (B) {
            double[] dist2 = new double[2 * SIDES + 1]; //一定记得放在while循环里面
            for (int i = 1; i <= N; i++) {
                dist2[(ran.nextInt(6) + 1) + (ran.nextInt(6) + 1)] += 1.0;
            }
            B = !(judege(dist, dist2, N));  //如果符合精度，则退出While循环。
            System.out.println("此时N = " + N);
            N++;

        }
    }

    public static void main(String[] args) {
        dice(accurate_data());
    }

}
测试三次结果可以看到在2万左右
第一次：
此时N = 26758

第二次：
此时N = 26431

第三次：
此时N = 24761

参考资料

[1] 易百教程：Java的Random类使用方法