算法 第四版 习题 答案(5)

}

dist2 =simulation(dist2,n,SIDES); int cnt=0;

for (int k = 2; k <= 2*SIDES; k++) {

if(Math.abs(dist[k]-dist2[k])>0.0001)

{ Ismatch=true; continue;} else {

cnt++;

} if(cnt==11) { }

StdOut.println(\+n +\+cnt); Print(dist2,SIDES); }

Ismatch=false;

}

public static void Print(double [] a,int SIDES) {

for (int k = 2; k <= 2*SIDES; k++) }

public static void main(String[] args) {

// TODO Auto-generated method stub int SIDES = 6; int N=1000000;

double[] dist = new double[2*SIDES+1]; double[] dist2 = new double[2*SIDES+1]; //准确概率分布

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

{

StdOut.print(\+k+\+a[k]+\); if((k-1)%6==0) }

StdOut.println(\);

StdOut.println(\);

}

}

for (int k = 2; k <= 2*SIDES; k++) { }

StdOut.println(\); Print(dist,SIDES);

match(dist,dist2,SIDES,N);

dist[k]/=36;

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

public class ShuffleTest { public ShuffleTest() { // TODO Auto-generated constructor stub } public static void main(String[] args) { // TODO Auto-generated method stub StdOut.print(\); int M=StdIn.readInt(); StdOut.print(\); int N=StdIn.readInt(); int[] a=new int[M]; int[][] c=new int[N][M]; int[][] b=new int[M][M]; int s=N; while(s>0) { for(int i=0;i

}

} StdOut.println(\); } StdOut.println(\); for(int k=0;k

public static void shuffle(int[] a) { int N = a.length;

for (int i = 0; i < N; i++) {

int r = i+StdRandom.uniform(N-i); // between i and N-1 int temp = a[i]; a[i] = a[r]; a[r] = temp; } }

1.1.37 糟糕的打乱。假设在我们的乱序代码中你选择的是一个0 到N-1 而非i 到N-1 之间的随机整数。证明得到的结果并非均匀地分布在N! 种可能性之间。用上一题中的测试检验这个版本。

public static void shuffleTerrible(int[] a) { int N = a.length; for (int i = 0; i < N; i++) { int r = StdRandom.uniform(N); // between i and N-1 int temp = a[i]; a[i] = a[r]; a[r] = temp; } }

1.1.38 二分查找与暴力查找。根据1.1.10.4 节给出的暴力查找法编写一个程序

BruteForceSearch，在你的计算机上比较它和BinarySearch 处理largeW.txt 和largeT.txt 所需的时间。

import java.util.Arrays;

public class BruteForceSearch {

public BruteForceSearch() { // TODO Auto-generated constructor stub } public static void main(String[] args) { In in = new In(\ int[] whitelist = in.readAllInts(); In in2 = new In(\ int[] key = in2.readAllInts(); // sort the array Arrays.sort(whitelist); // read integer key from standard input; print if not in whitelist for(int i=0;i

1.1.39 随机匹配。编写一个使用BinarySearch 的程序，它从命令行接受一个整型参数

T，并会分别针对N=10、10、10 和10 将以下实验运行T 遍：生成两个大小为N 的随机6 位正整数数组并找出同时存在于两个数组中的整数的数量。打印一个表格，对于每个N，给出T 次实验中该数量 的平均值。

import java.util.Arrays;

public class RandomMatching { public RandomMatching() { // TODO Auto-generated constructor stub } private static int M=1000000;//定义随机数范围6位 public static int[] RandomArray(int N) { int [] a=new int [N]; for(int i=0;i

for(int i=10;i<=1000000;i=i*10)

3456

{

StdOut.print(\+i+\); int[] a=new int[i]; int[] b=new int[i]; int cnt=0;

for(int j=0;j

StdOut.println(\+cnt/T); } } }