算法第四版习题答案解析

..1.1.1给出以下表达式的值：a.<0+15>/2b.2.0e-6*100000000.1c.true&&false||true&&true答案：a.7,b.200.0000002c.ture1.1.2给出以下表达式的类型和值：a.<1+2.236>/2b.1+2+3+4.0c.4.1>=4d.1+2+"3"答案：a.1.618b.10.0c.trued.33编写一个程序,从命令行得到三个整数参数。如果它们都相等则打印equal,否则打印notequal。publicclassTestUqual{publicstaticvoidmain<String[]args> {inta,b,c; a=b=c=0; StdOut.println<"Pleaseenterthreenumbers">;a=StdIn.readInt<>; b=StdIn.readInt<>; c=StdIn.readInt<>;if<equals<a,b,c>==1> { StdOut.print<"equal">; }else { StdOut.print<"notequal">; } }publicstaticintequals<inta,intb,intc> {if<a==b&&b==c> {return1; }else {return0; } }}下列语句各有什么问题〔如果有的话？a.if<a>b>thenc=0;b.ifa>b{c=0;}c.if<a>b>c=0;d.if<a>b>c=0elseb=0;答案：a.if<a>b>c=0;b.if<a>b>{c=0;}编写一段程序,如果double类型的变量x和y都严格位于0和1之间则打印true,否则打印false。publicclassTestUqual{publicstaticvoidmain<String[]args> {doublex;doubley;x=StdIn.readDouble<>;y=StdIn.readDouble<>;StdOut.print<compare<x>&&compare<y>>;}publicstaticbooleancompare<doublex>{If<x>0&&x<1>returenture;elsereturnfalse;}}1.1.6下面这段程序会打印出什么？intf=0;intg=1;for<inti=0;i<=15;i++>{StdOut.println<f>;f=f+g;g=f-g;}答案：011235813213455891442333776101.1.7分别给出以下代码段打印出的值：a.doublet=9.0;while<Math.abs<t-9.0/t>>.001>t=<9.0/t+t>/2.0;StdOut.printf<"%.5f\n",t>;sum=0;for<inti=1;i<1000;i++>for<intj=0;j<i;j++>sum++;StdOut.println<sum>;sum=0;for<inti=1;i<1000;i*=2>for<intj=0;j<1000;j++>sum++;StdOut.println<sum>;答案：a.3.00009b.499500c.100001.1.8下列语句会打印出什么结果？给出解释。a.System.out.println<'b'>;b.System.out.println<'b'+'c'>;c.System.out.println<<char><'a'+4>>;答案：a.bb.197c.e1.1.9编写一段代码,将一个正整数N用二进制表示并转换为一个String类型的值s。解答：Java有一个内置方法Integer.toBinaryString<N>专门完成这个任务,但该题的目的就是给出这个方法的其他实现方法。下面就是一个特别简洁的答案：Strings="";for<intn=N;n>0;n/=2>s=<n%2>+s;1.1.10下面这段代码有什么问题？int[]a;for<inti=0;i<10;i++>a[i]=i*i;解答：它没有用new为a[]分配内存。这段代码会产生一个variableamightnothavebeeninitialized的编译错误。编写一段代码,打印出一个二维布尔数组的内容。其中,使用*表示真,空格表示假。打印出行号和列号。publicclassTest{publicTest<>{//TODOAuto-generatedconstructorstub }publicstaticvoidmain<String[]args>{//TODOAuto-generatedmethodstubboolean[][]a=newboolean[10][10]; a=RandomInitial<a>;//随机初始化TestPrint<a>;//打印数组 }publicstaticvoidTestPrint<boolean[][]a> {for<inti=0;i<a.length;i++>//打印行号 StdOut.print<""+i>; StdOut.println<"">;for<inti=0;i<10;i++> { StdOut.print<i>;for<intj=0;j<10;j++> {if<a[i][j]> StdOut.print<"*"+"">;else StdOut.print<""+"">; } StdOut.println<"">; } }publicstaticboolean[][]RandomInitial<boolean[][]a> {for<inti=0;i<a.length;i++> {for<intj=0;j<a.length;j++> {if<StdRandom.bernoulli<0.1>> a[i][j]=true;else a[i][j]=false; } }returna; }}1.1.12以下代码段会打印出什么结果？int[]a=newint[10];for<inti=0;i<10;i++>a[i]=9-i;for<inti=0;i<10;i++>a[i]=a[a[i]];for<inti=0;i<10;i++>System.out.println<i>;答案：0123456789如System.out.println<a[i]>;01234432101.1.13编写一段代码,打印出一个M行N列的二维数组的转置〔交换行和列。publicclassMigrate{publicMigrate<>{//TODOAuto-generatedconstructorstub }publicstaticvoidmain<String[]args>{//TODOAuto-generatedmethodstubintm=5;intn=5;int[][]a=newint[m][n];int[][]b=newint[n][m];a=RandomInitial<a,n>;//初始化二维数组b=MigrateArrays<a,b>;//转置二维数组MigratePrint<b>;//输出转置二维数组 }publicstaticvoidMigratePrint<int[][]a> { StdOut.println<"输出转置二维数组:">;for<inti=0;i<a.length;i++> { for<intj=0;j<a[0].length;j++> { StdOut.print<a[i][j]+"">; } StdOut.println<>;} } publicstaticint[][]MigrateArrays<int[][]a,int[][]b> {for<inti=0;i<a.length;i++> {for<intj=0;j<a[0].length;j++> { b[j][i]=a[i][j]; } }returnb; }publicstaticint[][]RandomInitial<int[][]a,intN> { StdOut.println<"初始化二维数组:">;for<inti=0;i<a.length;i++> { for<intj=0;j<a[0].length;j++> { a[i][j]=StdRandom.uniform<N>; StdOut.print<a[i][j]+"">; } StdOut.println<>; }returna; }}1.1.14编写一个静态方法lg<>,接受一个整型参数N,返回不大于log2N的最大整数。不要使用Math库。publicstaticintlga<intN,intM> {inta=0;while<N>=M> { N=N/M; a++; }returna; }编写一个静态方法histogram<>,接受一个整型数组a[]和一个整数M为参数并返回一个大小为M的数组,其中第i个元素的值为整数i在参数数组中出现的次数。如果a[]中的值均在0到M-1之间,返回数组中所有元素之和应该和a.length相等。publicstaticint[]histogram<int[]a,intM> {int[]b=newint[M];intn=0;intm=0;for<inti=0;i<M;i++> {for<intj=0;j<a.length;j++> {if<i==a[j]> { n++; } b[i]=n; } n=0; }for<inti=0;i<M;i++> { m=m+b[i]; }returnb; }1.1.16给出exR1<6>的返回值：publicstaticStringexR1<intn>{if<n<=0>return"";returnexR1<n-3>+n+exR1<n-2>+n;}答案：1.1.17找出以下递归函数的问题：publicstaticStringexR2<intn>{Strings=exR2<n-3>+n+exR2<n-2>+n;if<n<=0>return"";returns;}答：这段代码中的基础情况永远不会被访问。调用exR2<3>会产生调用exR2<0>、exR2<-3>和exR2<-6>,循环往复直到发生StackOverflowError。可以修改为：publicstaticStringexR2<intn>{if<n<=0>return"";Strings=exR2<n-3>+n+exR2<n-2>+n;returns;}1.1.18请看以下递归函数：publicstaticintmystery<inta,intb>{if<b==0>return0;if<b%2==0>returnmystery<a+a,b/2>;returnmystery<a+a,b/2>+a;}mystery<2,25>和mystery<3,11>的返回值是多少？给定正整数a和b,mystery<a,b>计算的结果是什么？将代码中的+替换为*并将return0改为return1,然后回答相同的问题。答案：50,33.2253111.1.19在计算机上运行以下程序：publicclassFibonacci{publicstaticlongF<intN>{if<N==0>return0;if<N==1>return1;returnF<N-1>+F<N-2>;}publicstaticvoidmain<String[]args>{for<intN=0;N<100;N++>StdOut.println<N+""+F<N>>;}}计算机用这段程序在一个小时之内能够得到F<N>结果的最大N值是多少？开发F<N>的一个更好的实现,用数组保存已经计算过的值。publicclassFibonacci{publicstaticlongF<intN>{if<N==0>return0;if<N==1>return1;returnF<N-1>+F<N-2>;}publicstaticvoidmain<String[]args>{int[]a=newint[100];a=A<a>;}publicstaticlong[]A<int[]a>{ a[0]=0;a[1]=1;for<intN=2;N<100;N++> {a[N]=a[N-1]+a[N-2];StdOut.println<N+""+a[N]>; }}1.1.20编写一个递归的静态方法计算ln<N!>的值。publicstaticdoublefactorialln<longN>{if<N>1>returnMath.ln<N>+factorialln<N-1>;elsereturn0; }编写一段程序,从标准输入按行读取数据,其中每行都包含一个名字和两个整数。然后用printf<>打印一张表格,每行的若干列数据包括名字、两个整数和第一个整数除以第二个整数的结果,精确到小数点后三位。可以用这种程序将棒球球手的击球命中率或者学生的考试分数制成表格。publicclassScoreTable{publicstaticvoidmain<String[]args>{ Strings="Let'sgoforlunch!"; Inin=newIn<"Se">;String[]whitelist=in.readAllStrings<>;//将文件中的字符串读取到数组中for<inti=0;i<whitelist.length;i=i+3>{ StdOut.print<whitelist[i]+""+whitelist[i+1]+""+whitelist[i+2]+"">;doublem=Double.parseDouble<whitelist[i+1]>;doublen=Double.parseDouble<whitelist[i+2]>; StdOut.printf<"0.3%",m/n>; StdOut.println<"">;}}}使用节中的rank<>递归方法重新实现BinarySearch并跟踪该方法的调用。每当该方法被调用时,打印出它的参数lo和hi并按照递归的深度缩进。提示：为递归方法添加一个参数来保存递归的深度。为BinarySearch的测试用例添加一个参数：+打印出标准输入中不在白名单上的值；-,则打印出标准输入中在白名单上的值。publicstaticintrank<intkey,int[]a,charc>{intlo=0;inthi=a.length-1;if<c=='+'>{while<lo<=hi>{//Keyisina[lo..hi]mid=lo+<hi-lo>/2;if<key<a[mid]>hi=mid-1;elseif<key>a[mid]>lo=mid+1;elsereturnmid;}return-1;}if<c=='-'>{while<lo<=hi>{//Keyisina[lo..hi]mid=lo+<hi-lo>/2;if<key<a[mid]>hi=mid-1;elseif<key>a[mid]>lo=mid+1;elsereturn-1;}return0;}elsereturn-1;}给出使用欧几里德算法计算105和24的最大公约数的过程中得到的一系列p和q的值。扩展该算法中的代码得到一个程序Euclid,从命令行接受两个参数,计算它们的最大公约数并打印出每次调用递归方法时的两个参数。使用你的程序计算1111111和1234567的最大公约数。publicstaticintCommomDivisor<intx,inty> {if<x==1||y==1> {StdOut.println<"x="+x+"y="+y>;return1;}if<x<y> {inttemp=x; x=y; y=temp; } StdOut.println<"x="+x+"y="+y>;if<x%y==0> {returny; }else { x=x%y; StdOut.println<"x="+x>;returnCommomDivisor<x,y>; } }1.1.25使用数学归纳法证明欧几里德算法能够计算任意一对非负整数p和q的最大公约数。提高题将三个数字排序。假设a、b、c和t都是同一种原始数字类型的变量。证明以下代码能够将a、b、c按照升序排列：if<a>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>将会产生的递归调用次数：publicstaticdoublebinomial<intN,intk,doublep>{if<N==0&&k==0>return1.0;andif<N<0||k<0>return0.0;return<1.0-p>*binomial<N-1,k,p>+p*binomial<N-1,k-1>;}将已经计算过的值保存在数组中并给出一个更好的实现。估计递归调用次数：100！publicstaticdoublebinomial<intN,intk,doublep> {cnt++; StdOut.println<"N="+N+"k="+k+"p="+p>;if<N==0&&k==0> { StdOut.println<"N==0&&k==0">;return1.0; }if<N<0||k<0>{ StdOut.println<"N<0||k<0">;return0;}return<1.0-p>*binomial<N-1,k,p>+p*binomial<N-1,k-1,p>; }值保存在数组中的实现方法：publicstaticvoidbinomialArrays<intN,intK,doublep> {double[][]a=newdouble[N+1][K+1]; a[0][0]=1;for<intj=1;j<N+1;j++> { a[j][0]=a[j-1][0]*<1-p>; }for<inti=0;i<N+1;i++>for<intj=1;j<=i&&j<K+1;j++> { a[i][j]=<1-p>*a[i-1][j]+p*a[i-1][j-1]; } }思路：N列K行的数组：P<N,K>=〔1-pf<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类中的测试用例来删去排序之后白名单中的所有重复元素。publicstaticintcountC<int[]a>//排序后,统计重复数量{intcnt=0;for<inti=0;i<a.length-1;i++>if<a[i]==a[i+1]> { s++; }returncnt;}publicstaticint[]remove<int[]a,intcnt>{ints=0;int[]b=newint[a.length-cnt]; b[0]=a[0];for<inti=0;i<a.length-1;i++>if<a[i]==a[i+1]> { s++; }else{ b[i-s+1]=a[i+1]; }returnb;}等值键。为BinarySearch类添加一个静态方法rank<>,它接受一个键和一个整型有序数组〔可能存在重复键作为参数并返回数组中小于该键的元素数量,以及一个类似的方法count<>来返回数组中等于该键的元素的数量。注意：如果i和j分别是rank<key,a>和count<key,a>的返回值,那么a[i..i+j-1]就是数组中所有和key相等的元素。importjava.util.Arrays;publicclassBinarySearch2{publicBinarySearch2<>{//TODOAuto-generatedconstructorstub }/*返回小于key的元素数量 **/publicstaticintrank<intkey,int[]a>{intlo=0;inthi=a.length-1;while<lo<=hi>{//Keyisina[lo..hi]mid=lo+<hi-lo>/2;if<key<a[mid]>hi=mid-1;elseif<key>a[mid]>lo=mid+1;else{while<a[mid]==a[mid-1]&&mid>0> mid--; returnmid;} }return-1;}publicstaticintcount<intkey,int[]a> {intcnt=0;inti=rank<key,a>;while<a[i]==a[i+1]&&i<a.length> { cnt++; i++; }returncnt; } publicstaticvoidmain<String[]args>{//TODOAuto-generatedmethodstub Inin=newIn<"tinyW">; int[]whitelist=in.readAllInts<>; Arrays.sort<whitelist>;intkey=StdIn.readInt<>;intcnt=rank<key,whitelist>; StdOut.println<"smallerthan"+key+"elementhave"+cnt>;intcntequal=count<key,whitelist>; StdOut.println<"equal"+key+"elementhave"+cntequal>; }}数组练习。编写一段程序,创建一个N×N的布尔数组a[][]。其中当i和j互质时〔没有相同因子,a[i][j]为true,否则为false。publicstaticboolean[][]TestArrays<boolean[][]a>// {intN=a.length;intM=a[0].length; StdOut.println<M+"=M"+"N="+N>;for<inti=0;i<N;i++>for<intj=0;j<M;j++> {if<gcd<i,j>==1> a[i][j]=true;else a[i][j]=false; }returna; }publicstaticintgcd<intm,intn> {if<m==0||n==0> {return1; }if<m%n==0> {returnn; }else {returngcd<n,m%n>; } }随机连接。编写一段程序,从命令行接受一个整数N和double值p〔0到1之间作为参数,在一个圆上画出大小为0.05且间距相等的N个点,然后将每对点按照概率p用灰线连接。publicclassRandomAccess{publicRandomAccess<>{//TODOAuto-generatedconstructorstub }publicstaticvoiddrawcricle<doublex,doubley,doubler,intN,doublep,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<inti=0;i<N;i++> {StdDraw.setPenRadius<0.05>; StdDraw.setPenColor<StdDraw.BLACK>;doublem=50-50*Math.cos<2*Math.PI*i/N>;doublen=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+"m="+m+"n="+n>; } } publicstaticvoidRandomline<doublex,doubley,double[][]a> { StdDraw.setXscale<0,x*2>; StdDraw.setYscale<0,y*2>; StdDraw.setPenRadius<0.01>; StdDraw.setPenColor<StdDraw.LIGHT_GRAY>;intN=a.length;for<inti=0;i<N;i++>for<intj=0;j<N;j++> {if<StdRandom.bernoulli<0.5>> StdDraw.line<a[i][0],a[i][1],a[j][0],a[j][1]>; } }publicstaticvoidmain<String[]args>{doublex=50;doubley=50;doubler=50;intN=10;doublep=0.2;double[][]a=newdouble[N][2];//画圆/描点drawcricle<x,y,r,N,p,a>;//画线 Randomline<x,y,a>; }}直方图。假设标准输入流中含有一系列double值。编写一段程序,从命令行接受一个整数N和两个double值l和r。将<l,r>分为N段并使用StdDraw画出输入流中的值落入每段的数量的直方图。publicclasshistogram{ /*将<l,r>分为N段 **/publicstaticdouble[]segmentation<intN,doublel,doubler,double[]a>{ if<N==0>return a;doubles=<r-l>/N; a[0]=l;for<inti=1;i<a.length;i++> { a[i]=a[i-1]+s; }returna;}publicstaticvoidmakehistogram<double[]a,double[]b,doublel,doubler>{int[]c=newint[a.length-1];for<inti=0;i<b.length;i++>for<intj=0;j<a.length-1;j++> {if<b[i]>=a[j]&&b[i]<a[j+1]> { c[j]++;continue; } }intN=c.length; StdDraw.setXscale<0,<r-l>*1.2>; StdDraw.setYscale<0,b.length/N*1.5>;for<inti=0;i<N;i++> { doublex=l+<r-l>/N*i;doubley=c[i]/2.0;doublerw=<r-l>/<2*N>;doublerh=c[i]/2.0; StdDraw.filledRectangle<x,y,rw,rh>; StdOut.print<c[i]+"">; } }publicstaticvoidmain<String[]args>{//TODOAuto-generatedmethodstubintN=10;//段数doublel=2;doubler=20;double[]a=newdouble[N+1];//记录分段的节点double[]b=newdouble[N*N*N];//随机产生一个数组,作为输入数字。 a=segmentation<N,l,r,a>;for<inti=0;i<b.length;i++> { b[i]=StdRandom.uniform<l,r>; }makehistogram<a,b,l,r>; }}1.1.33矩阵库。编写一个Matrix库并实现以下API：publicclassMatrixstaticdoubledot<double[]x,double[]y>向量点乘staticdouble[][]mult<double[][]a,double[][]b>矩阵和矩阵之积staticdouble[][]transpose<double[][]a>转置矩阵staticdouble[]mult<double[][]a,double[]x>矩阵和向量之积staticdouble[]mult<double[]y,double[][]a>向量和矩阵之积编写一个测试用例,从标准输入读取矩阵并测试所有方法。publicclassMatrix{publicMatrix<>{//TODOAuto-generatedconstructorstub }publicstaticdoubledot<double[]x,double[]y>//向量点乘 {doublea=0;if<x.length!=y.length> {returna;}//此处抛出异常for<inti=0;i<x.length;i++> a+=x[i]*y[i];returna; }publicstaticdouble[][]transpose<double[][]a>//转置矩阵 {for<inti=0;i<a.length;i++> {for<intj=i;j<a[0].length;j++> {doubletemp=a[i][j]; a[i][j]=a[j][i]; a[j][i]=temp; } }returna; }/* *矩阵的乘积定义：一个n行m列的矩阵乘以一个m行p列的矩阵,得到的结果是一个n行p列的矩阵, *其中的第i行第j列位置上的数等于前一个矩阵第i行上的m个数与后一个矩阵第j列上的m个数对应 *相乘后所有m个乘积的和。 **/staticdouble[][]mult<double[][]a,double[][]b>//矩阵和矩阵之积 {intM=a[0].length;intN=a.length;intP=b[0].length;double[][]c=newdouble[M][P];if<M!=b.length> {}//此处抛出异常for<inti=0;i<N;i++>for<intj=0;j<P;j++> {for<intm=0;m<M;m++> c[i][j]+=a[i][m]*b[m][j]; }returnc; }publicstaticdouble[]mult<double[][]a,double[]x>//矩阵和向量之积 {intN=a.length;double[]c=newdouble[N];intM=a[0].length;if<M!=x.length> {}//此处抛出异常for<inti=0;i<N;i++> {for<intm=0;m<M;m++> c[i]+=a[i][m]*x[m]; }returnc; }publicstaticdouble[]mult<double[]y,double[][]a>//向量和矩阵之积 {intN=y.length;double[]c=newdouble[N];intM=y.length;if<M!=a[0].length> {}//此处抛出异常for<inti=0;i<N;i++> {for<intm=0;m<M;m++> c[i]+=a[i][m]*y[i]; }returnc; }publicstaticvoidPrint<double[][]a,Stringname> { StdOut.println<name+":">;for<inti=0;i<a.length;i++> {for<intj=0;j<a[0].length;j++> { StdOut.print<a[i][j]+"">; } StdOut.println<>;}StdOut.println<>; }publicstaticvoidPrint<double[][]a> {for<inti=0;i<a.length;i++> {for<intj=0;j<a[0].length;j++> { StdOut.print<a[i][j]+"">; } StdOut.println<>;} StdOut.println<>; }publicstaticvoidPrint<double[]a,Stringname> { StdOut.println<name+":">;for<inti=0;i<a.length;i++> { StdOut.print<a[i]+"">;if<<i+1>%10==0> StdOut.println<>;}StdOut.println<>; }publicstaticvoidPrint<double[]a> {for<inti=0;i<a.length;i++> { StdOut.print<a[i]+"">;if<<i+1>%10==0> StdOut.println<>;} StdOut.println<>; }publicstaticdouble[][]randominti<double[][]a> {intN=a.length;intM=a[0].length;for<inti=0;i<N;i++> {for<intj=0;j<M;j++> { a[i][j]=StdRandom.uniform<N+M>; } }returna; } publicstaticdouble[]randominti<double[]a> {intN=a.length;for<inti=0;i<N;i++> { a[i]=StdRandom.uniform<N>; }returna; } //测试用例publicstaticvoidmain<String[]args>{//TODOAuto-generatedmethodstubintN=5;intp=10;double[][]a=newdouble[N][N];double[][]b=newdouble[p][N];double[]c=newdouble[N];doubled=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=newdouble[a[0].length][a.length];x=transpose<a>;Print<x,"transpose<a>tox">;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>">; }}过滤。以下哪些任务需要〔在数组中,比如保存标准输入中的所有值？哪些可以被实现为一个过滤器且仅使用固定数量的变量和固定大小的数组〔和N无关？在每个问题中,输入都来自于标准输入且含有N个0到1的实数。‰打印出最大和最小的数‰打印出所有数的中位数‰打印出第k小的数,k小于100‰打印出所有数的平方和‰打印出N个数的平均值‰打印出大于平均值的数的百分比‰将N个数按照升序打印‰将N个数按照随机顺序打印实验题1.1.35模拟掷骰子。以下代码能够计算每种两个骰子之和的准确概率分布：intSIDES=6;double[]dist=newdouble[2*SIDES+1];for<inti=1;i<=SIDES;i++>for<intj=1;j<=SIDES;j++>dist[i+j]+=1.0;for<intk=2;k<=2*SIDES;k++>dist[k]/=36.0;dist[i]的值就是两个骰子之和为i的概率。用实验模拟N次掷骰子,并在计算两个1到6之间的随机整数之和时记录每个值的出现频率以验证它们的概率。N要多大才能够保证你的经验数据和准确数据的吻合程度达到小数点后三