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

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.331.1.3编写一个程序，从命令行得到三个整数参数。如果它们都相等则打印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;}}}1.1.4下列语句各有什么问题（如果有的话）？a.if(ab)thenc=0;b.ifab{c=0;}c.if(ab)c=0;d.if(ab)c=0elseb=0;答案：a.if(ab)c=0;b.if(ab){c=0;}1.1.5编写一段程序，如果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(x0&&x1)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);b.intsum=0;for(inti=1;i1000;i++)for(intj=0;ji;j++)sum++;StdOut.println(sum);c.intsum=0;for(inti=1;i1000;i*=2)for(intj=0;j1000;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;n0;n/=2)s=(n%2)+s;1.1.10下面这段代码有什么问题？int[]a;for(inti=0;i10;i++)a[i]=i*i;解答：它没有用new为a[]分配内存。这段代码会产生一个variableamightnothavebeeninitialized的编译错误。1.1.11编写一段代码，打印出一个二维布尔数组的内容。其中，使用*表示真，空格表示假。打印出行号和列号。publicclassTest{publicTest(){//TODOAuto-generatedconstructorstub}publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubboolean[][]a=newboolean[10][10];a=RandomInitial(a);//随机初始化TestPrint(a);//打印数组}publicstaticvoidTestPrint(boolean[][]a){for(inti=0;ia.length;i++)//打印行号StdOut.print(+i);StdOut.println();for(inti=0;i10;i++){StdOut.print(i);for(intj=0;j10;j++){if(a[i][j])StdOut.print(*+);elseStdOut.print(+);}StdOut.println();}}publicstaticboolean[][]RandomInitial(boolean[][]a){for(inti=0;ia.length;i++){for(intj=0;ja.length;j++){if(StdRandom.bernoulli(0.1))a[i][j]=true;elsea[i][j]=false;}}returna;}}1.1.12以下代码段会打印出什么结果？int[]a=newint[10];for(inti=0;i10;i++)a[i]=9-i;for(inti=0;i10;i++)a[i]=a[a[i]];for(inti=0;i10;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;ia.length;i++){for(intj=0;ja[0].length;j++){StdOut.print(a[i][j]+);}StdOut.println();}}publicstaticint[][]MigrateArrays(int[][]a,int[][]b){for(inti=0;ia.length;i++){for(intj=0;ja[0].length;j++){b[j][i]=a[i][j];}}returnb;}publicstaticint[][]RandomInitial(int[][]a,intN){StdOut.println(初始化二维数组:);for(inti=0;ia.length;i++){for(intj=0;ja[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;}1.1.15编写一个静态方法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;iM;i++){for(intj=0;ja.length;j++){if(i==a[j]){n++;}b[i]=n;}n=0;}for(inti=0;iM;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;}答案：3113611422461.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;N100;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]