北航計算機研究生課程-算法設計與分析-HomeWork-1

1、一、已知以下遞推式：Cn=1如n=1=2C（n/2）+n1如n2請由定理1導出Cn的非遞歸表達式并指出其漸進復雜性；k定理1：設a,c為非負整數(shù)，b,d,x為非負常數(shù)，并對于某個非負整數(shù)k,令n=c,就以下遞推式fn=d如n=1=afn/c+bnx如n>=2|精.|品.|可.|編.|輯.|學.|習.的解是fn=bncxlogn+dnbcxxcloga如a=cxbcxxx|資.|料.*|*|*|fn=dacxnacxn如ac*|歡.|迎.|下.|載.解：令Fn=Cn1就Fn=0n=1Fn=2Cn/2+n2n>=2=2Fn/2+1+n2=2Fn/2+n利用定理1，其中：d=0,a=2,

2、c=2,b=1,x=1,并且a=cx所以Fn=nlog2n所以Cn=Fn+1=nlog2n+1Cn的漸進復雜性是Onlog2n二、由于Prim算法和Kruskal算法設計思路的不同，導致了其對不同問題實例的效率對比關系的不同；請簡要論述：1、如何將兩種算法集成，以適應問題的不同實例輸入；2、你如何評判這一集成的意義？答：1、Prim算法基于頂點進行搜尋，所以適合頂點少邊多的情形；Kruskal從邊集合中進行搜尋，所以適合邊少的情形；依據(jù)輸入的圖中的頂點和邊的情形，邊少的選用kruskal算法，頂點少的選用prim算法2、沒有一個算法是萬能的，沒有一個算法是對全部情形都適合的；這一集成表達了針對

3、詳細問題選用最適合的方法，即詳細問題詳細分析的哲學思想；三、分析以下生成排列算法的正確性和時間效率：HeapPermuten/實現(xiàn)生成排列的Heap算法第1頁，共4頁|精.|品.|可.|編.|輯.|學.|習.|資.|料.*|*|*|*|歡.|迎.|下.|載./輸入：一個正正整數(shù)n和一個全局數(shù)組A1.n/輸出：A中元素的全排列ifn=1writeAelsefori1tondoHeapPermuten-1ifnisoddswapA1andAnelseswapAiandAn解：n=1時，輸出a1n=2時，輸出a1a2，a2a1n=3時，(1) 第一次循環(huán)i=1時，HeapPermute2將a1a2做

4、完全排列輸出，記為a1a2a3，并將A變?yōu)閍2a1a3，并交換1,3位，得a3a1a2(2) 其次次循環(huán)i=2時，HeapPermute2輸出a3a1a2，并將A變?yōu)閍1a3a2，交換1,3位，得a2a3a1(3) 第三次循環(huán)i=3時，HeapPermute2輸出a2a3a1，并將A變?yōu)閍3a2a1，交換1,3位，得a1a2a3，即全部輸出完畢后數(shù)組A回到初始次序；n=4時，(1) i=1時，HeapPermute3輸出a1a2a3a4，并且a1a2a3次序不變，交換1,4位，得a4a2a3a1(2) i=2時，HeapPermute3輸出a4a2a3a1，并且a4a2a3次序不變，交換2,4

5、位，得a4a1a3a2(3) i=3時，HeapPermute3輸出a4a1a3a2，并且a4a1a3次序不變，交換3,4位，得a4a1a2a3(4) i=4時，HeapPermute3輸出a4a1a2a3，并且a4a1a2次序不變，交換4,4位，得a4a1a2a3，即全部輸出完畢后數(shù)組A循環(huán)右移一位；由以上分析可得出結論：當n為偶數(shù)時，HeapPermuten輸出全排列后數(shù)組元素循環(huán)右移一位；當n為奇數(shù)時，HeapPermuten輸出全排列后數(shù)組元素次序保持不變；所以由歸納法證明如下：(1) i=1時，明顯成立；(2) i=k為偶數(shù)時，假設輸出的是全排列，就i=k+1奇數(shù)時，k+1次循環(huán)中，

6、每次前k個元素做全排列輸出后循環(huán)右移一位，所以對換swapA1andAn可以保證每次將前k個元素中的一個換到k+1的位置，所以k+1次循環(huán)后輸出的是A1k+1的全排列；(3) i=k為奇數(shù)時，假設輸出的是全排列,就i=k+1偶數(shù)時，k+1次循環(huán)中，每次前k個元素做全排列輸出后次序保持不變，所以對換swapAiandAn可以保證每次將前k個元素中的一個換到k+1的位置，所以k+1次循環(huán)后輸出的是A1k+1的全排列；證畢；第2頁，共4頁時間復雜度遞推公式為Tn=1n=1=nTn-1+2n>1化簡得Tn=n.+Onn-1所以時間復雜度為On.+Onn-1|精.|品.|可.|編.|輯.|學.|習

7、.|資.|料.*|*|*|*|歡.|迎.|下.|載.四、對于求n個實數(shù)構成的數(shù)組中最小元素的位置問題，寫出你設計的具有減治思想算法的偽代碼，確定其時間效率，并與該問題的蠻力算法相比較；解：(1) 算法思想：將n分為n/2，n-n/2表示向下取整兩部分，分別找出其中的最小元及其位置，比較這兩個元素的大小，得出總的最小元素的位置；(2) 偽代碼：x,i=FindLeastElementa,b/從數(shù)組Aab中找出最小元x，及其位置i/輸入：全局實數(shù)數(shù)組A1n，搜尋起始位置a,終止位置b/輸出：最小元素x及其位置iifa=breturn（Aa,a）elsex1,i=FindLeastElement1,

8、n/2;x2,j=FindLeastElementn/2+1,n;ifx1<x2returnx1,ielsereturnx2,j(3) 算法復雜度遞推公式：Fn=1n=1=2Fn/2n>1化簡：Fn=2Fn/2+1=22Fn/22+1+1=22Fn/22+2+1=2kF2k/2k+1+2+2k-1n=2k=2n-1所以復雜度為O2n-1蠻力法的復雜度為On，所以此方法仍沒有蠻力法效率高，由于減治后會增加比較次數(shù)；五、請給出約瑟夫斯問題的非遞推公式J（n），并證明之；其中，n為最初總人數(shù)，Jn為最終幸存者的最初編號；第3頁，共4頁|精.|品.|可.|編.|輯.|學.|習.|資.|料.*|*|*|*|歡.|迎.|下.|載.解：已知幸存者號碼的遞推公式：J1=1;J2k=2Jk1;n=2kJ2k+1=2Jk+1;n=2k+1幸存者號碼非遞推公式：設n=2m+b，Jn=2*b+10<=b<2m，m>=0證明數(shù)學歸納法：1i=1時，m=0，b=0，J1=2*b+1=1，成立；2i>1時，當i為偶數(shù)時，設k=i/2時成立，即k=2m+b，就Jk=2b+1，此時，i=2k=2m+1+2bJi=J2k=