算法-第四版-习题-答案

1、算法-第四版-习题-答案1.1.1 给出以下表达式的值：a. ( 0 + 15 )/ 2b. 2.0e-6 * 100000000.1c. true & false | true & true答案：a.7,b.200.0000002 c.ture1.1.2 给出以下表达式的类型和值：a. (1 + 2.236)/2b. 1 + 2 + 3 + 4.0c. 4.1 = 4d. 1 + 2 + 3答案：a.1.618 b. 10.0 c.true d.331.1.3 编写一个程序，从命令行得到三个整数参数。如果它们都相等则打印equal ,否则打印 not equal 。 public class

2、 TestUqual public static void main(String口 args) int a,b,c; a=b=c=0; StdOut. println (Please enter three numbers);a =StdIn. readInt (); b=StdIn.readInt ();c=StdIn.readInt ();if (equals (a,b,c)=1) StdOut. print (equal); elseStdOut. print (not equal ); public static int equals( int a , int b , int c)i

3、f (a=b&b=c) return 1; else return 0; 1.1.4 下列语句各有什么问题(如果有的话)？a. if (a b) then c = 0;b. if a b c = 0; c. if (a b) c = 0;d. if (a b) c = 0 else b = 0;答案：a. if (a b) c = 0; b. if(a b ) c = 0; 1.1.5 编写一段程序，如果double类型的变量x和y都严格位于0和1之间则打印true)否 则打印false 。public class TestUqual public static void main(Strin

4、g口 args)double x;double y;x=StdIn.readDouble();y=StdIn.readDouble();StdOut. print ( compare(x)& compare(y) )； public static boolean compare(double x)If(x0&x1)returenture;elsereturnfalse;1.1.6 下面这段程序会打印出什么？int f = 0;int g = 1;for (int i = 0; i .001)t = (9.0/t + t) / 2.0;StdOut.printf(%.5fn, t);b. int

5、 sum = 0;for (int i = 1; i 1000; i+)for (int j = 0; j i; j+)sum+;StdOut.println(sum);c. int sum = 0;for (int i = 1; i 1000; i *= 2)for (int j = 0; j 0; n /= 2)s = (n % 2) + s;1.1.10 下面这段代码有什么问题？int口 a;for (int i = 0; i 10; i+) ai = i * i;解答：它没有用new为a口分配内存。这段代码会产生一个 variable a might not havebeen init

6、ialized的编译错误。1.1.11 编写一段代码，打印出一个二维布尔数组的内容。其中，使用*表示真，空格表示假打印出行号和列号。public class Test public Test() / TODOAuto-generated constructor stub public static void main(String口 args) / TODOAuto-generated method stub boolean a = new boolean 1010;a=RandomInitialTestPrint (a);/(a);/ 随机初始化打印数组 public static void

7、 TestPrint( boolean a) for (int i=0;ia. length ;i+)/ 打印行号 StdOut. print ( +i);StdOut. println (); for (int i=0;i10;i+) StdOut. print (i); for ( int j=0;j10;j+) if (aij) StdOut. print (* +); else StdOut. print ( +); StdOut. println (); public static boolean RandomInitial(boolean a)for (int i=0;ia. le

8、ngth ;i+)for (int j=0;ja. length ;j+)if (StdRandom. bernoulli (0.1)aij= trueelse aij= false ； return a;1.1.12 以下代码段会打印出什么结果？int口 a = new int10;for (int i = 0; i 10; i+)ai = 9 - i;for (int i = 0; i 10; i+)ai = aai;for (int i = 0; i 10; i+)System.out.println(i);答案：0 1 2 3 4 5 6 7 8 9如 System.out.print

9、ln(ai);0 1 2 3 4 4 3 2 1 01.1.13 编写一段代码，打印出一个 M行N列的二维数组的转置(交换行和列)。public class Migrate public Migrate。/ TODOAuto-generated constructor stub public static void main(String args) / TODOAuto-generated method stub int m=5;int n=5;a= b=int a=newint b=newRandomInitial MigrateArraysMigratePrint (b);int mn;

10、int nm;(a,n);/初始化二维数组(a,b);/转置二维数组public static voidMigratePrint(int 叩 a)StdOut. println for ( int i=0;ia.(输出转置二维数组：length ;i+)；f or (int j=0;ja0.length ；j+)StdOut. print (aij+)；StdOut. println public static ()；int MigrateArrays(int a,int 叩 b)for ( int i=0;ia.length ;i+)f or (int j=0;ja0. length ;j+

11、)/输出转置二维数组b皿i=aijreturn b; publicstatic int RandomInitial(int a,int N)StdOut. println (初始化二维数组：);for for (int i=0;ia. length ;i+)(int j=0;j=M) N=N/M; a+； return a; 1.1.15 编写一个静态方法histogram。，接受一个整型数组a口和一个整数M为参数并返回 一个大小为M勺数组，其中第i个元素的值为整数 i在参数数组中出现的次数。如果a口中的值均在 0到M-1之间，返回数组中所有元素之和应该和 a.length 相等。public

12、 static int histogram( int a, int M) int b= new int M;int n=0;int m=0;for (int i=0;iM;i+) for (int j=0;ja. length ;j+) if (i=aj) n+; bi=n; n=0; for (int i=0;iM;i+) m=m+bi; return b;1.1.16 给出exR1(6)的返回值： public static String exR1(int n) (if (n = 0) return ;return exR1(n-3) + n + exR1(n-2) + n;答案： 311

13、3611422461.1.17 找出以下递归函数的问题：public static String exR2(int n) String s = exR2(n-3) + n + exR2(n-2) + n;if (n = 0) return ;return s;答：这段代码中的基础情况永远不会被访问。调用 exR2(3)会产生调用 exR2(0)、exR2(-3)和 exR2(-6),循环往复直到发生StackOverflowError 。可以修改为： public static String exR2(int n) if (n = 0) return ;String s = exR2(n-3)

14、 + n + exR2(n-2) + n;return s;1.1.18 请看以下递归函数：public static int mystery(int a, int b)if (b = 0) return 0;if (b % 2 = 0) return mystery(a+a, b/2);return mystery(a+a, b/2) + a;mystery(2, 25)和 mystery(3, 11)的返回值是 多少？给定正整数a和b, mystery(a,b)计算的结果是什么？将代码中的+替换为*并将return 0 改为return 1 ,然后回答相同的问题。答案：50, 33. 2

15、25 3111.1.19 在计算机上运行以下程序：publicclass Fibonaccipublic static long F(int N)if (N = 0) return 0;if (N = 1) return 1;return F(N-1) + F(N-2);public static void main(String口 args)for (int N = 0; N 100; N+) StdOut.println(N + + F(N);F(N)计算机用这段程序在一个小时之内能够得到 结果的最大N值是多少？开发F(N)的一 个更好的实现，用数组保存已经计算过的值 public cla

16、ss Fibonacci(public static long F( int N)(if (N = 0) return 0;if (N = 1) return 1;return F(N-1) +F(N-2);public static void main(String口 args)(int a=new int 100;a=A(a);public static long A(int a)(a0=0;a1=1； for ( int N = 2; N 1)return Math.ln(N)+factorialln(N-1); elsereturn 0; 1.1.21 编写一段程序，从标准输入按行读取

17、数据，其中每行都包含一个名字和两个整数。然 后用printf() 打印一张表格，每行的若干列数 据包括名字、两个整数和第一个整数除以第二个 整数的结果，精确到小数点后三位。可以用这种 程序将棒球球手的击球命中率或者学生的考试 分数制成表格。public class ScoreTable public static void main(String口 args) String s = _ Lets go for lunch!;In in = new In( Se);String whitelist = in.readAllStrings();/将文件中的字符串读取到数组中for (int i=0

18、;iwhitelist.length ;i=i+3) StdOut. print (whitelisti+ +whitelisti+1+ +whitelisti+2+ );double m=Double. parseDouble (whitelisti+1);double n=Double. parseDouble (whitelisti+2); StdOut. printf (0.3% ,m/n);StdOut. println ();1.1.22 使用 节中的rank() 递归方 法重新实现BinarySearch并跟踪该方法的调用。每当该方法被调用时，打印出它的参数lo和

19、hi并按照递归的深度缩进。提示：为递归方法 添加一个参数来保存递归的深度。1.1.23 为BinarySearch的测试用例添加一个参数：+打印出标准输入中不在白名单上的 值；-,则打印出标准输入中在白名单上的值。public static int rank( int key, int 口 a, char c) int lo = 0;int hi = a. length - 1; if (c= +)while (lo = hi) / Key is in alo.hi or not presentint mid = lo + (hi - lo) / 2;if (key amid) lo = mi

20、d + 1;elsereturn mid;return -1;if (c=-)while (lo = hi) / Key is in alo.hi or not mid = lo + (hi - lo) / 2;if (key amid) lo = mid + 1;elsereturn -1;return 0;elsereturn -1;1.1.24 给出使用欧几里德算法计算105和24 的最大公约数的过程中得到的一系列p和q的值。扩展该算法中的代码得到一个程序Euclid ,从命令行接受两个参数，计算它们的最大公约数 并打印出每次调用递归方法时的两个参数。使用你的程序

21、计算1 111 111和1 234 567的最大公 约数。 public static int CommomDivisor( int x, int y) if (x=1|y=1) StdOut. println ( x= +x+y= +y); return 1; if (x b) t = a; a = b; b = t; if (a c) t = a; a = c; c = t; if (b c) t = b; b = c; c = t; 1.1.27 二项分布。估计用以下代码计算binomial(100, 50)将会产生的递归调用次数：public static double binomia

22、l(int N, int k, double p)if (N = 0 & k = 0) return 1.0; and if (N 0 | k 0) return 0.0;return (1.0 - p)*binomial(N-1, k, p) + p*binomial(N-1, k-1);将已经计算过的值保存在数组中并给出一个更好的实现。估计递归调用次数：100!public static double binomial( int N, int k, double p) cnt +;StdOut. println (N= +N+k= +k+ p= +p);if (N = 0 & k = 0)

23、 StdOut. println (N = 0 & k = 0);return 1.0;if (N 0 | k 0) StdOut. println (N 0 | k 0);return 0;return (1.0 - p)* binomial (N-1, k, p) + p* binomial (N-1, k-1,p); 值保存在数组中的实现方法：public static void binomialArrays( int N, int K, double p) double a= new double N+1K+1;a00=1;for (int j=1;jN+1;j+) aj0=aj-10

24、*(1-p);for ( int i=0;iN+1;i+)for (int j=1;j=i&jK+1;j+) aij= (1-p)*ai-1j+p*ai-1j-1; 瓶-1,k)+p* f(N-1,K K1)数组P(N,K)=(1-p)f(N-1,K-1) f(卜，-1,k)f(N,K)1.1.28 删除重复元素。修改BinarySearch类中的测试用例来删去排序之后白名单中的所有重复元素。public static int countC( int 口 a) / 排序后，统计重复数量 i nt cnt=0; for (int i=0;ia. length -1;i+) i f (ai= ai

25、+1) s+; return cnt; public static int 口 remove( int 口 a, int cnt ) i nt s=0; i nt 口 b= new int a. length -cnt; b0=a0； for (int i=0;ia. length -1;i+) i f (ai= ai+1) s+； else bi-s+1=ai+1; return b; 1.1.29 等值键。为BinarySearch类添加一个静态方法rank(),它接受一个键和一个整型有序 数组(可能存在重复键)作为参数并返回数组中 小于该键的元素数量，以及一个类似的方法 count()来

26、返回数组中等于该键的元素的数量。 注意：如果i和j分别是rank(key,a) 和 count(key,a)的返回值，那么ai.i+j-1 就是 数组中所有和key相等的元素。 import java.util.Arrays; public class BinarySearch2 public BinarySearch2() / TODOAuto-generated constructor stub/*返回小于key的元素数量public static int rank( int key, int 口 a) int lo = 0;int hi = a. length - 1;while (lo

27、 = hi) / Key is in alo.hi or not mid = lo + (hi - lo) / 2;if (key amid) lo = mid + 1;else while (amid=amid-1&mid0) mid-;return mid;return -1; public static int count ( int key, int 口 a)int cnt=0;int i= rank (key,a);while (ai=ai+1&ia. length ) cnt+; i+; return cnt;public static void main(

28、String口 args) / TODOAuto-generated method stub In in = new In( tinyW);int 口 whitelist = in.readA111nts();Arrays. sort (whitelist);int key=StdIn. readInt ();int cnt= rank (key,whitelist);StdOut. println (smaller than +key+ element have +cnt ); int cntequal= count (key,whitelist);StdOut. println (equa

29、l +key+ element have +cntequal );1.1.30 数组练习。编写一段程序，创建一个Nx N的布尔数组a口口 。其中当i和j互质时(没有相同因子)，aij 为true ,否则为false。public static boolean TestArrays( boolean a) / int N=a. length ;int M=a0. length ;StdOut. println (M+=M +N= +N); for (int i=0;iN;i+) for (int j=0;jM;j+) if (gcd (i,j)=1) aij= true ;else aij= f

30、alse ; return a; public static int gcd( int m, int n) if (m=0|n=0) return 1; if (m%n=0) return n; else return gcd (n,m%n);1.1.31 随机连接。编写一段程序，从命令行接受一个整数N和double值p (0至!J1之间)作为参数，在一个圆上画出大小为0.05且间距相等的N个点，然后将每对点按照概率p用灰线连接。public class RandomAccess public / publicRandomAccess() p, double叩a)StdDraw.StdDraw

31、.StdDraw.StdDraw.StdDraw.setXscale(0, x*2);setYscale(0, y*2);setPenRadius (0.005);setPenColor (StdDraw. RED; circle (50, 50, 50);for (inti=0;iN;i+)StdDraw.StdDraw.doubledoublesetPenRadius setPenC010r m=50-50*Math. n=50+50*Math.(0.05);(StdDraw. BLACK);cos (2*Math.PI *i/N);sin (2*Math.PI *i/N);/ publi

32、cStdDraw. point (m, n);ai0=m;ai1=n;StdDraw. setPenColor(StdDraw. RED);StdDraw.text(m,n,i+ m=+m+ n=+n);staticvoid Randomline( double x, double y, double a)StdDraw.StdDraw.StdDraw.StdDraw.setXscale (0, x*2);setYscale (0, y*2);setPenRadius (0.01);setPenColor (StdDraw. LIGHT_GRAY);int forN=a. length ;(i

33、nt i=0;iN;i+)for (int j=0;jN;j+)if (StdRandom. bernoulli (0.5)StdDraw. line (ai0, ai1, a皿0, a皿1); publicstatic void main(String args) double x=50;double y=50;double r=50;int N=10;double p=0.2;double a= new double N2;/画圆/描点drawcricle (x,y,r,N,p,a);/画线Randomline (x,y,a);1.1.32直方图。假设标准输入流中含有一系TODOAuto-

34、generated constructor stub static void drawcricle( double x, double y, double r, int N, double 列double值。编写一段程序，从命令行接受一个整数N和两个double值l和r。将(l, r)分为N段并使用StdDraw画出输入流中的值落入每段的数量的直方图。public class histogram /*将(l , r)分为N段* */public static double 口 segmentationint N, double l, double r, double 口 a)i f (N=0)

35、 return a;double s=(r-l)/N;a0=l;for (int i=1;ia. length ;i+)ai=ai-1+s;return a;public static void makehistogram( double 口 a, double 口 b, double l, double r)i nt c= new int a. length -1;f or (int i=0;ib. length ;i+)for (int j=0;j=aj&biaj+1)cj+;continue ;i nt N=c. length ;StdDraw. setXscale (0,(r-l)*1

36、.2 );StdDraw. setYscale (0, b. length /N*1.5);f or (int i=0;iN;i+)double x = l+(r-l)/N*i;double y = ci/2.0;double rw = (r-l)/(2*N);double rh = ci/2.0;StdDraw. filledRectangle (x, y, rw, rh);StdOut. print (ci+);public static void main(String口 args) / TODOAuto-generated method stubint N=10; / 段数double

37、 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;ib. length ;i+) bi=StdRandom. uniform (l, r); makehistogram (a,b,l,r);1.1.33 矩阵库。编写一个Matrix库并实现以下API:public class Matrixstatic double dot(double x, double y)向量点乘

38、static double mult(double a,double田b)矩阵和矩阵之积static double transpose(double口口 a)转置矩阵static double mult(double a, doublex)矩阵和向量之积static double mult(double y, doublea)向量和矩阵之积编写一个测试用例，从标准输入读取矩阵并测试所有方法。public class Matrix public Matrix() / TODOAuto-generated constructor stub public static double dot( dou

39、ble x, double y) / 向量点乘 double a=0;if (x. length !=y. length ) return a; /此处抛出异常for (int i=0;ix. length ;i+) a+=xi*yi;return a; public static double transpose( double a) / 转置矩阵 for ( int i=0;ia. length ;i+) f or (int j=i;ja0. length ;j+) double temp=aij;aij=a皿i; aji=temp; return a; /* 矩阵的乘积定义：一个 n行m

40、J的矩阵乘以一个 m亍p列的矩阵，得到的结果是一个 n行p 列的矩阵，其中的第i行第j列位置上的数等于前一个矩阵第i行上的m个数与后一个矩阵第j列上的m个数对应* 相乘后所有私乘积的和。* */static double mult( double a, double b) /矩阵和矩阵之积int M=a0.length ;int N=a. length ;int P=b0.length ;double c= new double MP;if (M!=b. length ) /此处抛出异常for (int i=0;iN;i+)for (int j=0;jP;j+)for (int m=0;mM;

41、m+) cij+=aim*bmj;return c;public static double 口 mult( double a, double 口 x) / 矩阵和向量之积int N=a. length ;double 口 c= new double N;int M=a0.length ;if (M!=x. length ) /此处抛出异常for (int i=0;iN;i+)for (int m=0;mM;m+) ci+=aim*xm;return c;public static double 口 mult( double 口 y, double a) / 向量和矩阵之积 int N=y.

42、length ;double 口 c= new double N;int M=y. length ;if (M!=a0.length ) /此处抛出异常for (int i=0;iN;i+)for (int m=0;mM;m+) ci+=aim*yi; return c;public static void Print( double a , String name)StdOut. println (name+ :);for ( int i=0;ia. length ;i+)f or (int j=0;ja0. length ;j+)StdOut. print (a皿+); StdOut. p

43、rintln (); StdOut. println (); public static void Print( double a ) for ( int i=0;ia. length ;i+) for (int j=0;ja0. length ;j+) StdOut. print(a皿+); StdOut. println (); StdOut. println ();public static void Print( double 口 a , String name) StdOut. println (name+ :); for ( int i=0;ia. length ;i+) StdO

44、ut.print (ai+);if (i+1)%10=0) StdOut.println (); StdOut. println (); public static void Print( double 口 a ) for ( int i=0;ia. length ;i+)StdOut.print (ai+);if (i+1)%10=0) StdOut.println (); StdOut. println (); public static double randominti( double a)int N=a. length ;int M=a0. length ; for (int i=0

45、;iN;i+) for (int j=0;jM;j+) aij=StdRandom. uniform (N+M); return a; public static double 口 randominti( double 口 a)int N=a. length ;for (int i=0;iN;i+) ai=StdRandom. uniform (N);return a;/测试用例public static void main(String口 args) / TODOAuto-generated method stubint N=5;int p=10;double a= new double N

46、N;double b = new double pN;double 口 c= new double N;double d =0;a=randominti(a);b=randominti(b);c=randominti(c);d=dot (c,c);Print (c, c);StdOut. print (dot(c,c):d=+d);Print (a, a);Print (b, b);double x= new double a0. length a. length ; x= transpose (a);Print (x, transpose(a)to x );x= mult (a,b);Print (x, mult(a,b) );double 口 y=c; y=mult (a,c);Print (y, mult(a,c);y=mult (c,a);Print (y, mult(c,a);1.1.34 过滤。以下哪些任务需要（在数组中,比如）保存标准输入中的所有值？哪些可以被实定大小的数组（和N无关）？在每个问题中，输入都来自于标准输入且含有N个0至M的实数打印出最大和最小的数打印出所有数的中位数打印出第k小的数，k小于100打印出所有数的平方和打印出N个数的平均值打印出大于平均值的数的百分比将N个数按照升序打印将N个数按照随机顺序打印实验题1.1.