算法 第四版 习题 答案

算法第四版习题答案算法第四版习题答案算法第四版习题答案算法第四版习题答案编制仅供参考审核批准生效日期地址：电话：传真:邮编:给出以下表达式的值：a.(0+15)/2b.*c.true&&false||true&&true答案：,给出以下表达式的类型和值：a.(1+/2b.1+2+3+c.>=4d.1+2+"3"答案：b.编写一个程序，从命令行得到三个整数参数。如果它们都相等则打印equal，否则打印notequal。publicclassTestUqual{ publicstaticvoidmain(String[]args) { inta,b,c; a=b=c=0; ("Pleaseenterthreenumbers"); a=(); b=(); c=(); if(equals(a,b,c)==1) { ("equal"); } else { ("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=();y=();(compare(x)&&compare(y));}publicstaticbooleancompare(doublex){If(x>0&&x<1)returenture;elsereturnfalse;}}下面这段程序会打印出什么intf=0;intg=1;for(inti=0;i<=15;i++){(f);f=f+g;g=f-g;}答案：01123581321345589144233377610分别给出以下代码段打印出的值：a.doublet=;while(t-t)>.001)t=t+t)/;("%.5f\n",t);sum=0;for(inti=1;i<1000;i++)for(intj=0;j<i;j++)sum++;(sum);sum=0;for(inti=1;i<1000;i*=2)for(intj=0;j<1000;j++)sum++;(sum);答案：c.10000下列语句会打印出什么结果给出解释。a.'b');b.'b'+'c');c.('a'+4));答案：a.bb.197c.e编写一段代码，将一个正整数N用二进制表示并转换为一个String类型的值s。解答：Java有一个内置方法(N)专门完成这个任务，但该题的目的就是给出这个方法的其他实现方法。下面就是一个特别简洁的答案：Strings="";for(intn=N;n>0;n/=2)s=(n%2)+s;下面这段代码有什么问题int[]a;for(inti=0;i<10;i++)a[i]=i*i;解答：它没有用new为a[]分配内存。这段代码会产生一个variableamightnothavebeeninitialized的编译错误。编写一段代码，打印出一个二维布尔数组的内容。其中，使用*表示真，空格表示假。打印出行号和列号。publicclassTest{ publicTest(){ ength;j++) { (a[i][j]+""); } ();} } publicstaticint[][]MigrateArrays(int[][]a,int[][]b) { for(inti=0;i<;i++) { for(intj=0;j<a[0].length;j++) { b[j][i]=a[i][j]; } } returnb; } publicstaticint[][]RandomInitial(int[][]a,intN) { ("初始化二维数组:");for(inti=0;i<;i++) { for(intj=0;j<a[0].length;j++) { a[i][j]=(N); (a[i][j]+""); } (); }returna; }}编写一个静态方法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之间，返回数组中所有元素之和应该和相等。publicstaticint[]histogram(int[]a,intM) { int[]b=newint[M]; intn=0; intm=0; for(inti=0;i<M;i++) { for(intj=0;j<;j++) { if(i==a[j]) { n++; } b[i]=n; } n=0; } for(inti=0;i<M;i++) { m=m+b[i]; } returnb; }给出exR1(6)的返回值：publicstaticStringexR1(intn){if(n<=0)return"";returnexR1(n-3)+n+exR1(n-2)+n;}答案：3找出以下递归函数的问题：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;}请看以下递归函数：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在计算机上运行以下程序：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++)(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];(N+""+a[N]); }}编写一个递归的静态方法计算ln(N!)的值。publicstaticdoublefactorialln(longN){ if(N>1) return(N)+factorialln(N-1); else return0; }编写一段程序，从标准输入按行读取数据，其中每行都包含一个名字和两个整数。然后用printf()打印一张表格，每行的若干列数据包括名字、两个整数和第一个整数除以第二个整数的结果，精确到小数点后三位。可以用这种程序将棒球球手的击球命中率或者学生的考试分数制成表格。publicclassScoreTable{ publicstaticvoidmain(String[]args){ Strings="Let'sgoforlunch!"; Inin=newIn("Se"); String[]whitelist=();hi]mid=lo+(hi-lo)/2;if(key<a[mid])hi=mid-1;elseif(key>a[mid])lo=mid+1;else returnmid;}return-1;}if(c=='-'){while(lo<=hi){hi]mid=lo+(hi-lo)/2;if(key<a[mid])hi=mid-1;elseif(key>a[mid])lo=mid+1;else return-1;}return0;}else return-1;}给出使用欧几里德算法计算105和24的最大公约数的过程中得到的一系列p和q的值。扩展该算法中的代码得到一个程序Euclid，从命令行接受两个参数，计算它们的最大公约数并打印出每次调用递归方法时的两个参数。使用你的程序计算1111111和1234567的最大公约数。publicstaticintCommomDivisor(intx,inty) { if(x==1||y==1) {("x="+x+"y="+y); return1;} if(x<y) { inttemp=x; x=y; y=temp; } ("x="+x+"y="+y); if(x%y==0) { returny; } else { x=x%y; ("x="+x); returnCommomDivisor(x,y); } }使用数学归纳法证明欧几里德算法能够计算任意一对非负整数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;}二项分布。估计用以下代码计算binomial(100,50)将会产生的递归调用次数：publicstaticdoublebinomial(intN,intk,doublep){if(N==0&&k==0)return;andif(N<0||k<0)return;return-p)*binomial(N-1,k,p)+p*binomial(N-1,k-1);}将已经计算过的值保存在数组中并给出一个更好的实现。估计递归调用次数：100！publicstaticdoublebinomial(intN,intk,doublep) { cnt++; ("N="+N+"k="+k+"p="+p); if(N==0&&k==0) { ("N==0&&k==0"); return; }if(N<0||k<0){ ("N<0||k<0"); return0;} return-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-p）f(N-1,k)+p*f(N-1,K-1)f(N-1,K-1)f(N-1,k)f(N,K)删除重复元素。修改BinarySearch类中的测试用例来删去排序之后白名单中的所有重复元素。publicstaticintcountC(int[]a)i+j-1]就是数组中所有和key相等的元素。importclassBinarySearch2{ publicBinarySearch2(){ 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< { cnt++; i++; } returncnt; } publicstaticvoidmain(String[]args){ ength; (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之间）作为参数，在一个圆上画出大小为且间距相等的N个点，然后将每对点按照概率p用灰线连接。publicclassRandomAccess{ publicRandomAccess(){ ength;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)ength; intN=; intP=b[0].length; double[][]c=newdouble[M][P]; if(M!= {}ength; if(M!= {}ength) {}ength;j++) { (a[i][j]+""); } ();}(); } publicstaticvoidPrint(double[][]a) { for(inti=0;i<;i++) { for(intj=0;j<a[0].length;j++) { (a[i][j]+""); } ();} (); } publicstaticvoidPrint(double[]a,Stringname) { (name+":");for(inti=0;i<;i++) { (a[i]+""); if((i+1)%10==0) ();}(); } publicstaticvoidPrint(double[]a) { for(inti=0;i<;i++) { (a[i]+""); if((i+1)%10==0) ();} (); } publicstaticdouble[][]randominti(double[][]a) { intN=; intM=a[0].length; for(inti=0;i<N;i++) { for(intj=0;j<M;j++) { a[i][j]=(N+M); } } returna; } publicstaticdouble[]randominti(double[]a) { intN=; for(inti=0;i<N;i++) { a[i]=(N); } returna; } ength][];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个数按照随机顺序打印实验题模拟掷骰子。以下代码能够计算每种两个骰子之和的准确概率分布：intSIDES=6;double[]dist=newdouble[2*SIDES+1];for(inti=1;i<=SIDES;i++)for(intj=1;j<=SIDES;j++)dist[i+j]+=;for(intk=2;k<=2*SIDES;k++)dist[k]/=;dist[i]的值就是两个骰子之和为i的概率。用实验模拟N次掷骰子，并在计算两个1到6之间的随机整数之和时记录每个值的出现频率以验证它们的概率。N要多大才能够保证你的经验数据和准确数据的吻合程度达到小数点后三位答案：108测试用例：publicclassrolltheDice{ publicrolltheDice(){ //TODOAuto-generatedconstructorstub }publicstaticdouble[]simulation(double[]a,intN,intSIDES){ for(inti=0;i<N;i++) { intn=1+(SIDES); intm=1+(SIDES); a[n+m]=a[n+m]+; } for(intk=2;k<=2*SIDES;k++) { a[k]=a[k]/N; } returna;}publicstaticvoidmatch(double[]dist,double[]dist2,intSIDES,intN){ booleanIsmatch=true; for(intn=N;Ismatch;n=n+n/10) { dist2=simulation(dist2,n,SIDES); intcnt=0; for(intk=2;k<=2*SIDES;k++) { if(dist[k]-dist2[k])> {Ismatch=true;continue;} else{ cnt++; } if(cnt==11) { Ismatch=false; } } ("n="+n+"cnt="+cnt); Print(dist2,SIDES); } }publicstaticvoidPrint(double[]a,intSIDES){ for(intk=2;k<=2*SIDES;k++) { ("k="+k+""+a[k]+""); if((k-1)%6==0) (""); } ("");} publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstub intSIDES=6; intN=1000000; double[]dist=newdouble[2*SIDES+1]; double[]dist2=newdouble[2*SIDES+1]; //准确概率分布 for(inti=1;i<=SIDES;i++) for(intj=1;j<=SIDES;j++) dist[i+j]+=; for(intk=2;k<=2*SIDES;k++) { dist[k]/=36; } ("dist:"); Print(dist,SIDES); match(dist,dist2,SIDES,N); }}乱序检查。通过实验检查表中的乱序代码是否能够产生预期的效果。编写一个程序ShuffleTest，接受命令行参数M和N，将大小为M的数组打乱N次且在每次打乱之前都将数组重新初始化为a[i]=i。打印一个M×M的表格，对于所有的列j，行i表示的是i在打乱后落到j的位置的次数。数组中的所有元素的值都应该接近于N/M。publicclassShuffleTest{ publicShuffleTest(){ //TODOAuto-generatedconstructorstub } publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstub("M="); intM=(); ("N="); intN=(); int[]a=newint[M]; int[][]c=newint[N][M]; int[][]b=newint[M][M]; ints=N; while(s>0) { for(inti=0;i<M;i++) { a[i]=i; (a[i]+""); } shuffle(a); for(inti=0;i<M;i++) { c[N-s][i]=a[i]; } s--; (""); } ("c"); for(intj=0;j<N;j++) { for(inti=0;i<M;i++) { (c[j][i]+""); } (""); } ("daluanb[m][m]"); for(intk=0;k<M;k++) { for(inti=0;i<M;i++) { intnum=0; for(intj=0;j<N;j++) { if(c[j][i]==k) num++; } b[k][i]=num; //("i="+i+""); (b[k][i]+""); } ("k="+k); } }publicstaticvoidshuffle(int[]a){ intN=; for(inti=0;i<N;i++){ intr=i+(N-i);//betweeniandN-1 inttemp=a[i]; a[i]=a[r]; a[r]=temp; } } }糟糕的打乱。假设在我们的乱序代码中你选择的是一个0到N-1而非i到N-1之间的随机整数。证明得到的结果并非均匀地分布在N!种可能性之间。用上一题中的测试检验这个版本。publicstaticvoidshuffleTerrible(int[]a){ intN=; for(inti=0;i<N;i++){ intr=(N);//betweeniandN-1 inttemp=a[i]; a[i]=a[r]; a[r]=temp; } }二分查找与暴力查找。根据节给出的暴力查找法编写一个程序BruteForceSearch，在你的计算机上比较它和BinarySearch处理和所需的时间。importclassBruteForceSearch{ publicBruteForceSearch(){ //TODOAuto-generatedconstructorstub } publicstaticvoidmain(String[]args){ Inin=n