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

} }

思路： N列K行的数组：P(N,K)=（1-p）f(N-1,k)+p* f(N-1,K-1)

f(N-1,K-1) f(N-1,k) f(N,K)

1.1.28 删除重复元素。修改BinarySearch 类中的测试用例来删去排序之后白名单中的所有重复元素。

public static int countC(int [] a)//排序后，统计重复数量 {

int cnt=0;

for(int i=0;i

return cnt; }

public static int[] remove(int [] a,int cnt ) {

int s=0;

int[] b=new int[a.length-cnt]; b[0]=a[0];

for(int i=0;i

else{ b[i-s+1]=a[i+1]; }

return b; }

1.1.29 等值键。为BinarySearch 类添加一个静态方法rank()，它接受一个键和一个整型有序数组（可能存在重复键）作为参数并返回数组中小于该键的元素数量，以及一个类似的方法count() 来返回数组中等于该键的元素的数量。注意：如果i 和j 分别是rank(key,a) 和count(key,a)的返回值，那么a[i..i+j-1] 就是数组中所有和key 相等的元素。

import java.util.Arrays; public class BinarySearch2 {

public BinarySearch2() { }

/*返回小于key的元素数量 * */

// TODO Auto-generated constructor stub

public static int rank(int key, int[] a)

{int lo = 0;

int hi = a.length - 1; while (lo <= hi) {

// Key is in a[lo..hi] or not present. int mid = lo + (hi - lo) / 2; if (key < a[mid]) hi = mid - 1; else if (key > a[mid]) lo = mid + 1; else { }

return-1; }

public static int count (int key, int[] a) { }

int cnt=0;

int i=rank(key,a);

while(a[i]==a[i+1]&&i

return cnt;

// TODO Auto-generated method stub In in = new In(\);

cnt++; i++;

while(a[mid]==a[mid-1]&&mid>0)

mid--;

return mid;

}

public static void main(String[] args) {

int[] whitelist = in.readAllInts(); Arrays.sort(whitelist); int key=StdIn.readInt(); int cnt=rank(key,whitelist);

StdOut.println(\+key+\+cnt ); int cntequal=count(key,whitelist);

StdOut.println(\+key+\+cntequal ); }

}

1.1.30 数组练习。编写一段程序，创建一个N×N 的布尔数组a[][]。其中当i 和j 互质时（没有相同因子），a[i][j] 为true，否则为false。

public static boolean[][] TestArrays( boolean [][] a)// { int N=a.length; int M=a[0].length; StdOut.println(M+\+\+N); for(int i=0;i

1.1.31 随机连接。编写一段程序，从命令行接受一个整数N 和double 值p（0 到1 之间）作为参数，在一个圆上画出大小为0.05 且间距相等的N 个点，然后将每对点按照概率p 用灰线连接。

public class RandomAccess { public RandomAccess() { // TODO Auto-generated constructor stub } public static void drawcricle(double x,double y,double r,int N,double p,double[][] a) { StdDraw.setXscale(0, x*2); StdDraw.setYscale(0, y*2); StdDraw.setPenRadius(0.005); StdDraw.setPenColor(StdDraw.RED); StdDraw.circle(50, 50, 50); for(int i=0;i

}

double n=50+50*Math.sin(2*Math.PI*i/N); StdDraw.point(m, n); a[i][0]=m; a[i][1]=n; StdDraw.setPenColor(StdDraw.RED); // StdDraw.text(m,n,i+\ } }

public static void Randomline(double x,double y,double[][] a) { StdDraw.setXscale(0, x*2); StdDraw.setYscale(0, y*2); StdDraw.setPenRadius(0.01); StdDraw.setPenColor(StdDraw.LIGHT_GRAY); int N=a.length; for(int i=0;i

public static void main(String[] args) { double x=50; double y=50; double r=50; int N=10; double p=0.2; double[][] a=new double[N][2]; //画圆/描点 drawcricle(x,y,r,N,p,a); //画线 Randomline(x,y,a); }

1.1.32 直方图。假设标准输入流中含有一系列double 值。编写一段程序，从命令行接受一个整数N 和两个double 值l 和r。将(l，r) 分为N 段并使用StdDraw 画出输入流中的值落入每段的数量的直方图。

public class histogram {

/*将(l，r) 分为N段 * */

public static double[] segmentation(int N,double l,double r,double[] a) {

if(N==0) return a; double s=(r-l)/N; a[0]=l;

for(int i=1;i

a[i]=a[i-1]+s;

return a; }

public static void makehistogram(double[] a,double[] b,double l,double r) {

int[] c=new int[a.length-1]; for(int i=0;i

for(int j=0;j

if(b[i]>=a[j]&&b[i]

c[j]++; continue;

int N=c.length;

StdDraw.setXscale(0,(r-l)*1.2 );

StdDraw.setYscale(0, b.length/N*1.5);

for(int i=0;i

public static void main(String[] args) {

// TODO Auto-generated method stub double x = l+(r-l)/N*i; double y = c[i]/2.0; double rw = (r-l)/(2*N); double rh = c[i]/2.0;

StdDraw.filledRectangle(x, y, rw, rh); StdOut.print(c[i]+\); }

int N=10;//段数 double l=2; double r=20;

double [] a=new double[N+1];//记录分段的节点

double [] b=new double[N*N*N];//随机产生一个数组，作为输入数字。 a=segmentation(N,l,r,a); for(int i=0;i