算法-第四版-習題-答案

算法第四版習題答案1.2/*

*1.2.1編寫一個Point2D的用例，從命令行接受一個整數(shù)N。在單位正方形內生成N個隨機點，然后計算兩點之間的最近距離

*/publicclasstestPoint2D{publictestPoint2D(){//TODOAuto-generatedconstructorstub}

publicstaticvoiddrawbox(doublebw,doublebh){StdDraw.setPenRadius(0.005);StdDraw.setPenColor(StdDraw.RED);Interval1Dxinterval=newInterval1D(0,bw);Interval1Dyinterval=newInterval1D(0,bh);Interval2Dbox=newInterval2D(xinterval,yinterval);box.draw();}publicstaticPoint2D[]drawpoint(intN){

Point2D[]p=newPoint2D[N];for(inti=0;i<N;i++){doublex=Math.random();doubley=Math.random();p[i]=newPoint2D(x,y);

p[i].draw();}returnp;}publicstaticdoublefindmindist(Point2D[]p){

Point2Dp1=p[0];Point2Dp2=p[1];doublemindist=p[0].distanceTo(p[1]);StdDraw.setPenRadius(0.002);StdDraw.setPenColor(StdDraw.RED);intn=p.length;for(inti=1;i<n-1;i++)for(intj=i+1;j<n;j++){doubletemp=p[i].distanceTo(p[j]);if(temp<mindist){mindist=temp;p1=p[i];p2=p[j];}}p1.drawTo(p2);StdOut.print("mindist="+mindist+p1.toString()+p2.toString());returnmindist;}publicstaticvoidmain(String[]args){intN=StdIn.readInt();//讀取畫點的數(shù)量//StdDraw.setXscale(0,1);//StdDraw.setYscale(0,1);drawbox(1,1);//畫出一個單位大小的正方形StdDraw.setPenRadius(0.01);StdDraw.setPenColor(StdDraw.BLACK);//drawpoint(N);//畫出N個點doublemin=findmindist(drawpoint(N));}}/*

*編寫一個Interval1D的用例，從命令行接受一個整數(shù)N。從標準輸入中讀取N個間隔（每個間隔由一對double值定義）并打印出所有相交的間隔對

*/publicclasstestInterval1D{publictestInterval1D(){//TODOAuto-generatedconstructorstub}publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubintN=StdIn.readInt();Interval1D[]interval=newInterval1D[N];intT=N;while(N>0){doublelo=N;doublehi=N+N;interval[T-N]=newInterval1D(lo,hi);StdOut.println(interval[T-N].toString());N--;}StdOut.println("OUT:");for(inti=0;i<T-1;i++)for(intj=i+1;j<T;j++){if(interval[i].intersects(interval[j])==true){StdOut.println(interval[i].toString()+interval[j].toString());}else{StdOut.println(interval[i].toString()+interval[j].toString()+"none");}}}}/**

*1.2.3

*//**

*@authorAdministrator

*

*/publicclassTestInterval2D{publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubStdOut.println("enterN:");intN=10;StdOut.println("enterminandmax:");doublemin=0.1;doublemax=0.9;StdDraw.setXscale(0,1);StdDraw.setYscale(0,1);StdDraw.setPenRadius(0.001);StdDraw.setPenColor(StdDraw.RED);Interval2D[]box=newInterval2D[N];Interval1D[]xinterval=newInterval1D[N];Interval1D[]yinterval=newInterval1D[N];doubleaverage=(max-min);Point2D[][]p=newPoint2D[N][2];/**Point2D[][]p使用數(shù)組保存點二位平面的對角頂點，用來計算是否包含。Interval2D[]box*建立數(shù)組對象，保存每個平面的信息。*/for(inti=0;i<N;i++){doublex=Math.random();doubley=Math.random();doublex1=x+average*Math.random();doubley1=y+average*Math.random();if(x1>1){x1=1;}if(y1>1){y1=1;}p[i][0]=newPoint2D(x,y);p[i][1]=newPoint2D(x1,y1);xinterval[i]=newInterval1D(x,x1);yinterval[i]=newInterval1D(y,y1);box[i]=newInterval2D(xinterval[i],yinterval[i]);box[i].draw();}/**檢測時候相交*/for(inti=0;i<N-1;i++)for(intj=i+1;j<N;j++){if(box[i].intersects(box[j])){StdDraw.setPenColor(StdDraw.BLACK);box[i].draw();box[j].draw();//StdOut.println(box[i].toString()+box[j].toString());}}/**是否包含*/for(inti=0;i<N-1;i++)for(intj=i+1;j<N;j++){if(box[i].contains(p[j][0])&&box[i].contains(p[j][1])){StdDraw.setPenRadius(0.005);StdDraw.setPenColor(StdDraw.BLUE);box[i].draw();StdDraw.setPenColor(StdDraw.GREEN);box[j].draw();StdOut.println("i="+i+"j="+j+"

"+box[i].toString()+box[j].toString());}}}}/*

*1.2.6

回環(huán)變位檢測

*1.2.7

遞歸返回值

*/publicclassCircularRotation{publicCircularRotation(){//TODOAuto-generatedconstructorstub}

publicstaticStringmystery(Strings)

{

intN=s.length();

if(N<=1)returns;

Stringa=s.substring(0,N/2);

Stringb=s.substring(N/2,N);

StdOut.println(a+b);

returnmystery(b)+mystery(a);

}publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubStrings1="ACTGACG";Strings2="TGACGAC";Stringss;ss=s1.concat(s1);//intp=ss.indexOf(s2);if(s1.length()==s2.length()&&ss.indexOf(s2)>0){StdOut.println("Yes!");}else{StdOut.println("NO!");StdOut.println(ss.indexOf(s2,ss.indexOf(s2))+"

"+ss.indexOf(s2));}

//測試mystery(s)ss="0123456789";Stringa=mystery(ss);StdOut.println("a="+a);}}/*************************************************************************

*

1.2.9

*

*

*

Compilation:

javacBinarySearch.java

*

Execution:

javaBinarySearchwhitelist.txt<input.txt

*

Datafiles:

/11model/tinyW.txt

*

/11model/tinyT.txt

*

/11model/largeW.txt

*

/11model/largeT.txt

*

*

%javaBinarySearchtinyW.txt<tinyT.txt

*

50

*

99

*

13

*

*

%javaBinarySearchlargeW.txt<largeT.txt|more

*

499569

*

984875

*

295754

*

207807

*

140925

*

161828

*

[367,966totalvalues]

*

*************************************************************************/importjava.util.Arrays;/**

*The<tt>BinarySearch</tt>classprovidesastaticmethodforbinarysearching

*foranintegerinasortedarrayofintegers.

*<p>

*The<em>rank</em>operationstakeslogarithmictimeintheworstcase.

*<p>

*Foradditionaldocumentation,see<a

*href="/11model">Section1.1</a>of

*<i>Algorithms,4thEdition</i>byRobertSedgewickandKevinWayne.

*

*@authorRobertSedgewick

*@authorKevinWayne

*/publicclassBinarySearch3{/***Thisclassshouldnotbeinstantiated.*//***Searchesfortheintegerkeyinthesortedarraya[].*

*@paramkey*

thesearchkey*@parama*

thearrayofintegers,mustbesortedinascendingorder*@returnindexofkeyinarraya[]ifpresent;-1ifnotpresent*/publicstaticintrank(intkey,int[]a,Countercounter){intlo=0;inthi=a.length-1;while(lo<=hi){//Keyisina[lo..hi]ornotmid=lo+(hi-lo)/2;if(key<a[mid]){hi=mid-1;counter.increment();StdOut.println("<c="+counter.tally());}elseif(key>a[mid]){lo=mid+1;counter.increment();StdOut.println(">c="+counter.tally());}else{StdOut.println("c="+counter.tally());returnmid;}}return-1;}/***Readsinasequenceofintegersfromthewhitelistfile,specifiedasa*command-lineargument.Readsinintegersfromstandardinputandprints*tostandardoutputthoseintegersthatdo*not*appearinthefile.*/publicstaticvoidmain(String[]args){//readtheintegersfromafileInin=newIn("LargeW");int[]whitelist=in.readAllInts();Countercounter=newCounter("counter");//sortthearrayArrays.sort(whitelist);StdOut.println(whitelist.length);//readintegerkeyfromstandardinput;printifnotinwhitelistwhile(!StdIn.isEmpty()){intkey=StdIn.readInt();if(rank(key,whitelist,counter)==-1)StdOut.println(key);}}}/*

*1.2.10編寫一個VisualCounter類，支持加一和減一操作。它的構造函數(shù)接受兩個參數(shù)N和max，

*其中N指定了操作的最大次數(shù)，max指定了計數(shù)器的最大絕對值。作為副作用，用圖像顯示每次計數(shù)器變化后的值。

*/publicclassVisualCounter{privateintcount;privateintmaxOperation;privateintval;//RecordvalueoftheCounterprivateintmaxVal;privateintx=0;publicVisualCounter(intN,intmax){maxOperation=N;maxVal=max;StdDraw.setXscale(0,N);StdDraw.setYscale(-max,max);StdDraw.setPenRadius(0.005);//TODOAuto-generatedconstructorstub}//currentvalue/***Initializesanewcounterstartingat0,withthegivenid.*

*@paramid*

thenameofthecounter*//***Incrementsthecounterby1.*/publicvoidincrement(){if(count<maxOperation&&val<maxVal){count++;val++;x++;StdDraw.setPenColor(StdDraw.BLACK);StdDraw.point(x,val);}}/***decrementthecounterby1.*/publicvoiddecrement(){if(count<maxOperation&&val>-maxVal){count++;val--;x++;StdDraw.setPenColor(StdDraw.RED);StdDraw.point(x,val);}}/***Returnsthecurrentcount.*/publicinttally(){returncount;}/***Returnsastringrepresentationofthiscounter*/publicStringtoString(){returncount+"";}publicstaticvoidmain(String[]args){VisualCounterVC=newVisualCounter(2000,1000);for(inti=0;i<2000;i++){if(i/1000==1)VC.decrement();elseVC.increment();}StdOut.println(VC.tally());}}/**1.2.11根據(jù)Date的API實現(xiàn)SmartDate類型在日期非法時拋出一個異常*1.2.12為SmartDate添加一個方法dayofWeek()，為日期返回一個星期。*1.2.19字符串解析。*/publicclassSmartDateimplementsDatable{ privatefinalintmonth; privatefinalintday; privatefinalintyear; publicintmonth(){ returnmonth; } publicintday(){ returnday; } publicintyear(){ returnyear; } /* *原理：蔡勒公式:W={[C/4]-2C+y+[y/4]+[26(m+1)/10]+d-1}%7（其中[]為取整符號） *其中,W是所求日期的星期數(shù).如果求得的數(shù)大于7,可以減去7的倍數(shù),直到余數(shù)小于7為止.c是公元年份 *的前兩位數(shù)字,y是已知公元年份的后兩位數(shù)字;m是月數(shù),d是日數(shù).方括[]表示只截取該數(shù)的整數(shù)部分。 */ publicStringdayofWeek(){ intw=(year/100/4-2*(year/100)+year%100+year%100 /4+26*(month+1)/10+day-1)%7; switch(w){ case1: return"Monday"; case2: return"Tuseday"; case3: return"Wednesday"; case4: return"Thursday"; case5: return"Friday"; case6: return"Saturday"; default: return"Sunday"; } } privatestaticbooleanisLeapYear(inty){ return((y%4==0&&y%100!=0)||y%400==0); } privatebooleanisIllegal(intm,intd,inty){ if(y<0||d<1||d>31) returnfalse; if(m>12||m<0) returnfalse; int[]monthofday={0,31,-1,31,30,31,30,31,31,30,31,30,31}; if(isLeapYear(y)){ monthofday[2]=29; }else{ monthofday[2]=28; } if(d>monthofday[m]) returnfalse; else returntrue; } publicSmartDate(intm,intd,inty){ if(!isIllegal(m,d,y)){ thrownewIllegalArgumentException("Illegaldate"); }else{ month=m; day=d; year=y; } } publicStringtoString(){ return(month()+"/"+day()+"/"+year()); } /* *大于返回1，等于返回0，小于返回-1； */ publicintcomparaTo(SmartDatethat){ if(this.year()==that.year()&&this.month()==that.month()&&this.day()==that.day())return0; if(this.year()>that.year())return1; if(this.month()>that.month())return1; if(this.day()>that.day())return1; return-1; } publicbooleanequals(Objectx){ if(this==x) returntrue; if(x==null) returnfalse; if(this.getClass()!=x.getClass()) returnfalse; SmartDatethat=(SmartDate)x; if(this.day!=that.day) returnfalse; if(this.month!=that.month) returnfalse; if(this.year!=that.year) returnfalse; returntrue; }}/**1.2.13實現(xiàn)Transaction模版*1.2.14實現(xiàn)Transaction模版equals()方法*1.2.19字符串解析。*/publicclassTransaction{ privateStringwho; privateSmartDatewhen; privatedoubleamount; publicTransaction(Stringwho,SmartDatewhen,doubleamount){ //TODOAuto-generatedconstructorstub if(who==null) thrownewIllegalArgumentException("Illegaldate"); this.who=who; this.when=when; this.amount=amount; } publicStringtoString(){ return(who+""+when.toString()+""+amount); } publicStringgetWho(){ returnwho; } publicvoidsetWho(Stringwho){ this.who=who; } publicSmartDategetWhen(){ returnwhen; } publicvoidsetWhen(SmartDatewhen){ this.when=when; } publicdoublegetAmount(){ returnamount; } publicvoidsetAmount(doubleamount){ this.amount=amount; } publicbooleanequals(Objectx){ if(this==x) returntrue; if(x==null) returnfalse; if(this.getClass()!=x.getClass()) returnfalse; Transactionthat=(Transaction)x; if(this.who!=that.who) returnfalse; if(this.when!=that.when) returnfalse; if(this.amount!=that.amount) returnfalse; returntrue; } publicintcompareTo(Transactionthat) { returnparaTo(that.when); } publicinthashCode(){ returnthis.toString().hashCode(); }}/**1.2.16有理數(shù)，實現(xiàn)有理數(shù)的加減乘除。*1.2.17有理數(shù)的健壯性，使用斷言來防止溢出**/publicclassRationalimplementsComparable<Rational>{ privateintnum;//分子 privateintden;//分母 privateintINT_max=2147483647; privateintINT_min=-2147483647; privatestaticRationalzero=newRational(0,1); publicRational(intnumerator,intdenominator){ //TODOAuto-generatedconstructorstub if(denominator==0){ thrownewRuntimeException("Denominatoriszero"); } intg=gcd(numerator,denominator); num=numerator/g; den=denominator/g; if(den<0){ den=-den; num=-num; } } publicintnumerator(){ returnnum; } publicintdenominator(){ returnden; } privateintgcd(intnumerator,intdenominator){ if(numerator<0) numerator=-numerator; if(denominator<0) denominator=-denominator; if(denominator==0) returnnumerator; returngcd(denominator,numerator%denominator); } /* *計算最小公倍數(shù) */ privateintlcm(intm,intn){ if(m<0) m=-m; if(n<0) n=-n; if(n==0) returnm; else{ intg=gcd(m,n);assertis_overflow_times(m,n/g):"lcmtimesoverflow"; returnm*(n/g); } } publicdoubletodouble(){ return(double)num/den; } publicStringtoString(){ if(den==1) returnnum+""; returnnum+"/"+den; } /* *(non-Javadoc) * *@seejava.lang.Comparable#compareTo(java.lang.Object)大于返回1，小于返回-1，等于返回0； */ publicintcompareTo(Rationalthat){ //TODOAuto-generatedmethodstub intlhs=this.num*that.den; intrhs=this.den*that.num; if(lhs<rhs) return-1; if(lhs>rhs) return1; return0; } publicbooleanequals(ObjectY){ if(Y==null) returnfalse; if(Y.getClass()!=this.getClass()) returnfalse; Rationalb=(Rational)Y; returnpareTo(b)==0; } /* *判斷加法溢出,如果溢出返回ture,不溢出返回flase; */ privatebooleanis_overflow_plus(inta,intb){ returna>=0?INT_max-a>b:INT_min-a<b; } /* *判斷乘法溢出,如果溢出返回ture,不溢出返回flase; * * */ privatebooleanis_overflow_times(inta,intb){ if(a<0)a=-a; if(b<0)b=-b; if(a==0||b==0) returnfalse; else returnINT_max/a>b; } publicRationaltimes(Rationalthat){ Rationalc=newRational(this.num,that.den); Rationald=newRational(that.num,this.den); asse