习题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
请登录之后再进行评论