習(xí)題講解高運(yùn)張迎亞趙垠蘭趙振東作業(yè)要求字跡整潔過程清晰Chapter1Recursion：程序調(diào)用自身的編程技巧稱為遞歸。把一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來求解。遞歸只需少量的程序就可描述出解題過程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。遞歸需要有邊界條件、遞歸返回段和遞歸前進(jìn)段。當(dāng)邊界條件滿足時(shí)，遞歸返回；反之，遞歸前進(jìn)。德羅斯特效應(yīng)遞歸的一種視覺形式，是指一張圖片的某個(gè)部分與整張圖片相同，如此產(chǎn)生無限循環(huán)。從前有座山，山上有座廟，廟里有個(gè)老和尚，一天老和尚對(duì)小和尚講故事，從前有座山，山上有座廟。。。舉個(gè)栗子再來一個(gè)？遞歸的缺點(diǎn)遞歸算法解題相對(duì)常用的算法如普通循環(huán)等，運(yùn)行效率較低。在遞歸調(diào)用的過程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開辟了棧來存儲(chǔ)。遞歸次數(shù)過多容易造成棧溢出等。應(yīng)該盡量避免使用遞歸，除非沒有更好的算法或者某種特定情況下遞歸更為適合。Exercises1Writearecursivemethodthatreturnsthenumberof1’sinthebinaryrepresentationofN.Usethefactthatisequaltothenumberof1’sintherepresentationofN/2,plus1,ifNisodd.數(shù)字N二進(jìn)制中1的個(gè)數(shù)設(shè)N的二進(jìn)制表示有n位，即求n位二進(jìn)制數(shù)中1的個(gè)數(shù)，即求前n－1位二進(jìn)制數(shù)中1的個(gè)數(shù)與最后一位1的個(gè)數(shù)的總和。邊界條件：(n==0)遞歸返回段：返回n遞歸前進(jìn)段：count(n/2)+n%2;代碼publicintcount(intn){if(n==0){return0;}else{returnn%2+count(n/2);}}條件n==1不用作為邊界條件，每一次會(huì)多一次判斷。不必討論n的奇偶性。Exercises2Writetheroutineswisethefollowingdeclarations:publicvoidpermute(Stringstr);privatevoidpermute(char[]str,intlow,inthigh)ThefirstroutineisadriverthatcallsthesecondandprintsallthepermutationsofthecharactersinStringstr.Ifstris“abc”,thenthestringsthatareoutputareabc,acb,bac,bca,cab,andcba.Userecursionforthesecondroutine.全排列n個(gè)字母的全排列，一個(gè)一個(gè)地進(jìn)行挑選邊界條件：只剩一個(gè)字母(low==high)遞歸返回段：輸出得到的一個(gè)排列遞歸前進(jìn)段：對(duì)剩下的n-1個(gè)字母進(jìn)行全排列abcabcbaccbaabcacbabcacb//low和high標(biāo)記進(jìn)行全排列的字母的范圍publicvoidperm(char[]str,intlow,inthigh){if(low==high){for(charc:str)cout<<c;cout<<endl;}else{for(inti=low;i<=high;i++){swap(str,low,i);permute(str,low+1,high);swap(str,low,i);}}}交換函數(shù)//str是引用傳遞(passedbyreference)voidswap(char[]str,inti,intj){chartemp=str[i];str[i]=str[j];str[j]=temp;}Exercises3已知a[n]為整型數(shù)組，試寫出實(shí)現(xiàn)下列運(yùn)算的遞歸算法。1）求數(shù)組a中的最大整數(shù)。2）求n個(gè)整數(shù)的平均值數(shù)組中最大整數(shù)(1)將數(shù)組中前n-1個(gè)數(shù)的最大值與第n個(gè)數(shù)比較，返回較大的。邊界條件：(n==1)。遞歸返回段：返回a[0]。遞歸前進(jìn)段：將剩下的n個(gè)數(shù)的前n-1個(gè)數(shù)的最大值與第n個(gè)數(shù)進(jìn)行比較，返回較大的。publicintfindMax(int[]a,intn){//n表示第n個(gè)元素，對(duì)應(yīng)數(shù)組a[n-1]if(n==1){returna[0];}else{inttemp=findMax(a,n-1);returntemp>a[n-1]?temp:a[n-1];}}數(shù)組中最大整數(shù)(2)分別求出數(shù)組前半段和后半段的最大值，返回其中較大的。邊界條件：(low==high)。遞歸返回段：返回a[low]。遞歸前進(jìn)段：計(jì)算剩下的n個(gè)數(shù)的前半段和后半段的最大值，返回其中較大的。//初始值low=0,high=a.lengthintmax(int[]a,intlow,inthigh){if(low==high)returna[low];else{intx=max(a,low,(low+high)/2);inty=max(a,(low+high)/2+1,high);returnx>y?x:y;}}n個(gè)整數(shù)的平均值求出前n-1個(gè)數(shù)的和，再求它跟第n個(gè)數(shù)的平均值。邊界條件：(n==1)。遞歸返回段：返回a[0]。遞歸前進(jìn)段：計(jì)算剩下的n個(gè)數(shù)的前n-1個(gè)數(shù)的和，再求它跟第n個(gè)數(shù)的平均值。publicdoublegetAverage(int[]a,intn){//n表示數(shù)組的第n個(gè)元素if(n==1)returna[0];elsereturn(getAverage(a,n-1)*(n-1)+a[n-1])/n;}Exercises4Writearecursivemethodthatcalculatesandreturnsthelengthofalinkedlist.計(jì)算和返回鏈表長(zhǎng)度publicintlength(ListNodea)//計(jì)算方法{if(a==null)return0;elsereturn1+length(a.next);}classListNode//節(jié)點(diǎn)類{Objectcontent=null;ListNodenext=null;}Exercises5Checkrecursivelyifthefollowingobjectsarepalindromes:a.awordb.asentence(ignoringblanks,loweranduppercasedifferences,andpunctuationmarkssothat“Madam,I’mAdam”isacceptedasapalindrome)檢測(cè)回文a)一個(gè)單詞b)一個(gè)句子(忽略空格,大小寫,標(biāo)點(diǎn),例如“Madam,I’mAdam”是一個(gè)回文)a)檢測(cè)回文單詞比較頭尾兩個(gè)字符，相同則向中間聚攏比較，不相同則返回false。邊界條件和遞歸返回段：要比較的子字符竄為空，返回true遞歸前進(jìn)段：截取當(dāng)前字符串從位置1到位置length-1的子字符串，返回其回文性。publicstaticbooleanpalindrome0(Stringword,intlow,inthigh){if(low>high)returntrue;if(word.charAt(low)==word.charAt(high)||Math.abs(word.charAt(low)-word.charAt(high))==32)returnpalindrome(word,low+1,high-1);elsereturnfalse;}b)檢測(cè)回文句子在遞歸過程中去除不符合要求的字符publicstaticbooleanpalindrome(Stringword,intlow,inthigh){if(low>high)returntrue;while(!Character.isLetter(word.charAt(low)))low++;while(!Character.isLetter(word.charAt(high)))high--;if(word.charAt(low)==word.charAt(high)||Math.abs(word.charAt(low)-word.charAt(high))==32)returnpalindrome(word,low+1,high-1);elsereturnfalse;}另一種解法首先去除不符合要求的字符，然后檢測(cè)其回文性publicstaticbooleansentence(Stringword){Strings1=word.toLowerCase();Strings2="";for(inti=0;i<word.length();i++)if(s1.charAt(i)>='a'&&s1.charAt(i)<='z')s2+=s1.charAt(i);returnpalindrome(s2,0,s2.length()-1);}Chapter2Timecomplexity程序的運(yùn)行時(shí)間Operationcounts：找出程序的關(guān)鍵操作，確定它們的執(zhí)行次數(shù)。Stepcounts：確定程序總共執(zhí)行的次數(shù)。AsymptoticNotation(O,,,o)：符號(hào)化描述。i的取值問題連續(xù)的[1,n]離散的2,4,8,…Exercise1Fselectkth(inta[],intk,intn){inti,j,mini,temp;for(i=0;i<k;i++){mini=i;for(j=i+1;j<n;j++)if(a[j]<a[mini])mini=j;tmp=a[i];a[i]=a[mini];a[mini]=tmp;}returna[k-1];}

Findthecomputationalcomplexityforthefollowingfourloops:c.for(cnt3=0,i=1;i<=n;i*=2)for(j=1;j<=n;j++)cnt3++;d.for(cnt4=0,i=1;i<=n;i*=2)for(j=1;j<=i;j++)cnt4++;Exercise2

Foreachofthefollowingtwoprogramfragments:Giveananalysisoftherunningtime(Big-Ohwilldo)sum=0;for(i=0;i<n;i++)for(j=0;j<i*i;j++)for(k=0;k<j;k++)sum++;sum=0;for(i=1;i<n;i++)for(j=0;j<i*i;j++)if(j%i==0)for(k=0;k<j;k++)sum++;Exercise3

Exercise4

4.

設(shè)n為正整數(shù)，