算法設(shè)計(jì)與分析-homework

1、一、已知下列遞推式：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 f(n) = 2C( n / 2) + n 2 若n=1 = 2f(n / 2) + n 若n= 2帶入定理1：a = 2, d = 0, c = 2, b = 1

2、, x = 1,因?yàn)閍=cx所以f(n) = nlog2n所以C(n) = f(n) + 1 = nlog2n + 1C(n)的漸進(jìn)復(fù)雜度為O（nlog2n）二、由于Prim算法和Kruskal 算法設(shè)計(jì)思路的不同，導(dǎo)致了其對(duì)不同問題實(shí)例的效率對(duì)比關(guān)系的不同。請(qǐng)簡要論述：1、如何將兩種算法集成，以適應(yīng)問題的不同實(shí)例輸入；2、你如何評(píng)價(jià)這一集成的意義？解：Prime的時(shí)間復(fù)雜度為O(n2) （其中n 為頂點(diǎn)數(shù)）， Kruskal 算法的時(shí)間復(fù)雜度為 O(eln(e) （其中e為邊數(shù)），因此對(duì)于頂點(diǎn)少的輸入，適合Prime算法，對(duì)于邊比較少的輸入，適合Kruskal 算法。評(píng)價(jià)算法的優(yōu)劣需要根據(jù)輸

3、入數(shù)據(jù)的特點(diǎn)。對(duì)于不同特征的輸入最適用的算法可能不同。三、分析以下生成排列算法的正確性和時(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í)，i=1時(shí)，HeapPermute(2)輸出A1A2的全排列，并將A變?yōu)锳2A1A3，并交換1,3位，得A3A1A2i=2時(shí)

4、，HeapPermute(2)輸出A3A1的全排列，并將A變?yōu)锳1A3A2，交換1,3位，得A2A3A1i=3時(shí)，HeapPermute(2)輸出A2A3的全排列，并將A變?yōu)锳3A2A1，交換1,3位，得A1A2A3算法運(yùn)行結(jié)束后，A的元素順序不變。n=4時(shí)，i=1時(shí)，HeapPermute(3)輸出A1A2A3的全排列，并且A1A2A3順序不變，交換1,4位，得A4A2A3A1i=2時(shí)，HeapPermute(3)輸出A4A2A3的全排列，并且A4A2A3順序不變，交換2,4位，得A4A1A3A2i=3時(shí)，HeapPermute(3)輸出A4A1A3的全排列，并且A4A1A3順序不變，交換3

5、,4位，得A4A1A2A3i=4時(shí)，HeapPermute(3)輸出A4A1A2的全排列，并且A4A1A2順序不變，交換4,4位，得A4A1A2A3算法運(yùn)行結(jié)束后，數(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的位置

6、，所以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ù)雜度：由算法流程得：F(n) = 1 n=1= n * (F(n - 1) + 2) n1= n * (n - 1) * (F(n - 2) + 2) + 2) = n(n - 1) * F(n-2) + 2n2= n! + 2 * nn-1因此時(shí)間復(fù)雜度為O(n!) + O(n

7、n-1)四、對(duì)于求n 個(gè)實(shí)數(shù)構(gòu)成的數(shù)組中最小元素的位置問題，寫出你設(shè)計(jì)的具有減治思想算法的偽代碼，確定其時(shí)間效率，并與該問題的蠻力算法相比較。Min(A1.n, n, &loc)If(n = 1)Return A1Elseloc1, loc2Min1 = Min(A1.n/2, n/2, &loc1)Min2 = Min(An/2 + 1. n, n/2, &loc2)If(Min1 1= 2(2F(n/4) + 1) + 1 = 4F(n/4) + 2 + 1= 2kF(2k/2k) + 1 + 2 + + 2k-1 ( n=2k)= 2n 1復(fù)雜度為O（n），蠻力法也為O（n）五、請(qǐng)給出約瑟夫斯問題的非遞推公式 J（n），并證明之。其中，n 為最初總?cè)藬?shù)，J(n) 為最后幸存者的最初編號(hào)。 解：非遞推公式為：設(shè)J(n) = 2*b+1，其中n = 2m + b (0b1時(shí)，分兩種情況討論：當(dāng)n=2k，即為偶數(shù)時(shí)，假設(shè)k = n/2時(shí)成立，即k = 2m + b，則J(k) = 2b+1，由n=2k得n = 2m+1 + 2bJ(n) = J(2k) = 2J(k) 1 = 2(2b+1) 1 = 4b + 1 = 2(2b) + 1，對(duì)n成立當(dāng)n=2k+1，即為奇數(shù)時(shí)，假設(shè)k = (n-