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

1、算法設(shè)計與分析基礎(chǔ)課后練習答案習題1.14.設(shè)計一個計算的算法，n是任意正整數(shù)。除了賦值和比較運算，該算法只能用到基本的四則運算操作。算法求輸入：一個正整數(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、？請估算一下。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可知計算gcd（31415，14142）歐幾里德算法做了11次除法。連續(xù)整數(shù)檢測算法在14142每次迭代過程中或者做了一次除法，或者

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

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

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