北航計(jì)算機(jī)研究生課程-算法設(shè)計(jì)與分析-HomeWork-1.doc

一、已知下列遞推式：C(n) = 1若n =1= 2C（n/2） + n 1 若n 2請(qǐng)由定理1 導(dǎo)出C(n)的非遞歸表達(dá)式并指出其漸進(jìn)復(fù)雜性。定理1：設(shè)a,c為非負(fù)整數(shù)，b,d,x為非負(fù)常數(shù)，并對(duì)于某個(gè)非負(fù)整數(shù)k, 令n=ck, 則以下遞推式f(n)=d若 n=1=af(n/c)+bnx若 n=2的解是f(n)= bnxlogcn + dnx若 a=cxf(n)= 若 acx解：令F(n) = C(n) 1則 F(n) = 0 n=1 F(n) = 2C(n/2) + n 2 n=2 = 2F(n/2) + 1 + n 2 = 2F(n/2) + n利用定理1，其中：d=0,a=2,c=2,b=1,x=1,并且a=cx所以 F(n) = nlog2n所以 C(n) = F(n) + 1 = nlog2n + 1C(n)的漸進(jìn)復(fù)雜性是O(nlog2n) 二、由于Prim算法和Kruskal 算法設(shè)計(jì)思路的不同，導(dǎo)致了其對(duì)不同問(wèn)題實(shí)例的效率對(duì)比關(guān)系的不同。請(qǐng)簡(jiǎn)要論述：1、如何將兩種算法集成，以適應(yīng)問(wèn)題的不同實(shí)例輸入；2、你如何評(píng)價(jià)這一集成的意義？答： 1、Prim算法基于頂點(diǎn)進(jìn)行搜索，所以適合頂點(diǎn)少邊多的情況。Kruskal從邊集合中進(jìn)行搜索，所以適合邊少的情況。根據(jù)輸入的圖中的頂點(diǎn)和邊的情況，邊少的選用kruskal算法，頂點(diǎn)少的選用prim算法2、沒有一個(gè)算法是萬(wàn)能的，沒有一個(gè)算法是對(duì)所有情況都適合的。這一集成體現(xiàn)了針對(duì)具體問(wèn)題選用最適合的方法，即具體問(wèn)題具體分析的哲學(xué)思想。三、分析以下生成排列算法的正確性和時(shí)間效率：HeapPermute(n)/實(shí)現(xiàn)生成排列的Heap算法/輸入：一個(gè)正正整數(shù)n和一個(gè)全局?jǐn)?shù)組A1.n/輸出：A中元素的全排列if n = 1write Aelsefor i 1 to n doHeapPermute(n-1)if n is oddswap A1and Anelse swap Aiand An解：n=1時(shí)，輸出a1n=2時(shí)，輸出a1a2，a2a1n=3時(shí)，(1) 第一次循環(huán)i=1時(shí)，HeapPermute(2)將a1a2做完全排列輸出，記為a1a2a3，并將A變?yōu)閍2a1a3，并交換1,3位，得a3a1a2(2) 第二次循環(huán)i=2時(shí)，HeapPermute(2)輸出a3a1a2，并將A變?yōu)閍1a3a2，交換1,3位，得a2a3a1(3) 第三次循環(huán)i=3時(shí)，HeapPermute(2)輸出a2a3a1，并將A變?yōu)閍3a2a1，交換1,3位，得a1a2a3，即全部輸出完畢后數(shù)組A回到初始順序。n=4時(shí)，(1) i=1時(shí)，HeapPermute(3)輸出a1a2a3a4，并且a1a2a3順序不變，交換1,4位，得a4a2a3a1(2) i=2時(shí)，HeapPermute(3)輸出a4a2a3a1，并且a4a2a3順序不變，交換2,4位，得a4a1a3a2(3) i=3時(shí)，HeapPermute(3)輸出a4a1a3a2，并且a4a1a3順序不變，交換3,4位，得a4a1a2a3(4) i=4時(shí)，HeapPermute(3)輸出a4a1a2a3，并且a4a1a2順序不變，交換4,4位，得a4a1a2a3，即全部輸出完畢后數(shù)組A循環(huán)右移一位。由以上分析可得出結(jié)論：當(dāng)n為偶數(shù)時(shí)，HeapPermute(n)輸出全排列后數(shù)組元素循環(huán)右移一位。當(dāng)n為奇數(shù)時(shí)，HeapPermute(n)輸出全排列后數(shù)組元素順序保持不變。所以由歸納法證明如下：(1)i=1時(shí)，顯然成立。(2)i=k為偶數(shù)時(shí)，假設(shè)輸出的是全排列，則i=k+1(奇數(shù))時(shí)，k+1次循環(huán)中，每次前k個(gè)元素做全排列輸出后循環(huán)右移一位，所以對(duì)換swap A1and An可以保證每次將前k個(gè)元素中的一個(gè)換到k+1的位置，所以k+1次循環(huán)后輸出的是A1k+1的全排列。(3)i=k為奇數(shù)時(shí)，假設(shè)輸出的是全排列,則i=k+1(偶數(shù))時(shí)，k+1次循環(huán)中，每次前k個(gè)元素做全排列輸出后順序保持不變，所以對(duì)換swap Aiand An可以保證每次將前k個(gè)元素中的一個(gè)換到k+1的位置，所以k+1次循環(huán)后輸出的是A1k+1的全排列。證畢。時(shí)間復(fù)雜度遞推公式為T(n) = 1 n=1= n T(n-1)+2 n1化簡(jiǎn)得T(n) = n! + O(nn-1)所以時(shí)間復(fù)雜度為O(n!) + O(nn-1)四、對(duì)于求n 個(gè)實(shí)數(shù)構(gòu)成的數(shù)組中最小元素的位置問(wèn)題，寫出你設(shè)計(jì)的具有減治思想算法的偽代碼，確定其時(shí)間效率，并與該問(wèn)題的蠻力算法相比較。解：(1)算法思想：將n分為n/2，n-n/2(表示向下取整)兩部分，分別找出其中的最小元及其位置，比較這兩個(gè)元素的大小，得出總的最小元素的位置。(2)偽代碼：(x,i) = FindLeastElement(a,b)/從數(shù)組Aab中找出最小元x，及其位置i/輸入：全局實(shí)數(shù)數(shù)組A1n，搜索起始位置a,結(jié)束位置b/輸出：最小元素x及其位置iif a=breturn （Aa,a）else(x1,i) = FindLeastElement(1,n/2);(x2,j) = FindLeastElement(n/2+1,n);if x11化簡(jiǎn)：F(n) = 2F(n/2) + 1 = 22F(n/22)+1 + 1 = 22F(n/22) + 2 + 1 = 2kF(2k/2k) + 1 + 2 + + 2k-1 ( n=2k)= 2n-1所以復(fù)雜度為O(2n-1)蠻力法的復(fù)雜度為O(n)，所以此方法還沒有蠻力法效率高，因?yàn)闇p治后會(huì)增加比較次數(shù)。五、請(qǐng)給出約瑟夫斯問(wèn)題的非遞推公式 J（n），并證明之。其中，n 為最初總?cè)藬?shù)，J(n) 為最后幸存者的最初編號(hào)。解：已知幸存者號(hào)碼的遞推公式：J(1) = 1; J(2k) = 2J(k) 1; n=2k J(2k+1) = 2J(k) + 1; n=2k+1幸存者號(hào)碼非遞推公式：設(shè)n = 2m + b，J(n) = 2*b+1 (0=b=0)證明(數(shù)學(xué)歸納法)：(1) i=1時(shí)，m=0，b=0，J(1)=2*b+1=1，成立。(2) i1時(shí)，當(dāng)i為偶數(shù)時(shí)，設(shè)k = i/2時(shí)成立，即k = 2m + b，則J(k) = 2b+1，此時(shí)，i = 2k = 2m+1 + 2bJ(i) = J(2k) = 2J(k) 1 = 2(2b+1) 1 = 4b + 1 = 2(2b) + 1，即k=i時(shí)成立。當(dāng)i為