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

}

}

{ }

makehistogram(a,b,l,r);

b[i]=StdRandom.uniform(l, r);

1.1.33 矩阵库。编写一个Matrix 库并实现以下API： public class Matrix

static double dot(double[] x, double[] y) 向量点乘

static double[][] mult(double[][] a, double[][] b) 矩阵和矩阵之积 static double[][] transpose(double[][] a) 转置矩阵

static double[] mult(double[][] a, double[] x) 矩阵和向量之积 static double[] mult(double[] y, double[][] a) 向量和矩阵之积 编写一个测试用例，从标准输入读取矩阵并测试所有方法。

public class Matrix { public Matrix() { // TODO Auto-generated constructor stub } public static double dot(double[] x, double[] y)//向量点乘 { double a=0; if(x.length!=y.length) { return a; }//此处抛出异常 for(int i=0;i * */ static double[][] mult(double[][] a, double[][] b)// 矩阵和矩阵之积 { int M=a[0].length; int N=a.length; int P=b[0].length; double[][] c=new double[M][P]; if(M!=b.length) {}//此处抛出异常 for(int i=0;i for(int j=0;j

StdOut.println(); }

StdOut.println(); } public static void Print(double [][] a ) { for (int i=0;i

for(int j=0;j

StdOut.println(); } StdOut.println(); } public static void Print(double [] a , String name) { StdOut.println(name+\); for (int i=0;i

StdOut.print(a[i]+\); if((i+1)==0) StdOut.println(); }

StdOut.println(); } public static void Print(double [] a ) { for (int i=0;i

StdOut.print(a[i]+\); if((i+1)==0) StdOut.println(); } StdOut.println(); } public static double[][] randominti(double[][] a) { int N=a.length; int M=a[0].length; for(int i=0;i

for(int i=0;i

StdOut.print(\+d);

Print(a,\); Print(b,\);

double[][] x=new double[a[0].length][a.length]; x= transpose(a);

Print(x,\);

x=mult(a,b);

Print(x,\);

double[] y=c; y=mult(a,c);

Print(y,\);

y=mult(c,a);

Print(y,\); } }

1.1.34 过滤。以下哪些任务需要（在数组中，比如）保存标准输入中的所有值？哪些可以被实现为一个过滤器且仅使用固定数量的变量和固定大小的数组（和N 无关）？在每个问题中，输入都来自于标准输入且含有N 个0 到1 的实数。 ?? 打印出最大和最小的数 ?? 打印出所有数的中位数 ?? 打印出第k 小的数，k 小于100 ?? 打印出所有数的平方和 ?? 打印出N 个数的平均值 ?? 打印出大于平均值的数的百分比 ?? 将N 个数按照升序打印 ?? 将N 个数按照随机顺序打印

实验题

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 要多大才能够保证你的经验数据和准确数据的吻合程度达到小数点后三位？ 答案：10

8

测试用例：

public class rolltheDice { {

for(int i=0;i

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

public static void match(double[] dist,double[] dist2,int SIDES,int N) {

boolean Ismatch=true;

for(int n=N;Ismatch;n=n+n/10) {

{

a[k]= a[k]/N; }

int n=1+StdRandom.uniform(SIDES); int m=1+StdRandom.uniform(SIDES); a[n+m]=a[n+m]+1.0;

public rolltheDice() { }

// TODO Auto-generated constructor stub

public static double[] simulation(double[] a,int N,int SIDES)

return a;