算法設(shè)計與分析王紅梅胡明習題答案

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

2、幾里德算法中（即最初的歐幾里德算法）用的不是除法而是減法。請用偽代碼描述這個版本的歐幾里德算法=m-n2.循環(huán)直到r=0m=nn=rr=m-n3輸出m3.設(shè)計算法求數(shù)組中相差最小的兩個元素（稱為最接近數(shù)）的差。要求分別給出偽代 碼和C+苗述。編寫程序，求n至少為多大時，n個“1”組成的整數(shù)能被 2013整除。#include<iostream>using namespace std;int main（）double value=0;for(int n=1;n<=10000 ;+n) (value=value*10+1;if(value%2013=0) (cout<<

3、;"n 至少為:"<<n<<endl; break;計算汽值的問題能精確求解嗎？編寫程序，求解滿足給定精度要求的汽值#include <iostream> using namespace std;int main () ( double a,b;double arctan(double x);圣經(jīng)上說：神 6天創(chuàng)造天地萬有，第 7日安歇。為什么是 6 天呢？任何一個自然數(shù)的因數(shù)中都有1和它本身，所有小于它本身的因數(shù)稱為這個數(shù)的真因數(shù)，如果一個自然數(shù)的真因數(shù)之和等于它本身，這個自然數(shù)稱為完美數(shù)。例如，6=1+2+3,因此6是完美數(shù)。神6天創(chuàng)

4、造世界，暗示著該創(chuàng)造是完美的。設(shè)計算法，判斷給定的自然 數(shù)是否是完美數(shù)#include<iostream> using namespace std;int main() (int value, k=1;cin>>value;for (int i = 2;i!=value;+i)(while (value % i = 0 )(k+=i; 有4個人打算過橋，這個橋每次最多只能有兩個人同時通過。他們都 在橋的某一端，并且是在晚上，過橋需要一只手電筒，而他們只有一只手電筒。這就意味 著兩個人過橋后必須有一個人將手電筒帶回來。每個人走路的速度是不同的：甲過橋要用1分鐘，乙過橋要用

5、 2分鐘，丙過橋要用 5分鐘，丁過橋要用10分鐘，顯然，兩個人走路的 速度等于其中較慢那個人的速度，問題是他們?nèi)窟^橋最少要用多長時間？由于甲過橋時間最短，那么每次傳遞手電的工作應(yīng)有甲完成甲每次分別帶著乙丙丁過橋例如：第一趟：甲，乙過橋且甲回來第二趟：甲，丙過橋且甲回來第一趟：甲，丁過橋一共用時19小時9.歐幾里德游戲：開始的時候，白板上有兩個不相等的正整數(shù)，兩個玩家交替行動， 每次行動時，當前玩家都必須在白板上寫出任意兩個已經(jīng)出現(xiàn)在板上的數(shù)字的差，而且這 個數(shù)字必須是新的，也就是說，和白板上的任何一個已有的數(shù)字都不相同，當一方再也寫 不出新數(shù)字時，他就輸了。請問，你是選擇先行動還是后行動？為

6、什么？設(shè)最初兩個數(shù)較大的為a,較小的為b,兩個數(shù)的最大公約數(shù)為factor。則最終能出現(xiàn)的數(shù)包括 ：factor, factor*2, factor*3, ., factor*(a/factor)=a.一共a/factor 個。如果a/factor是奇數(shù)，就選擇先行動；否則就后行動。習題21.如果 Ti(n)=Qf ( n) , T2(n)=Qg(n),解答下列問題：(1)證明加法定理：Ti( n) +Ta(n)=max C(f ( n), C(g( n)；(2)證明乘法定理：Ti(n) XT2(n)=Qf ( n) xQg(n);(3)舉例說明在什么情況下應(yīng)用加法定理和乘法定理。(3)比如在

7、for (f(n)for(g(n)中應(yīng)該用乘法定理如果在“講兩個數(shù)組合并成一個數(shù)組時”，應(yīng)當用加法定理2.考慮下面的算法，回答下列問題：算法完成什么功能？算法的基本語句是什么？基本語句執(zhí)行了多少次？算法的時間復雜性是多少?(1) int Stery(int n)int S = 0;for (int i = 1; i <= n;i+)(1) 胎解掙是* i1-n的平方和基索UrnS; s+=i*i ,執(zhí)行了 n次時間復雜度C (n)(2) int Q(int n) if (n = 1)return 1;elsereturn Q(n-1) + 2 * n - 1; (2)(2)完成的是n的平

8、方基本語句：return Q(n-1) + 2 * n 時間復雜度O (n)3.分析以下程序段中基本語句的執(zhí)行次數(shù)是多少，要求列出計算公式。(1) for (i = 1; i <= 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+)j+)(1) 基本語句2*i<n執(zhí)行了 n/2次基本語句y = y + i * j 執(zhí)行了 2/n次一共執(zhí)行次數(shù)=n/2+n/2=O (n)(2) 基本語句 m+=1 執(zhí)行了(n/2)*

9、n=O(n*n)4.使用擴展遞歸技術(shù)求解下列遞推關(guān)系式： T(n)4 n 13T (n 1) n 1 T(n)1n 12T(n 3) n n 1(1) int T(int n)if(n=1)return 4;else if(n>1)return 3*T(n-1);(2)int T(int n)if(n=1)return 1;else if(n>1)return 2*T(n/3)+n;5.求下列問題的平凡下界，并指出其下界是否緊密。(1)求數(shù)組中的最大元素；(2)判斷鄰接矩陣表示的無向圖是不是完全圖；(3)確定數(shù)組中的元素是否都是惟一的；(4)生成一個具有n個元素集合的所有子集(1)

10、 Q(n) 緊密?(2) Q (n*n)Q (logn+n)(先進行快排，然后進行比較查找)Q(2An)7.畫出在三個數(shù)a, b, c中求中值問題的判定樹。8.國際象棋是很久以前由一個印度人Shashi發(fā)明的，當他把該發(fā)明獻給國王時，國王很高興，就許諾可以給這個發(fā)明人任何他想要的獎賞。Shashi要求以這種方式給他一些糧食：棋盤的第1個方格內(nèi)只放1粒麥粒，第2格2粒，第3格4粒，第4格8粒， 以此類推，直到64個方格全部放滿。這個獎賞的最終結(jié)果會是什么樣呢？#include<iostream> using namespace std;int main()(long double r

11、esult=1;double j=1;for(int i=1;i<=64;+i)(j=j*2;result+=j;j+;)cout<<result<<endl;return 0;習題36/8化簡為3/4 。1.假設(shè)在文本"ababcabccabccacbab"中查找模式"abccac",寫出分別采用 BF算法和 KMP 算法的串匹配過式化簡。設(shè)計算法，將一個給定的真分數(shù)化簡為最簡分數(shù)形式。例如，將#include<iostream>using namespace std;int main（）int n;數(shù)字游戲。

12、把數(shù)字1,2,9這9個數(shù)字填入以下含有加、減、乘、除的四則運算式中，使得該等式成立。要求9個數(shù)字均出現(xiàn)一次且僅出現(xiàn)一次，且數(shù)字 1不能出現(xiàn)在乘和除的一位數(shù)中（即排除運算式中一位數(shù)為1的平凡情形）。x += 05.設(shè)計算法求解 an mod m其中a、n和m均為大于1的整數(shù)。（提示：為了避免 an超出int型的表示范圍，應(yīng)該每做一次乘法之后對n取模）#include<iostream> using namespace std;int square(int x)return x*x;設(shè)計算法，在數(shù)組 r n中刪除所有元素值為 x的元素，要求時間復雜性為O(n),空間復雜性為0(1)。7

13、.設(shè)計算法，在數(shù)組 rn中刪除重復的元素，要求移動元素的次數(shù)較少并使剩余元素 間的相對次序保持不變。#include <iostream>using namespace std;void deletere(int a,int N)int b100=0;int i,k;k=0;static int j=0;for(i=0;i<N;i+)bai+;for(i=0;i<100;i+)if(bi!=0)if(bi=2)k+;aj=i;j+;for(i=0;i<N-k;i+) cout<<ai<<endl;int main()int a尸1,2,1,

14、3,2,4;deletere(a,6);return 0;設(shè)表A=a1, a2,，an,將A拆成B和C兩個表，使 A中值大于等于0的元素存入表B,值小于0的元素存入表 G要求表B和C不另外設(shè)置存儲空間而利用表 A的空間。荷蘭國旗問題。要求重新排列一個由字符 R W B(R代表紅色，W代表白色，B代表 蘭色，這都是荷蘭國旗的顏色)構(gòu)成的數(shù)組，使得所有的R都排在最前面， W排在其次，B排在最后。為荷蘭國旗問題設(shè)計一個算法，其時間性能是Qn)。設(shè)最近對問題以k維空間的形式出現(xiàn)，k維空間的兩個點 pi=(xi, X2,，Xk)和p2=(yi, ky2,，yk)的歐幾里德距離定義為：d(p1P2)(yi

15、-x.)2。對k維空間的最近對問題設(shè).ii 11計蠻力算法，并分析其時間性能。11 .設(shè)計蠻力算法求解小規(guī)模的線性規(guī)劃問題。假設(shè)約束條件為：(1) x+yW4; (2)x+3yW6; (3) x>0且y>0;使目標函數(shù)3x+5y取得極大值。#include<iostream>using namespace std;int main()int x,y,x0,y0;int summax=0,temp=0;for(x0=0;x0<=4;+x0)for(y0=0;(x0+y0<=4)&&(x0+3*y0<=6);+y0)temp=3*x0+5*

16、y0;if(temp>=summax)summax=temp;x=x0;1.1.11.1.2 變位詞。給定兩個單詞，判斷這兩個單詞是否是變位詞。如果兩個單詞的字母完全相同，只是位置有所不同，則這兩個單詞稱為變位詞。例如，eat和tea是變位詞。分治法的時間性能與直接計算最小問題的時間、合并子問題解的時間以及子問題的個 數(shù)有關(guān)，試說明這幾個參數(shù)與分治法時間復雜性之間的關(guān)系。12 證明：如果分治法的合并可以在線性時間內(nèi)完成，則當子問題的規(guī)模之和小于原問題的規(guī)模時，算法的時間復雜性可達到Qn)。O(N)=2*O(N/2)+xO(N)+x=2*O(N/2)+2*xa*O(N)+x=a*(2*O(

17、N/2)+x)+x=2*a *O(N/2)+(a+1)*x由此可知，時間復雜度可達到O(n);13 分治策略一定導致遞歸嗎？如果是，請解釋原因。如果不是，給出一個不包含遞歸的分治例子，并闡述這種分治和包含遞歸的分治的主要不同。不一定導致遞歸。如非遞歸的二叉樹中序遍歷。這種分治方法與遞歸的二叉樹中序遍歷主要區(qū)別是：應(yīng)用了棧這個數(shù)據(jù)結(jié)構(gòu)。14 對于待排序序列(5, 3, 1,9)，分別畫出歸并排序和快速排序的遞歸運行軌跡。歸并排序：第一趟：(5,3) (1,9);第二趟：(3,5,1,9 );第三趟：(1,3,5,9 );快速排序：第一趟：5 ( ,3,1,9 );設(shè)計分治算法求一個數(shù)組中的最大元

18、素，并分析時 間性能。設(shè)計分治算法，實現(xiàn)將數(shù)組A n中所有元素循環(huán)左移k個位置，要求時間復雜性為Qn),空間復雜性為 C(1)。例如，對 abcdefgh循環(huán)左移3位得到defghabc。設(shè)計遞歸算法生成 n個元素的所有排列對象。#include <iostream>using namespace std;int data100;設(shè)計分治算法求解一維空間上n個點的最近對問題。參見4.4.1最近對問題的算法分析及算法實現(xiàn)15 在有序序列(r1,2,，rn)中，存在序號i (1 < i < n),使得c=i。請設(shè)計一個分 治算法找到這個元素，要求算法在最壞情況下的時間性能為

19、Qlog 2n)。在一個序列中出現(xiàn)次數(shù)最多的元素稱為眾數(shù)。請設(shè)計算法尋找眾數(shù)并分析算法的時間 復雜性。設(shè)M是一個nxn的整數(shù)矩陣，其中每一行（從左到右）和每一列（從上到下）的元素都按升序排列。設(shè)計分治算法確定一個給定的整數(shù)x是否在M中，并分析算法的時間復雜性。16 .設(shè)S是n （n為偶數(shù)）個不等的正整數(shù)的集合，要求將集合S劃分為子集S和使得| Si|=| S2|= n/2 ,且兩個子集元素之和的差達到最大。設(shè)ai,電，an是集合1,2,，n的一個排列，如果i <j且a>aj,則序偶（ai,句）稱為該排列的一個逆序。例如， 2, 3, 1有兩個逆序：（3,1）和（2,1）。設(shè)計算法統(tǒng)

20、計給定 排列中含有逆序的個數(shù)。循環(huán)賽日程安排問題。設(shè)有 n=2k個選手要進行網(wǎng)球循環(huán)賽，要求設(shè)計一個滿足以下要求 的比賽日程表：（1）每個選手必須與其他 n-1個選手各賽一次；（2）每個選手一天只能賽一次。采用分治方法。將2”選手分為2”-1兩組，采用遞歸方法，繼續(xù)進行分組，直到只剩下2個選手時，然后進行比賽，回溯就可以指定比賽日程表了15.格雷碼是一個長度為 2n的序列，序列中無相同元素，且每個元素都是長度為n的二進制位串，相鄰元素恰好只有 1位不同。例如長度為 23的格雷碼為（000, 001, 011, 010, 110, 111, 101, 100） 。設(shè)計分治算法對任意的 n值構(gòu)造相

21、應(yīng)的格雷碼。矩陣乘法。兩個 nxn的矩陣X和Y的乘積得到另外一個 nx n的矩陣Z,且Zj滿足（1<i , j <n）,這個公式給出了運行時間為O n3）的算法?？梢杂梅种畏ń鉀Q矩陣乘法問題，將矩陣X和Y都劃分成四個n/2 x n/2的子塊，從而 X和Y的乘積可以用這些子塊進行表達，即從而得到分治算法：先遞歸地計算8個規(guī)模為n/2的矩陣乘積 AE BG AF、BH CE DGCF DH然后再花費 Qn2）的時間完成加法運算即可。請設(shè)計分治算法實現(xiàn)矩陣乘法，并分 析時間性能。能否再改進這個分治算法？1 .下面這個折半查找算法正確嗎？如果正確，請給出算法的正確性證明，如果不正確，請 說

22、明產(chǎn)生錯誤的原因。int BinSearch(int r , int n, int k) (int low = 0, high = n - 1;int mid;while (low <= high)(mid = (low + high) / 2;if (k < rmid) high = mid;else if (k > rmid) low = mid;else return mid;return 0;錯誤。正確算法：int BinSearch1(int r , int n, int k)(int low = 0, high = n - 1;int mid;while (low

23、 <= high)(mid = (low + high) / 2;if (k < rmid) high =mid - 1 ;else if (k > rmid) low = mid + 1 ;else return mid;return 0;2 .請寫出折半查找的遞歸算法，并分析時間性能。求兩個正整數(shù)m和n的最小公倍數(shù)。(提示：m和n的最小公倍數(shù)lcm( mn)與m和n的最大公約數(shù) gcd(m n)之間有如下關(guān)系：lcm( m n)= mx n/gcd( m n)插入法調(diào)整堆。已知(k1 ,k2,，kn)是堆，設(shè)計算法將(k1 ,k2,，kn,kn+1)調(diào)整為堆(假設(shè)調(diào)整為大

24、根堆)。參照：void SiftHeap(int r , int k, int n)(int i, j, temp;1 = k; j = 2 * i + 1;設(shè)計算法實現(xiàn)在大根堆中刪除一個元素，要求算法的時間復雜性為Qog 2n)on m 5065 25 13013012 260 65203 1040 1040 1 2080 2080 3250一圖俄式乘法計算兩個正整數(shù)n和m的乘積有一個很有名的算法稱 為俄式乘法，其思想是利用了一個規(guī)模是n的解和一個規(guī)模是n/2的解之間的關(guān)系：nxm= n/2X2m(當n是偶數(shù)) 或：nXm= ( n-1)/2 x 2m m(當 n 是奇數(shù))，并以 1 x m

25、= m 作為算法結(jié)束的條件。例如，圖給出了利用俄式乘法計算 50X 65的例子。據(jù)說十九世紀的俄國農(nóng)夫使用該算法并因 此得名，這個算法也使得乘法的硬件實現(xiàn)速度非?？?，因 為只使用移位就可以完成二進制數(shù)的折半和加倍。請設(shè)計 算法實現(xiàn)俄式乘法。拿子游戲?？紤]下面這個游戲：桌子上有一堆火柴，游戲開始時共有n根火柴，兩個玩家輪流拿走1, 2, 3或4根火柴，拿走最后一根火柴的玩家為獲勝方。請為先走的玩家 設(shè)計一個制勝的策略(如果該策略存在)。如果桌上有小于4根的火柴，先手必勝，如果是5根，先手必輸；依次類推，同理15、20、25.都是必輸狀態(tài)；所有每次把對手逼到15、20、25.等必輸狀態(tài)，就可以獲勝

26、。9 .競賽樹是一棵完全二叉樹，它反映了一系列“淘汰賽”的結(jié)果：葉子代表參加比賽 的n個選手，每個內(nèi)部結(jié)點代表由該結(jié)點的孩子結(jié)點所代表的選手中的勝者，顯然，樹的 根結(jié)點就代表了淘汰賽的冠軍。請回答下列問題：(1)這一系列的淘汰賽中比賽的總場數(shù)是多少？(2)設(shè)計一個高效的算法，它能夠利用比賽中產(chǎn)生的信息確定亞軍。(1)因為n人進行淘汰賽，要淘汰 n-1人，所有要進行 n-1場比賽。10 .在120枚外觀相同的硬幣中，有一枚是假幣，并且已知假幣與真幣的重量不同， 但不知道假幣與真幣相比較輕還是較重?？梢酝ㄟ^一架天平來任意比較兩組硬幣，最壞情 況下，能不能只比較 5次就檢測出這枚假幣？將120枚平均

27、分為三組，記為： A, B, C;先將A,B比較，如果 A,B重量不同(假如 B比A 重)，再將B與C比較，如果B, C相同，則A有假幣；如果B,C不同，再將A,C比較，如果 A,C相同，則B有假幣；如果 A,C不同，則B有假幣；如果 A,B相同，則C有假幣；習題61.動態(tài)規(guī)劃法為什么都需要填表？如何設(shè)計表格的結(jié)構(gòu)?在填寫表格過程中，不僅可以使問題更加清晰，更重要的是可以確定問題的存儲結(jié)構(gòu); 設(shè)計表格，以自底向上的方式計算各個子問題的解并填表。2.對于圖所示多段圖，用動態(tài)規(guī)劃法求從頂點 程。0到頂點12的最短路徑，寫出求解過將該多段圖分為四段；首先求解初始子問題，可直接獲得：d(0, 1)= coi= 5(0 一 1)d(0, 2)= Co2=3(0 一 1)再求解下一個階段的子問題，有：d(0,3)= d(0, 1)+ C13 =6(1 - 3) d(0,4)=mind(0,1)+ c 14 ,d(0,2)+ oooooooo (以此類推)最短路徑為：0一 1一 3 一 8一11 一 12c 24=8（1 一 4）3.用動態(tài)規(guī)劃法求如下0/1背包問題的最優(yōu)解：有 5個物品，其重量分別為(3, 2, 1,4,5),價值分別為(25, 20, 15, 40, 50),背包容量為6。寫出求解過程。(x1, x2,x3,x4,x5) 一