算法設(shè)計(jì)與分析習(xí)題答案1 6章

1、1.習(xí)題1圖論誕生于七橋問(wèn)題。出生于瑞士的偉大數(shù)學(xué)家歐拉 提出并解決了該問(wèn)題。七橋問(wèn)題是這樣描述的： 一個(gè)人是否能在一次步行中穿越哥尼斯堡（現(xiàn) 在叫加里寧格勒，在波羅的海南岸）城中全部 的七座橋后回到起點(diǎn)，且每座橋只經(jīng)過(guò)一次， 圖是這條河以及河上的兩個(gè)島和七座橋的草 圖。請(qǐng)將該問(wèn)題的數(shù)據(jù)模型抽象出來(lái)，并判斷 此問(wèn)題是否有解。(Leonhard Euler ,1707 1783)七橋問(wèn)題屬于一筆畫(huà)問(wèn)題。輸入：一個(gè)起點(diǎn)輸出：相同的點(diǎn)一次步行經(jīng)過(guò)七座橋，且每次只經(jīng)歷過(guò)一次回到起點(diǎn)1，2，3，該問(wèn)題無(wú)解：能一筆畫(huà)的圖形只有兩類(lèi)：一類(lèi)是所有的點(diǎn)都是偶點(diǎn)。另一類(lèi)是只有二個(gè) 奇點(diǎn)的圖形。2 .在歐幾里德提出

2、的歐幾里德算法中（即最初的歐幾里德算法）用的不是除法而是減法。請(qǐng)用偽代碼描述這個(gè)版本的歐幾里德算法=m-n2.循環(huán)直到r=0m=nn=rr=m-n3輸出m3 .設(shè)計(jì)算法求數(shù)組中相差最小的兩個(gè)元素（稱(chēng)為最接近數(shù)）的差。要求分別給出偽代 碼和C+描述。編寫(xiě)程序，求n至少為多大時(shí)，n個(gè)“ 1”組成的整數(shù)能被 2013整除。#in clude using n ames pace std;int mai n()double value=0;for(int n=1;n=10000 ;+n)value=value*10+1;if(value%2013=0)coutn 至少為 :nendl; break;計(jì)算

3、n值的問(wèn)題能精確求解嗎編寫(xiě)程序，求解滿(mǎn)足給定精度要求的#include using namespace std;int main ()double a,b;double arctan(double x); 圣經(jīng)上說(shuō)：神 6 天創(chuàng)造天地萬(wàn)有，第 7 日安歇。為什么是 6 天呢任何一個(gè)自然數(shù)的因數(shù)中都有 1 和它本身，所有小于它本身的因數(shù)稱(chēng)為這個(gè)數(shù)的真因 數(shù)，如果一個(gè)自然數(shù)的真因數(shù)之和等于它本身，這個(gè)自然數(shù)稱(chēng)為完美數(shù)。例如，6=1+2+3，因此 6 是完美數(shù)。神 6 天創(chuàng)造世界，暗示著該創(chuàng)造是完美的。設(shè)計(jì)算法，判斷給定的自然 數(shù)是否是完美數(shù)#include using namespace std;

4、int main()int value, k=1; cinvalue;for (int i = 2;i!=value;+i) while (value % i = 0 )k+=i; 有 4 個(gè)人打算過(guò)橋，這個(gè)橋每次最多只能有兩個(gè)人同時(shí)通過(guò)。他們都 在橋的某一端，并且是在晚上，過(guò)橋需要一只手電筒，而他們只有一只手電筒。這就意味 著兩個(gè)人過(guò)橋后必須有一個(gè)人將手電筒帶回來(lái)。 每個(gè)人走路的速度是不同的： 甲過(guò)橋要用 1 分鐘，乙過(guò)橋要用 2 分鐘，丙過(guò)橋要用 5 分鐘，丁過(guò)橋要用 10 分鐘，顯然，兩個(gè)人走路的 速度等于其中較慢那個(gè)人的速度，問(wèn)題是他們?nèi)窟^(guò)橋最少要用多長(zhǎng)時(shí)間 由于甲過(guò)橋時(shí)間最短，那么

5、每次傳遞手電的工作應(yīng)有甲完成甲每次分別帶著乙丙丁過(guò)橋例如：第一趟：甲，乙過(guò)橋且甲回來(lái)第二趟：甲，丙過(guò)橋且甲回來(lái)第一趟：甲，丁過(guò)橋 一共用時(shí)19小時(shí)9 .歐幾里德游戲：開(kāi)始的時(shí)候，白板上有兩個(gè)不相等的正整數(shù)，兩個(gè)玩家交替行動(dòng)， 每次行動(dòng)時(shí)，當(dāng)前玩家都必須在白板上寫(xiě)出任意兩個(gè)已經(jīng)出現(xiàn)在板上的數(shù)字的差，而且這 個(gè)數(shù)字必須是新的，也就是說(shuō)，和白板上的任何一個(gè)已有的數(shù)字都不相同，當(dāng)一方再也寫(xiě) 不出新數(shù)字時(shí)，他就輸了。請(qǐng)問(wèn)，你是選擇先行動(dòng)還是后行動(dòng)為什么一共設(shè)最初兩個(gè)數(shù)較大的為a,較小的為b兩個(gè)數(shù)的最大公約數(shù)為factor。則最終能出現(xiàn)的數(shù)包括：factor, factor*2, factor*3,，fa

6、ctor*(a/factor)=a.a/factor 個(gè)。如果a/factor 是奇數(shù)，就選擇先行動(dòng)；否則就后行動(dòng)。習(xí)題21.如果 Ti(n)=qf ( n) , T2(n)=qg(n)，解答下列問(wèn)題： (1 )證明加法定理：Ti(n) + T2(n)=maxC(f ( n), C(g(n)；(2) 證明乘法定理：T1(n) XT2(n)=Cf ( n) x Cg(n);(3) 舉例說(shuō)明在什么情況下應(yīng)用加法定理和乘法定理(3)比如在for (f(n)for(g( n)中應(yīng)該用乘法定理如果在“講兩個(gè)數(shù)組合并成一個(gè)數(shù)組時(shí)”，應(yīng)當(dāng)用加法定理2 考慮下面的算法，回答下列問(wèn)題：算法完成什么功能算法的基本

7、語(yǔ)句是什么基本語(yǔ)句 執(zhí)行了多少次算法的時(shí)間復(fù)雜性是多少(2) int Q(int n)if (n = 1)return 1;elsereturn Q(n-1) + 2 * n - 1;(1) int Stery(int n) int S = 0;for (int i = 1; i = n;i+)(1)完成的是* i1-n的平方和基本語(yǔ)句S; s+=i*i，執(zhí)行了 n次時(shí)間復(fù)雜度0(n)(2)完成的是n的平方-1，執(zhí)行了 n次基本語(yǔ)句：return Q( n-1) + 2 * n時(shí)間復(fù)雜度0(n)3. 分析以下程序段中基本語(yǔ)句的執(zhí)行次數(shù)是多少，要求列出計(jì)算公式。(1) for (i = 1; i

8、 = n; i+)if (2*i = n)for (j = 2*i; j = n;(2) m = 0;for (i = 1; i = n; i+) for (j = 1; j = 2*i;=j+)(1) 基本語(yǔ)句2*i1) return 3*T( n-1); int T(i nt n)if(n=1)return 1;else if(n 1) return 2*T( n/3)+n; 5.求下列問(wèn)題的平凡下界,(1)(2)(3)(4)并指出其下界是否緊密。求數(shù)組中的最大元素；判斷鄰接矩陣表示的無(wú)向圖是不是完全圖; 確定數(shù)組中的元素是否都是惟一的； 生成一個(gè)具有n個(gè)元素集合的所有子集Q (n) 緊密

9、Q (n*n)Q （logn+n）（先進(jìn)行快排，然后進(jìn)行比較查找）Q （2人n）發(fā)明的，當(dāng)他把該發(fā)明獻(xiàn)給國(guó)王時(shí)，國(guó)Shashi要求以這種方式給他一些&國(guó)際象棋是很久以前由一個(gè)印度人Shashi王很高興，就許諾可以給這個(gè)發(fā)明人任何他想要的獎(jiǎng)賞。 糧食：棋盤(pán)的第1個(gè)方格內(nèi)只放1粒麥粒，第2格2粒，第3格4粒，第4格8粒, 以此類(lèi)推，直到64個(gè)方格全部放滿(mǎn)。這個(gè)獎(jiǎng)賞的最終結(jié)果會(huì)是什么樣呢#in cludeusing n ames pace std;int mai n()long double result=1; double j=1;for(i nt i=1;i=64;+i) j=j*2;resul

10、t+=j;j+;coutresulte ndl;return 0;1的平凡情形）。=05. 設(shè)計(jì)算法求解an mod m其中a、n和超出int型的表示范圍，應(yīng)該每做一次乘法之后對(duì)m均為大于1的整數(shù)。（提示：為了避免 an n取模）習(xí)題31.假設(shè)在文本ababcabccabccacbab中查找模式abccac，寫(xiě)出分別采用 BF算法和 KMP算法的串匹配過(guò)6/8化簡(jiǎn)為3/4 。式化簡(jiǎn)。設(shè)計(jì)算法，將一個(gè)給定的真分?jǐn)?shù)化簡(jiǎn)為最簡(jiǎn)分?jǐn)?shù)形式。例如，將 #in clude using n ames pace std;int mai n()intn;數(shù)字游戲。把數(shù)字1,2,9這9個(gè)數(shù)字填入以下含有加、減、乘、

11、除的四則運(yùn)算式中，使得該等式成立。要求9個(gè)數(shù)字均出現(xiàn)一次且僅出現(xiàn)一次，且數(shù)字 1不能出現(xiàn)在乘和除的一位數(shù)中（即排除運(yùn)算式中一位數(shù)為X +-#in clude using n ames pace std;int square(i nt x) return x*x;設(shè)計(jì)算法，在數(shù)組 r n中刪除所有元素值為 x的元素，要求時(shí)間復(fù)雜性為 Qn),空間 復(fù)雜性為 O(1) 。7. 設(shè)計(jì)算法，在數(shù)組 rn 中刪除重復(fù)的元素，要求移動(dòng)元素的次數(shù)較少并使剩余元素 間的相對(duì)次序保持不變。#include using namespace std;void deletere(int a,int N)int b10

12、0=0;int i,k;k=0;static int j=0;for(i=0;iN;i+) bai+;for(i=0;i100;i+)if(bi!=0)if(bi=2)k+;aj=i; j+;for(i=0;iN-k;i+)coutai 0且y0;使目標(biāo)函數(shù)3x+5y取得極大值。#in clude using n ames pace std;int mai n()int x,y,x0,y0;int summax=0,te mp=0;for(x0=0;x0=4;+x0)for(y0=0;(x0+y0=4)&( x0+3*y0=summax)summax=te mp;x=x0;變位詞。給定兩個(gè)單詞

13、，判斷這兩個(gè)單詞是否是變位詞。如果兩個(gè)單詞的字母完全相同，只是位置有所不同，則這兩個(gè)單詞稱(chēng)為變位詞。例如，eat和tea是變位詞。分治法的時(shí)間性能與直接計(jì)算最小問(wèn)題的時(shí)間、合并子問(wèn)題解的時(shí)間以及子問(wèn)題的個(gè) 數(shù)有關(guān)，試說(shuō)明這幾個(gè)參數(shù)與分治法時(shí)間復(fù)雜性之間的關(guān)系Qn)。2. 證明：如果分治法的合并可以在線性時(shí)間內(nèi)完成，則當(dāng)子問(wèn)題的規(guī)模之和小于原問(wèn) 題的規(guī)模時(shí)，算法的時(shí)間復(fù)雜性可達(dá)到O(N)=2*O(N/2)+xO(N)+x=2*O(N/2)+2*xa*O(N)+x=a*(2*O(N/2)+x)+x=2*a *O(N/2)+(a+1)*x 由此可知，時(shí)間復(fù)雜度可達(dá)到 O(n);3. 分治策略一定導(dǎo)致

14、遞歸嗎如果是，請(qǐng)解釋原因。如果不是，給出一個(gè)不包含遞歸的分 治例子，并闡述這種分治和包含遞歸的分治的主要不同。不一定導(dǎo)致遞歸。 如非遞歸的二叉樹(shù)中序遍歷。 這種分治方法與遞歸的二叉樹(shù)中序遍歷主要區(qū)別是：應(yīng)用了棧這個(gè)數(shù)據(jù)結(jié)構(gòu)。4. 對(duì)于待排序序列 （5, 3, 1, 9） ，分別畫(huà)出歸并排序和快速排序的遞歸運(yùn)行軌跡。歸并排序：第一趟：第二趟：第三趟： 快速排序：第一趟： 55,3)(1,9)；3.5.1.91.3.5.9）；）；,3,1,9）；設(shè)計(jì)分治算法求一個(gè)數(shù)組中的最大元素，并分析時(shí)間性能。設(shè)計(jì)分治算法，實(shí)現(xiàn)將數(shù)組A n中所有元素循環(huán)左移k個(gè)位置，要求時(shí)間復(fù)雜性為On），空間復(fù)雜性為 qi）

15、。例如，對(duì) abcdefgh循環(huán)左移3位得到defghabc。設(shè)計(jì)遞歸算法生成 n 個(gè)元素的所有排列對(duì)象。#include using namespace std;int data100;設(shè)計(jì)分治算法求解一維空間上 n個(gè)點(diǎn)的最近對(duì)問(wèn)題。參見(jiàn)最近對(duì)問(wèn)題的算法分析及算法實(shí)現(xiàn)9.在有序序列（ri,2,rn）中，存在序號(hào)i （1 i n）,使得ri=i。請(qǐng)?jiān)O(shè)計(jì)一個(gè)分 治算法找到這個(gè)元素，要求算法在最壞情況下的時(shí)間性能為O（log 2n）。在一個(gè)序列中出現(xiàn)次數(shù)最多的元素稱(chēng)為眾數(shù)。請(qǐng)?jiān)O(shè)計(jì)算法尋找眾數(shù)并分析算法的時(shí)間 復(fù)雜性。設(shè)M是一個(gè)nxn的整數(shù)矩陣，其中每一行（從左到右）和每一列（從上到下）的元 素都按

16、升序排列。設(shè)計(jì)分治算法確定一個(gè)給定的整數(shù)x是否在M中，并分析算法的時(shí)間復(fù)雜性。12.設(shè)S是n （n為偶數(shù)）個(gè)不等的正整數(shù)的集合，要求將集合S劃分為子集S和蟲(chóng)使得| S1|=| S2|=n/2 ，且兩個(gè)子集元素之和的差達(dá)到最大。設(shè) a1, 稱(chēng)為該排列的一個(gè)逆序。例如， 排列中含有逆序的個(gè)數(shù)。a2,an是集合1,2,n的一個(gè)排列，如果2, 3, 1 有兩個(gè)逆序： （3, 1）i aj，則序偶（ai, aQ和（2, 1）。設(shè)計(jì)算法統(tǒng)計(jì)給定循環(huán)賽日程安排問(wèn)題。設(shè)有的比賽日程表：（ 1 ）每個(gè)選手必須與其他 n-1（ 2）每個(gè)選手一天只能賽一次。n=2k個(gè)選手要進(jìn)行網(wǎng)球循環(huán)賽,要求設(shè)計(jì)一個(gè)滿(mǎn)足以下要求個(gè)

17、選手各賽一次；采用分治方法。采用遞歸方法，繼續(xù)進(jìn)行分組，直到只剩下 2 個(gè)選手時(shí)，然將2你選手分為2你-1兩組，后進(jìn)行比賽，回溯就可以指定比賽日程表了15.格雷碼是一個(gè)長(zhǎng)度為 2n的序列，序列中無(wú)相同元素，且每個(gè)元素都是長(zhǎng)度為n的二進(jìn)制位串，相鄰元素恰好只有 1 位不同。例如長(zhǎng)度為 23的格雷碼為 （000, 001, 011, 010, 110, 111, 101, 100） 。設(shè)計(jì)分治算法對(duì)任意的 n 值構(gòu)造相應(yīng)的格雷碼。矩陣乘法。兩個(gè) nx n的矩陣X和Y的乘積得到另外一個(gè)nx n的矩陣Z,且Zj滿(mǎn)足（1 i , j w n）,這個(gè)公式給出了運(yùn)行時(shí)間為O n3）的算法。可以用分的子塊，從

18、而X和Y的乘積治法解決矩陣乘法問(wèn)題，將矩陣X和Y都劃分成四個(gè)n/2 x n/2可以用這些子塊進(jìn)行表達(dá)，即AE、BG、AF、BH、CE、DG、從而得到分治算法：先遞歸地計(jì)算 8 個(gè)規(guī)模為 n/2 的矩陣乘積CF DH然后再花費(fèi) qn2）的時(shí)間完成加法運(yùn)算即可。請(qǐng)?jiān)O(shè)計(jì)分治算法實(shí)現(xiàn)矩陣乘法，并分 析時(shí)間性能。能否再改進(jìn)這個(gè)分治算法習(xí)題 51. 下面這個(gè)折半查找算法正確嗎如果正確，請(qǐng)給出算法的正確性證明，如果不正確，請(qǐng)說(shuō) 明產(chǎn)生錯(cuò)誤的原因。int BinSearch(int r , int n, int k)int low = 0, high = n - 1;int mid;while (low =

19、high)mid = (low + high) / 2;if (k rmid) low = mid; else return mid;return 0;錯(cuò)誤。正確算法：int BinSearch1(int r , int n, int k)int low = 0, high = n - 1;int mid;while (low = high)mid = (low + high) / 2;if (k rmid) low =mid + 1 ;else return mid;return 0;2. 請(qǐng)寫(xiě)出折半查找的遞歸算法，并分析時(shí)間性能。lcm( m n)與 m和 nn) )k2,kn,kn+1

20、)調(diào)求兩個(gè)正整數(shù) m和n的最小公倍數(shù)。(提示：m和n的最小公倍數(shù) 的最大公約數(shù) gcd(m n)之間有如下關(guān)系：lcm( m n)=nix n/gcd( m插入法調(diào)整堆。已知(ki, k2,kn)是堆，設(shè)計(jì)算法將(ki, 整為堆(假設(shè)調(diào)整為大根堆) 。參照：void SiftHea p(int r , i nt k, int n) int i, j, temp;設(shè)計(jì)算法實(shí)現(xiàn)在大根堆中刪除一個(gè)元Olog 2n)。i = k; j = 2 * i + 1;素，要求算法的時(shí)間復(fù)雜性為5065251301301226065203104010401208020803250圖俄式乘法n m計(jì)算兩個(gè)正整數(shù)n

21、和m的乘積有一個(gè)很有名的算法稱(chēng) 為俄式乘法，其思想是利用了一個(gè)規(guī)模是n的解和一個(gè)規(guī)模是n/2的解之間的關(guān)系：nx m= n/2 x 2m (當(dāng)n是偶數(shù)) 或：nx m= (n-1)/2 x 2m m (當(dāng) n 是奇數(shù))，并以 1 x m= m 作為算法結(jié)束的條件。例如，圖給出了利用俄式乘法計(jì)算 50x 65的例子。據(jù)說(shuō)十九世紀(jì)的俄國(guó)農(nóng)夫使用該算法并因 此得名，這個(gè)算法也使得乘法的硬件實(shí)現(xiàn)速度非?？欤?為只使用移位就可以完成二進(jìn)制數(shù)的折半和加倍。請(qǐng)?jiān)O(shè)計(jì) 算法實(shí)現(xiàn)俄式乘法。n根火柴，兩個(gè)拿子游戲?？紤]下面這個(gè)游戲：桌子上有一堆火柴，游戲開(kāi)始時(shí)共有玩家輪流拿走1, 2, 3或4根火柴，拿走最后一根

22、火柴的玩家為獲勝方。請(qǐng)為先走的玩家 設(shè)計(jì)一個(gè)制勝的策略(如果該策略存在)。如果桌上有小于4根的火柴，先手必勝，如果是5根，先手必輸；依次類(lèi)推，同理15、20、25勝。15、20、25.都是必輸狀態(tài)；所有每次把對(duì)手逼到15、20、25.等必輸狀態(tài)，就可以獲9.競(jìng)賽樹(shù)是一棵完全二叉樹(shù)，它反映了一系列“淘汰賽”的結(jié)果：葉子代表參加比賽 的n個(gè)選手，每個(gè)內(nèi)部結(jié)點(diǎn)代表由該結(jié)點(diǎn)的孩子結(jié)點(diǎn)所代表的選手中的勝者，顯然，樹(shù)的 根結(jié)點(diǎn)就代表了淘汰賽的冠軍。請(qǐng)回答下列問(wèn)題：(1) 這一系列的淘汰賽中比賽的總場(chǎng)數(shù)是多少(2) 設(shè)計(jì)一個(gè)高效的算法，它能夠利用比賽中產(chǎn)生的信息確定亞軍(1) 因?yàn)閚人進(jìn)行淘汰賽，要淘汰n-

23、1人，所有要進(jìn)行 n-1場(chǎng)比賽。(2)10.在120枚外觀相同的硬幣中，有一枚是假幣，并且已知假幣與真幣的重量不同, 但不知道假幣與真幣相比較輕還是較重?？梢酝ㄟ^(guò)一架天平來(lái)任意比較兩組硬幣，最壞情 況下，能不能只比較 5次就檢測(cè)出這枚假幣 將120枚平均分為三組，記為： A, B, C;先將A,B比較，如果A,B重量不同(假如 B比A 重)，再將B與C比較，如果B, C相同，則A有假幣；如果B,C不同，再將A,C比較，如果 A,C相同，則B有假幣；如果 A,C不同，貝y B有假幣；如果 A,B相同，則C有假幣；習(xí)題61.動(dòng)態(tài)規(guī)劃法為什么都需要填表如何設(shè)計(jì)表格的結(jié)構(gòu)在填寫(xiě)表格過(guò)程中，不僅可以使問(wèn)

24、題更加清晰，更重要的是可以確定問(wèn)題的存儲(chǔ)結(jié)構(gòu); 設(shè)計(jì)表格，以自底向上的方式計(jì)算各個(gè)子問(wèn)題的解并填表。2.對(duì)于圖所示多段圖，用動(dòng)態(tài)規(guī)劃法求從頂點(diǎn) 程。0到頂點(diǎn)12的最短路徑，寫(xiě)出求解過(guò)3734585966圖4第2題圖|1368將該多段圖分為四段；首先求解初始子問(wèn)題，可直接獲得：d(0, 1)= C01= 5(0 71)d(0, 2)= C02= 3(0 71)再求解下一個(gè)階段的子問(wèn)題，有： d(0,3)=d(0, 1)+ C13 =6(1 7 3)d(0,4)=mi nd(0,1)+c 14 ,d(0,2)+00000000 (以此類(lèi)推)最短路徑為：07 17 37 87 11 7 12c 24=8(1 7 4)3. 用動(dòng)態(tài)規(guī)劃法求如下0/1背包問(wèn)題的最優(yōu)解：有5個(gè)物品，其重量分別為(3, 2, 1,4,5)，價(jià)值分別為(25, 20, 15, 40, 50)，背包容量為6。寫(xiě)出求解過(guò)程。(x1, x2,x3,x4,x