算法設(shè)計與分析第二版課后習(xí)題解答

習(xí)題1.14。設(shè)計一個計算k石」的算法,n是任意正整數(shù).除了賦值和比較運算，該算法只能用到基本的四則運算操作。算法求h五1〃輸入：一個正整數(shù)nl2//輸出：.step1：a=1；step2：若a*a〈n轉(zhuǎn)step3,否則輸出a;step3:a=a+1轉(zhuǎn)step2；.2.用歐幾里德算法求gcd(31415,14142)。b。用歐幾里德算法求gcd(31415,14142),比檢查min{m,n}和gcd(m,n)間連續(xù)整數(shù)的算法快多少倍？請估算一下。a。gcd(31415,14142)=gcd(14142,3131)=gcd(3131,1618)=gcd(1618,1513)=gcd(1513,105)=gcd(1513,105)=gcd(105,43)=gcd(43,19)=gcd(19,5)=gcd(5,4)=gcd(4,1)=gcd(1,0)=1.b。有a可知計算gcd(31415,14142)歐幾里德算法做了11次除法。連續(xù)整數(shù)檢測算法在14142每次迭代過程中或者做了一次除法,或者兩次除法,因此這個算法做除法的次數(shù)鑒于1?14142和2?14142之間，所以歐幾里德算法比此算法快1?14142/11處1300與2?14142/11處2600倍之間..證明等式gcd(m,n)=gcd(n,mmodn)對每一對正整數(shù)m,n都成立。Hint:根據(jù)除法的定義不難證明：如果d整除u和v,那么d一定能整除u士v;

如果d整除u,那么d也能夠整除u的任何整數(shù)倍ku。對于任意一對正整數(shù)巾,3若d能整除m和n,那么d一定能整除n和r二mmodn二m-qn；顯然，若d能整除n和r，也一定能整除m=r+qn和n.數(shù)對（m，n）和（n，r）具有相同的公約數(shù)的有限非空集，其中也包括了最大公約數(shù)。故gcd（m,n）=gcd（n,r）7.對于第一個數(shù)小于第二個數(shù)的一對數(shù)字，歐幾里得算法將會如何處理?該算法在處理這種輸入的過程中，上述情況最多會發(fā)生幾次？Hint：對于任何形如0<=m〈n的一對數(shù)字，Euclid算法在第一次疊代時交換m和n,即gcd（m,n）=gcd（n，m）并且這種交換處理只發(fā)生一次。8.a。對于所有1WmnW108.a。對于所有1WmnW10的輸入,Euclid算法最少要做幾次除法？（1次）b.對于所有1WmnW10的輸入,Euclid算法最多要做幾次除法？（5次）gcd（5，8）習(xí)題1.21.（農(nóng)夫過河）G-山羊C一白菜P-1.（農(nóng)夫過河）G-山羊C一白菜P-農(nóng)夫 W-狼2。（過橋問題）1,2,5,10——分別代表4個人，f—手電筒4。對于任意實系數(shù)a,b，c，某個算法能求方程ax八2+bx+c=0的實根，寫出上述算法的偽代碼(可以假設(shè)$4^(x)是求平方根的函數(shù))算法Quadratic(a,b,c)〃求方程ax八2+bx+c=0的實根的算法//輸入:實系數(shù)a,b,c//輸出：實根或者無解信息IfaW0D—b*b-4*a*cIfD〉0temp12*ax11(—b+sqrt(D))/tempx21(—b—sqrt(D))/tempreturnx1,x2elseifD=0return-b/(2*a)elsereturn“norealroots”else//a=0ifbW0return-c/belse//a=b=0ifc=0return“norealnumbers"elsereturn“norealroots"5。描述將十進制整數(shù)表達為二進制整數(shù)的標(biāo)準(zhǔn)算法a。用文字描述b.用偽代碼描述解答：a.將十進制整數(shù)轉(zhuǎn)換為二進制整數(shù)的算法輸入：一個正整數(shù)n輸出：正整數(shù)門相應(yīng)的二進制數(shù)第一步：用n除以2,余數(shù)賦給Ki(i=0，1,2。。.)，商賦給n第二步：如果門=0，則到第三步，否則重復(fù)第一步第三步：將Ki按照i從高到低的順序輸出b.偽代碼算法DectoBin(n)〃將十進制整數(shù)n轉(zhuǎn)換為二進制整數(shù)的算法〃輸入：正整數(shù)n〃輸出：該正整數(shù)相應(yīng)的二進制數(shù)，該數(shù)存放于數(shù)組Bin[1..。n]中i=1whilen!=0do{Bin[i]=n%2;n=(int)n/2;i++；}whilei!=0do{printBin[i];（完整word）算法設(shè)計與分析第二版課后習(xí)題解答9?？紤]下面這個算法,它求的是數(shù)組中大小相差最小的兩個元素的差.（算法略）對這個算法做盡可能多的改進.算法MinDistance（A[0.。n—1]）〃輸入：數(shù)組A[00.n-l]//輸出：m6smallestdistancedbetweentwoofitselementsdmin—ncfori―0ton—2daforj-B+1t。打一1doifmp-A\i'_-A[j'iftemp<dmindmin—tempreturndmm習(xí)題1.31.考慮這樣一個排序算法,該算法對于待排序的數(shù)組中的每一個元素，計算比它小的元素個數(shù)，然后利用這個信息，將各個元素放到有序數(shù)組的相應(yīng)位置上去.for￡「（）to門.一1doCount[z]_0for2—（）ton—2doforj—?；+1to7?—1doifA\i]<A[j]Count[jCount[j\+1cl5cCouvzti「Count￡]+1far￡「（）ton-idoS[County—A[i]a。應(yīng)用該算法對列表”60,35,81,98,14,47”排序b。該算法穩(wěn)定嗎？c。該算法在位嗎？解：a。該算法對列表a。該算法對列表”60,35,81,98,14,47"排序的過程如下所示:b.該算法不穩(wěn)定.比如對列表”2,2*"排序c.該算法不在位.額外空間forSandCount口4。(古老的七橋問題)第