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

习题1.1.36

乱序检查。通过实验检查表1.1.10 中的乱序代码是否能够产生预期的效果。编写一个程序ShuffleTest，接受命令行参数 M 和 N，将大小为M 的数组打乱 N 次且在每次打乱之前都将数组重新初始化为a[i] = i。打印一个 M×M 的表格，对于所有的列 j，行 i 表示的是 i 在打乱后落到 j 的位置的次数。数组中的所有元素的值都应该接近于 N/M。

要点分析

表1.1.10是StdRandom库中的shuffle静态方法的实现（课本第19页），为了给没带书的同学提供方便，这里给出该方法。

public static void shuffle(double[] a)
{
    int N = a.length;
    for (int i = 0; i < N; i++)
    {  // 将 a[i]和in a[i..N-1] 中任意一个元素交换
        int r = i + StdRandom.uniform(N-i);
        double temp = a[i];
        a[i] = a[r];
        a[r] = temp;
    }
}

在本题中，直接调用STDRandom库中的该方法就可以，但是为了1.1.37题的解题方便，我们这里将该方法手动加入到我们创建的类中。

参考答案

import edu.princeton.cs.algs4.StdRandom;

public class Thirty_six {
    /**
     * @description: 将大小为N的数组，打乱N次
     * @param: a 要打乱的数组
     * @return: 已经打乱完成的数组
     */
    public static void shuffle(double[] a)
    {
        int N = a.length;
        for (int i = 0; i < N; i++)
        {  // 将 a[i]和in a[i..N-1] 中任意一个元素交换
            int r = i + StdRandom.uniform(N-i);
            double temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
    }

    /**
     * @description: 初始化数组
     * @param:  a：需要初始化的数组
     * @return:  Nothing
     */
//    public static double[] array_initialization(double[] a) {
    public static void array_initialization(double[] a) {  //修改版
        for (int i = 0; i < a.length ; i++) {
            a[i] = i;
        }
    }

    /**
     * @description: 将数组打乱N次
     * @param: N 打乱N次
     * @param: a 要打乱的数组
     * @return: 存储M * M这个表格的数组
     */
    public static double[][] upset(int N,double[] a) {
        double[][] count = new double[a.length][a.length]; //初始化用于存储M * M这个表格的数组
        for (int i = 0; i < N; i++) {
            array_initialization(a); //打乱前重新初始化
//            StdRandom.shuffle(a); //打乱数组
            shuffle(a); //打乱数组
            compute(a,count); //计算要打印的表格的值
        }
        return count;
    }

    /**
     * @description: 计算M * M 表格中，每个元素的值
     * @param: a 已经打乱的数组a
     * @param: count 存储M * M表格的数组
     * @return: Nothing
     */
//    public static double[][] compute(double[] a,double[][] count) {
      public static void compute(double[] a,double[][] count) { //修改版
        double[] b = new double[a.length];
        array_initialization(b); //初始化数组b，用来和已经打乱的数组a比较
        int c,d;
        for (int i = 0; i < a.length; i++) {
            c = (int)a[i];
            d = (int)b[i];
            count[c][d] += 1.0; //行i表示i在打乱后落到j的次数行i表示i在打乱后落到j的次数
        }
    }

    /**
     * @description: 打印一个M * M 的表格，
     * @param:  count:存储打印信息的数组
     * @return: Nothing
     */
    public static void print(double[][] count) {
        for (int i = 0; i < count.length; i++) {
            for (int j = 0; j < count.length; j++) {
                System.out.print(count[i][j] + "   ");
            }
            System.out.println();
        }

    }


    public static void main(String[] args) {
        int M = Integer.parseInt(args[0]);
        int N = Integer.parseInt(args[1]);
        double[] a = new double[M];
        print(upset(N,a));

    }
}
输出：
1.0   2.0   1.0   1.0   
1.0   2.0   0.0   2.0   
1.0   1.0   2.0   1.0   
2.0   0.0   2.0   1.0