算法第四版习题答案.docx
《算法第四版习题答案.docx》由会员分享，可在线阅读，更多相关《算法第四版习题答案.docx（39页珍藏版）》请在冰点文库上搜索。
算法第四版习题答案
1.1.1给出以下表达式的值：
a.（0+15）/2
b.2.0e-6*100000000.1
c.true&&false||true&&true
答案：
a.7,b.200.0000002c.ture
1.1.2给出以下表达式的类型和值：
a.（1+2.236）/2
b.1+2+3+4.0
c.4.1>=4
d.1+2+"3"
答案：
a.1.618b.10.0c.trued.33
1.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（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;}
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（x>0&&x<1）
returenture;
else
returnfalse;
}
}
1.1.6下面这段程序会打印出什么？
intf=0;
intg=1;
for（inti=0;i<=15;i++）
{
StdOut.println（f）;
f=f+g;
g=f-g;
}
答案：
01123581321345589144233377610
1.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;i<1000;i++）
for（intj=0;jsum++;
StdOut.println（sum）;
c.intsum=0;
for（inti=1;i<1000;i*=2）
for（intj=0;j<1000;j++）
sum++;
StdOut.println（sum）;
答案：
a.3.00009b.499500c.10000
1.1.8下列语句会打印出什么结果？
给出解释。
a.System.out.println（'b'）;
b.System.out.println（'b'+'c'）;
c.System.out.println（（char）（'a'+4））;
答案：
a.bb.197c.e
1.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[]分配内存。
这段代码会产生一个variableamightnothave
beeninitialized的编译错误。
1.1.11 编写一段代码，打印出一个二维布尔数组的内容。
其中，使用*表示真，空格表示假。
打印出行号和列号。
publicclassTest{
publicTest（）{
//TODOAuto-generatedconstructorstub
}
publicstaticvoidmain（String[]args）{
//TODOAuto-generatedmethodstub
boolean[][]a=newboolean[10][10];
a=RandomInitial（a）;//随机初始化
TestPrint（a）;//打印数组
}
publicstaticvoidTestPrint（boolean[][]a）
{
for（inti=0;iStdOut.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{
for（intj=0;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]）;
0123443210
1.1.13编写一段代码，打印出一个M行N列的二维数组的转置（交换行和列）。
publicclassMigrate{
publicMigrate（）{
//TODOAuto-generatedconstructorstub
}
publicstaticvoidmain（String[]args）{
//TODOAuto-generatedmethodstub
intm=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{
for（intj=0;j{
StdOut.print（a[i][j]+""）;
}
StdOut.println（）;
}
}
publicstaticint[][]MigrateArrays（int[][]a,int[][]b）
{
for（inti=0;i{
for（intj=0;j{
b[j][i]=a[i][j];
}
}
returnb;
}
publicstaticint[][]RandomInitial（int[][]a,intN）
{
StdOut.println（"初始化二维数组:
"）;
for（inti=0;i{
for（intj=0;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;i{
for（intj=0;j{
if（i==a[j]）
{
n++;
}
b[i]=n;
}
n=0;
}
for（inti=0;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;
}
答案：
311361142246
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.225311
1.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）;
else
return0;
}
1.1.21 编写一段程序，从标准输入按行读取数据，其中每行都包含一个名字和两个整数。
然后用printf（）打印一张表格，每行的若干列数据包括名字、两个整数和第一个整数除以第二个整数的结果，精确到小数点后三位。
可以用这种程序将棒球球手的击球命中率或者学生的考试分数制成表格。
publicclassScoreTable{
publicstaticvoidmain（String[]args）{
Strings="Let'sgoforlunch!
";
Inin=newIn（"Se"）;
String[]whitelist=in.readAllStrings（）;//将文件中的字符串读取到数组中
for（inti=0;i{
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（""）;
}
}
}
1.1.22 使用1.1.6.4节中的rank（）递归方法重新实现BinarySearch并跟踪该方法的调用。
每当该方法被调用时，打印出它的参数lo和hi并按照递归的深度缩进。
提示：
为递归方法添加一个参数来保存递归的深度。
1.1.23 为BinarySearch的测试用例添加一个参数：
+打印出标准输入中不在白名单上的值；-，则打印出标准输入中在白名单上的值。
publicstaticintrank（intkey,int[]a,charc）{
intlo=0;
inthi=a.length-1;
if（c=='+'）
{
while（lo<=hi）{
//Keyisina[lo..hi]ornotpresent.
intmid=lo+（hi-lo）/2;
if（keyelseif（key>a[mid]）lo=mid+1;
else
returnmid;
}
return-1;
}
if（c=='-'）
{
while（lo<=hi）{
//Keyisina[lo..hi]ornotpresent.
intmid=lo+（hi-lo）/2;
if（keyelseif（key>a[mid]）lo=mid+1;
else
return-1;
}
return0;
}
else
return-1;
}
1.1.24 给出使用欧几里德算法计算105和24的最大公约数的过程中得到的一系列p和q的值。
扩展该算法中的代码得到一个程序Euclid，从命令行接受两个参数，计算它们的最大公约数并打印出每次调用递归方法时的两个参数。
使用你的程序计算1111111和1234567的最大公约数。
publicstaticintCommomDivisor（intx,inty）
{
if（x==1||y==1）
{StdOut.println（"x="+x+"y="+y）;
return1;}
if（x{
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的最大公约数。
提高题
1.1.26 将三个数字排序。
假设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{
a[j][0]=a[j-1][0]*（1-p）;
}
for（inti=0;ifor（intj=1;
升级会员 