算法設(shè)計(jì)與分析課后習(xí)題解答

1、算法設(shè)計(jì)與分析基礎(chǔ)課后練習(xí)答案習(xí)題1.14.設(shè)計(jì)一個(gè)計(jì)算的算法，n是任意正整數(shù)。除了賦值和比較運(yùn)算，該算法只能用到基本的四則運(yùn)算操作。算法求輸入：一個(gè)正整數(shù)n2輸出：。step1:a=1；step2:若aan轉(zhuǎn)step3，否則輸出a；step3:a=a1轉(zhuǎn)step2；5.a用歐幾里德算法求gcd（31415，14142）。b.用歐幾里德算法求gcd（31415，14142）比檢查min｛m，n｝和gcd（m，n）間連續(xù)整數(shù)的算法快多少倍

2、？請(qǐng)估算一下。a.gcd(3141514142)=gcd(141423131)=gcd(31311618)=gcd(16181513)=gcd(1513105)=gcd(1513105)=gcd(10543)=gcd(4319)=gcd(195)=gcd(54)=gcd(41)=gcd(10)=1.b.有a可知計(jì)算gcd（31415，14142）歐幾里德算法做了11次除法。連續(xù)整數(shù)檢測(cè)算法在14142每次迭代過程中或者做了一次除法，或者

3、兩次除法，因此這個(gè)算法做除法的次數(shù)鑒于114142和214142之間，所以歐幾里德算法比此算法快11414211≈1300與21414211≈2600倍之間。6.證明等式gcd(mn)=gcd(nmmodn)對(duì)每一對(duì)正整數(shù)mn都成立.Hint:根據(jù)除法的定義不難證明:?如果d整除u和v那么d一定能整除uv?如果d整除u那么d也能夠整除u的任何整數(shù)倍ku.對(duì)于任意一對(duì)正整數(shù)mn若d能整除m和n那么d一定能整除n和r=mmodn=mqn；顯

4、然，若d能整除n和r，也一定能整除m=rqn和n。數(shù)對(duì)(mn)和(nr)具有相同的公約數(shù)的有限非空集，其中也包括了最大公約數(shù)。故gcd(mn)=gcd(nr)7.對(duì)于第一個(gè)數(shù)小于第二個(gè)數(shù)的一對(duì)數(shù)字歐幾里得算法將會(huì)如何處理該算法在處理這種輸入的過程中上述情況最多會(huì)發(fā)生幾次Hint:對(duì)于任何形如0=mn的一對(duì)數(shù)字Euclid算法在第一次疊代時(shí)交換m和n即gcd(mn)=gcd(nm)并且這種交換處理只發(fā)生一次.8.a.對(duì)于所有1≤mn≤10

5、的輸入Euclid算法最少要做幾次除法(1次)b.對(duì)于所有1≤mn≤10的輸入Euclid算法最多要做幾次除法(5次)gcd(58)習(xí)題1.21.(農(nóng)夫過河)算法DectoBin(n)將十進(jìn)制整數(shù)n轉(zhuǎn)換為二進(jìn)制整數(shù)的算法輸入：正整數(shù)n輸出：該正整數(shù)相應(yīng)的二進(jìn)制數(shù)，該數(shù)存放于數(shù)組Bin[1...n]中i=1whilen!=0doBin[i]=n%2n=(int)n2iwhilei!=0doprintBin[i]i9.考慮下面這個(gè)算法它求的