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

1、(完整word)算法設(shè)計與分析第二版課后習(xí)題解答(完整word)算法設(shè)計與分析第二版課后習(xí)題解答算法設(shè)計與分析基礎(chǔ)課后練習(xí)答案習(xí)題 1.14。設(shè)計一個計算的算法,n4。設(shè)計一個計算的算法,n算法求/輸入:一個正整數(shù) n 2/ 輸 出 ：. step1：a=1；step2aanstep 3step3:a=a+1step 2；5. a用歐幾里德算法求 gcd（31415，14142)。b。 用歐幾里德算法求gcd（31415，14142，比檢查minm，n和gcd（m,n）間連續(xù)整數(shù)的算法快多少倍？請估算一下。agcd(3141514142)gcd（14142,3131）gcd(31311618）

2、 =gcd（1618,1513)gcd(1513105)= = 43） =gcd（43, = 5） = gcd(5, = gcd(4, = 0） = 1.b。有a可知計算gcd（31415，14142）歐幾里德算法做了11次除法。連續(xù)整數(shù)檢測算法在14142每次迭代過程中或者做了一次除法,或者兩次除法，因此這個算法做除法的次數(shù)鑒于之間,所以歐幾里德算法比此算法快214142/11 2600 倍之間.gcd（m，n）=gcd(n,mmodn）m，nHint:根據(jù)除法的定義不難證明：如果duv，duv;如果d 整除 u，那么 d 也能夠整除 u 的任何整數(shù)倍 ku。m,ndm 和n，dnr=m m

3、od dnr，m=r+qnn.數(shù)對(m，n)和（n，r）具有相同的公約數(shù)的有限非空集，其中也包括了最大公約數(shù)。故 gcd（m,n)=gcd(n，r）的過程中，上述情況最多會發(fā)生幾次？Hint：0=mn,Euclidmn，gcd（m,n）=gcd（n，m)并且這種交換處理只發(fā)生一次。a1m，n10Euclid(1b.1m，n10Euclid?(5gcd（5，8）習(xí)題 1.21.(農(nóng)夫過河）P-農(nóng)夫W-狼G山羊C白2。(過橋問題)1,2,5,10-分別代表 4 個人, f手電筒4。對于任意實系數(shù)a,bc，某個算法能求方程ax2+bx+c=0sqrt（x)是求平方根的函數(shù))算法 Quadratic(

4、a，b，c)/求方程 ax2+bx+c=0 的實根的算法/輸入:實系數(shù)a，b，c/輸出：實根或者無解信息If a0Dbb-4ac If D0temp2a x1（b+sqrt(D)/temp x2(bsqrt(D)）/temp return x1,x2else if D=0 return b/（2a） else return “no real roots”else /a=0if b0 return else /a=b=0if c=0 return “no real numbers else return “no real roots5。 5。 描述將十進(jìn)制整數(shù)表達(dá)為二進(jìn)制整數(shù)的標(biāo)準(zhǔn)算法a。用文字

5、描述b.用偽代碼描述解答：n輸出：正整數(shù) n 相應(yīng)的二進(jìn)制數(shù)n2Ki(i=0，1,2。.）,n=0，則到第三步，否則重復(fù)第一步Kiib.偽代碼算法 DectoBin(n）/將十進(jìn)制整數(shù) n 轉(zhuǎn)換為二進(jìn)制整數(shù)的算法/輸入：正整數(shù) n/輸出:該正整數(shù)相應(yīng)的二進(jìn)制數(shù),該數(shù)存放于數(shù)組 Bin1.。n中i=1while n！=0 do Bini=n%2； n=(int)n/2； i+；while i！=0 do print i-;9?？紤]下面這個算法,它求的是數(shù)組中大小相差最小的兩個元素的差.（對這個算法做盡可能多的改進(jìn).算法 MinDistance(A0.。n1)/輸入：數(shù)組 A0。.n-1/輸出:the smallest distance d between two of its elements習(xí)題 1.31.然后利用這個信息，將各個元素放到有序數(shù)組的相應(yīng)位置上去.a。應(yīng)用該算法對列表”60，35,81，98,14，47”排序b。該算法穩(wěn)定嗎?c。該算法在位嗎? 解:a。 該算法對列表”60，35,81,98，14,47排序的過程如下所示：該算法不穩(wěn)定.比如對列表”2,2*”排序forSandCount 4（古老的七橋問題)第 2 章 2。7.（ a。 如