算法部分作業(yè)答案

1、1.1算法：是對特定問題求解步驟的一種描述，是指令的有限序列。 程序：當(dāng)一個(gè)算法用某種程序設(shè)計(jì)語言來描述時(shí)，得到的就是程序，也就是說,程序是用某種程序設(shè)計(jì)語言對算法的具體實(shí)現(xiàn). 算法有輸入、輸出、確定性、能行性和有限性等特征，當(dāng)不具備有窮性時(shí)，只能叫做計(jì)算過程，而不能稱之為算法，算法可以終止，而程序沒有此限制。1.2程序證明和程序測試的目的各是什么？ 程序證明是確認(rèn)一個(gè)算法能正確無誤的工作. 程序測試的目的是發(fā)現(xiàn)錯(cuò)誤1-9 解: n!的遞歸定義： 求解n!的遞歸函數(shù)long Factorial (long n) if(n<0) cout<<”error!”;exit(0);i

2、f(n=0) return 1; else return n *Factorial (n-1);1-10 使用歸納法，證明上題所設(shè)計(jì)的計(jì)算n！的遞歸函數(shù)的正確性 證明(歸納法證明)： (1)首先，如果n=0，那么程序執(zhí)行if(n=0) return 1;返回1,算法顯然正確;(2)假定函數(shù)Factorial對n<k(>1)能正確運(yùn)行，那么，當(dāng)n=k時(shí)，算法必定執(zhí)行:else return k *Factorial (k-1);因?yàn)镕actorial (k-1)正確，所以，當(dāng)n=k時(shí)，程序運(yùn)行正確綜合以上兩點(diǎn)，可得程序正確.證畢.2-1, 簡述衡量一個(gè)算法的主要性能標(biāo)準(zhǔn),說明算法的正

3、確性與健壯性的關(guān)系 答: 衡量一個(gè)算法的主要性能指標(biāo)有:正確性，簡單性，高效低存儲(chǔ)，最優(yōu)性 算法的正確性與健壯性的關(guān)系:所謂算法的正確性:是指在合法的輸入下，算法應(yīng)實(shí)現(xiàn)預(yù)先規(guī)定的功能和計(jì)算精度要求;所謂算法的健壯性，是指當(dāng)輸入不合法時(shí)，算法應(yīng)該能按某種預(yù)定的方式做出適當(dāng)?shù)奶幚?正確的算法不一定的是健壯的，健壯的算法也不一定是完全正確的.正確性和健壯性是相互補(bǔ)充的.一個(gè)可靠的算法，要求能在正常情況下正確的工作，而在異常情況下，亦能做出適當(dāng)處理.2-9(1)設(shè)計(jì)一個(gè)C/C+程序，實(shí)現(xiàn)一個(gè)n*m的矩陣轉(zhuǎn)置，原矩陣與其轉(zhuǎn)置矩陣保存在二維數(shù)組中.Void reverse(int *a,int *b,in

4、t n,int m) For(int i=0;i<n;i+) For(int j=0;j<m;j+) bji=aij;(2)使用全局變量count,改寫矩陣轉(zhuǎn)置程序，并運(yùn)行修改后的程序以確定此程序所需的程序步 Void reverse(int *a,int *b,int n,int m,int &count) int i=0;count+;int j=0;count+; For(;i<n;i+) For(;j<m;j+) count+; bji=aij;count+;2-10 試用定義證明下列等式的正確性(1) 5n2-8n+2=O(n2)證明: 因?yàn)楫?dāng)n0=1

5、,C=6時(shí),當(dāng)n>n0時(shí)，有5n2-8n+2<=6n22-16 使用遞推關(guān)系式計(jì)算求n!的遞歸函數(shù)的時(shí)間(即分析1-9題中的函數(shù)的時(shí)間復(fù)雜度),要求使用替換和迭代兩種方法分別計(jì)算之. 解: 分析1-9題中的函數(shù)的時(shí)間復(fù)雜度:用基本運(yùn)算乘法的運(yùn)算次數(shù)作為衡量時(shí)間復(fù)雜度的量當(dāng)n=0時(shí)，程序執(zhí)行if(n=0) return 1;,并沒有做乘法，故T(0)=0;當(dāng)n>=1時(shí)程序執(zhí)行n *Factorial (n-1);此時(shí)T(n)= T(n-1)+1故: 替換法: T(0)=0,T(1)=1,T(2)=2- 總結(jié)得到:T(n)=n;歸納法證明:(1),當(dāng)n=0時(shí),T(0)=0,結(jié)論成

6、立;(2)假設(shè)當(dāng)k<n時(shí)，有 T(k)=k,那么，當(dāng)k=n時(shí)，有T(n)=T(n-1)+1=(n-1)+1=n所以，對所有n>=0有T(n)=n;成立. 迭代法: T(n)=T(n-1)+1 =(T(n-2)+1)+1=(T(n-3)+1)+1)+1=.=T(0)+1+1.+1(n個(gè)1)=n2-19 利用遞歸樹計(jì)算遞推方程 假設(shè)n=2k,那么,總共有l(wèi)ogn+1(即k+1)層,非遞歸部分之和為n2+n2/21+n2/22+n2/2k=(1+1/2+1/22+1/23+1/2logn)n2 =2n2+2n=O(n2)5-8三分搜索算法的做法是:它先將待查元素X與n/3處的元素比較，然

7、后將X與2n/3處的元素比較,比較的結(jié)果或者找到X,或者將范圍縮小到原來的n/3int Search3(int a,int left,int right,int x) /*遞歸算法*/ int l,u; if(left<=right) l=left+(right-left)/3;u=left+(right-left)*2/3;if(x=au) return u;else if(x=al) return l; else if(x>au) return Search3(a, u+1, right,x); else if(x>al) return Search3(a, l+1, u

8、-1,x); else return Search3(a, left, l-1,x); return -1;void main()int n,*a; int x,i; cout<<"Please input n:"cin>>n;a=new intn; /動(dòng)態(tài)數(shù)組int location=-1; for(i=0;i<n;i+) ai=i+1; cout<<"Please input the search x:"cin>>x; cout<<endl<<Search3(a, 0, n

9、-1,x)<<endl;void main() /*非遞歸算法*/ int a15; int x,i; int location=-1; for(i=0;i<15;i+) ai=i+1; cin>>x; i=0;int j=14,l,u; while(i<=j) l=i+(j-i)/3;u=i+(j-i)*2/3;if(x=au) location=u;break;else if(x=al)location=l;break; else if(x>au) i=u+1; else if(x<al) j=l-1; else i=l+1; j=u-1;

10、cout<<location<<endl; /x的位置 5-12Void stoogesort(nt a,int left,int right) if(aleft>aright) swap(a,left,right);if(left+1>=right) return; int k=(right-left+1)/3;stoogesort(a,left,right-k);stoogesort(a,left+k,right);stoogesort(a,left,right-k);證明: 元素個(gè)數(shù)n=right-left+1; (1) 若為空表或只有一個(gè)元素(n=1

11、時(shí),即left+1=right)時(shí)，程序執(zhí)行if(aleft>aright) swap(a,left,right);之后，執(zhí)行if(left+1>=right) return;即此時(shí)程序做了一次元素之間的比較之后，不做任何操作，顯然正確.(2) 假設(shè)當(dāng)n< right-left+1(n>=2)時(shí)，算法正確，即對于所有元素個(gè)數(shù)小于n的元素集,算法能正確排序.那么,當(dāng)n= right-left+1時(shí)，算法執(zhí)行程序段:int k=(right-left+1)/3;stoogesort(a,left,right-k);stoogesort(a,left+k,right); st

12、oogesort(a,left,right-k);由假設(shè)可知:以上三條語句都能正確運(yùn)行，所以，當(dāng)n= right-left+1時(shí),算法正確. 由以上兩點(diǎn)可知，算法正確. 分析算法的時(shí)間復(fù)雜度: 排序算法，基本運(yùn)算仍然是元素之間的比較,所以，算法時(shí)間復(fù)雜度為: （用替換或迭代法計(jì)算之即可）6-1設(shè)有背包問題實(shí)例，n=7，(w0,w1,w2,w3,w4,w5,w6)=(2,3,5,7,1,4,1)，(p0,p1,p2,p3,p4,p5,p6)=( 10,5,15,7,6,18,3)，M=15。求這一實(shí)例的最優(yōu)解及最大收益.解:首先，選擇最優(yōu)量度標(biāo)準(zhǔn)為收益重量比;其次, 依據(jù)收益重量比的非增次序?qū)?/p>

13、入(物品)進(jìn)行排序 (p0/w0,p1/w1,p2/w2,p3/w3,p4/w4,p5/w5,p6/w6)=(5,5/3,3,1,6,4.5,3) 對物品排序結(jié)果為:4,0,5,2,6,1,3最后，進(jìn)行貪心選擇: X=(4) X=(4,0) X=(4,0,5) (剩余載重)U=14 U=12 U=8 (收益) P=6 P=6+10=16 P=16+18=34 X=(4,0,5,2) X=(4,0,5,2,6) X=(4,0,5,2,6,1(2/3) (剩余載重)U=3 U=2 U=0 (收益) P=34+15=49 P=49+3=52 P=52+2/3*5=55.33所以,最優(yōu)解為x=(1,2

14、/3,1,0,1,1,1); 即裝入第0,2,4,5,6物品和第1個(gè)物品的2/3 最大收益: P=55.336-2,0/1背包問題是一種特殊的背包問題，裝入背包的物品不能分割,只允許或者整個(gè)物品裝入背包，或者不裝入，即xi=0,或1,(0<=i<n),以題6-1的數(shù)據(jù)作為0/1背包的實(shí)例，按貪婪法求解，這樣求得的解一定是最優(yōu)解嗎?為什么?解:首先，選擇最優(yōu)量度標(biāo)準(zhǔn)為收益重量比;其次, 依據(jù)收益重量比的非增次序?qū)斎?物品)進(jìn)行排序 (p0/w0,p1/w1,p2/w2,p3/w3,p4/w4,p5/w5,p6/w6)=(5,5/3,3,1,6,4.5,3) 對物品排序結(jié)果為:4,0

15、,5,2,6,1,3最后，進(jìn)行貪心選擇: X=(4) X=(4,0) X=(4,0,5) (剩余載重)U=14 U=12 U=8 (收益) P=6 P=6+10=16 P=16+18=34 X=(4,0,5,2) X=(4,0,5,2,6) X=(4,0,5,2,6) (剩余載重)U=3 U=2 繼續(xù)考察第1和第3個(gè) (收益) P=34+15=49 P=49+3=52 物品,都不能裝入.所以,貪心法求得的0/1背包問題的最優(yōu)解為x=(1,0,1,0,1,1,1);即裝入第0,2,4,5,6物品 最大收益: P=52 但實(shí)際上，當(dāng)y=(1,1,1,0,1,1,0) 即裝入第0,1,2,4,5物品

16、,可獲收益為P=54,所以，貪心法求得的0/1背包問題的解x一定不是最優(yōu)解. 原因是: 對于0/1背包問題，貪心法并不能保證使其單位載重下的收益最大，因?yàn)橥ǔＴ诒嘲鼪]還裝滿時(shí)，卻再也裝不下任何物品，這樣，就使得單位載重下的物品收益減少,所以， 0/1背包問題通常不能用貪心法求解.6-3 設(shè)有帶時(shí)限的作業(yè)排序?qū)嵗齨=7，收益(p0, p1, p2, p3, p4, p5, p6)=(3,5,20,18,1,6,30)，作業(yè)的時(shí)限(d0, d1, d2, d3, d4, d5, d6)=(1,3,4,3,2,1,2),給出以此實(shí)例為輸入，執(zhí)行函數(shù)JS得到的用最優(yōu)解和最大收益。解:X=5,6,3,2

17、 最大收益為74函數(shù)JS如下:int JS(int *d, int *x, int n) /設(shè)p0p1pn-1int k=0; x0=0; for (int j=1; j<n; j+)/O(n)int r=k; while (r>=0 && dxr>dj && dxr>r+1)r-;/搜索作業(yè)j的插入位置if(r<0 | dxr<=dj) && dj>r+1)/若條件不滿足，選下一個(gè)作業(yè)for (int i=k; i>=r+1; i-) xi+1=xi;/將xr以后的作業(yè)后移xr+1=j; k+;/

18、將作業(yè)j插入r+1處return k; 在執(zhí)行JS函數(shù)之前，必須先對輸入(即作業(yè))按作業(yè)的收益非增次序排序，結(jié)果為: 6,2,3,5,1,0,4X: 接著執(zhí)行JS函數(shù): 最初, 解集合X為空.6X:0 1 2 3 4 5 6 首先, 考慮作業(yè)6, 假設(shè)將其加入集合X, 即x0=6;考慮X中的作業(yè)能否均如期完成,因?yàn)榇藭r(shí)X中只有作業(yè)6,其截止時(shí)限為2,故,能如期完成,此時(shí),將作業(yè)6加入作業(yè)子集X中,此時(shí)，子集X中的最大可用下標(biāo)k=0;X:6 0 1 2 3 4 5 6 k 接著，考慮作業(yè)2. 首先搜索作業(yè)2在X集合中的插入位置，使得X集合中的元素按作業(yè)的截止時(shí)限的非減次序排序,因?yàn)閐6=2,而d

19、2=4,所以，可將作業(yè)2插在作業(yè)6的后面，即x1=2,得到X=(6,2),X:620 1 2 3 4 5 6 k 考慮X中的作業(yè)能否均如期完成?因?yàn)閐6=2>=1, d2=4>=2,所以，X中作業(yè)均能如期完成，將作業(yè)2加入子集X中. 子集X中的最大可用下標(biāo)k=k+1=1X:620 1 2 3 4 5 6 k考慮作業(yè)3.首先搜索作業(yè)3在X集合中的插入位置，使得X集合中的元素按作業(yè)的截止時(shí)限的非減次序排序,因?yàn)閐6=2, d2=4,而d3=3所以，可將作業(yè)3插在作業(yè)6的后面,作業(yè)2的前面，得到X=(6,3,2),X:6320 1 2 3 4 5 6 k 考慮X中的作業(yè)能否均如期完成?因

20、為d6=2>=1, d3=3>=2, d2=4>=3所以，X中作業(yè)均能如期完成，將作業(yè)2加入子集X中. 子集X中的最大可用下標(biāo)k=k+1=2X:6320 1 2 3 4 5 6 k考慮作業(yè)5.首先搜索作業(yè)5在X集合中的插入位置，使得X集合中的元素按作業(yè)的截止時(shí)限的非減次序排序,因?yàn)閐6=2, d2=4, d3=3而d5=1所以，可將作業(yè)5插在作業(yè)6的前面,得到X=(5,6,3,2),X:56320 1 2 3 4 5 6 k 考慮X中的作業(yè)能否均如期完成?因?yàn)閐5=1>=1,d6=2>=2, d3=3>=3, d2=4>=4所以，X中作業(yè)均能如期完成，

21、將作業(yè)5加入子集X中. 子集X中的最大可用下標(biāo)k=k+1=3X:56320 1 2 3 4 5 6 k考慮作業(yè)1.首先搜索作業(yè)1在X集合中的插入位置，使得X集合中的元素按作業(yè)的截止時(shí)限的非減次序排序,因?yàn)閐5=1,d6=2, d3=3,d2=4,而d1=3所以，可將作業(yè)1插在作業(yè)2的前面,作業(yè)3的后面,得到X=(5,6,3,1,2),X:563120 1 2 3 4 5 6 k 考慮X中的作業(yè)能否均如期完成?因?yàn)閐5=1>=1,d6=2>=2, d3=3>=3, d1=3<4所以，X中1作業(yè)不能如期完成，所以，不能將作業(yè)1加入子集X. X:56320 1 2 3 4 5

22、 6 k 接著考慮作業(yè)0,4均不能加入子集X,故，執(zhí)行JS得到的最優(yōu)解為X=(5,6,3,2),最大收益為P=p5+p6+p3+p2=30+20+18+6=746-17,最佳裝載問題是將一批集裝箱裝上一艘載重為C的輪船，其中集裝箱i的重量為wi(0<=i<=n-1),最優(yōu)裝載問題是指在裝載體積不受限制的情況下,求使得裝箱數(shù)目最多的裝載方案.(1)按貪心策略的要求,給出關(guān)于上述最優(yōu)化問題的形式化描述.(2)給出貪心法求解這一問題的最優(yōu)量度標(biāo)準(zhǔn);(3)討論其最優(yōu)解的最優(yōu)子結(jié)構(gòu).(4)編寫裝箱問題的貪心算法;(5)設(shè)有重量為(4,6,3,5,7,2,9)的7個(gè)集裝箱，輪船載重為26,求最

23、優(yōu)解.解;(1),形式化描述如下：給定C>0, wi>0求X=()使得并且使最大 （2）以重量作為最優(yōu)量度標(biāo)準(zhǔn)，以重量最輕者先裝來選擇集裝箱裝上船（3）設(shè)(x0,x1,-xn-1)是最優(yōu)裝載問題的最優(yōu)解，則易知(x1,x2,-xn-1)是輪船載重為C-x0w0且待裝船的集裝箱為1，3-n-1時(shí)相應(yīng)最優(yōu)裝載問題的一個(gè)最優(yōu)解，即最優(yōu)裝載問題具有最優(yōu)子結(jié)構(gòu)特性。否則，假設(shè)(x1,x2,-xn-1)不是子問題的最優(yōu)解，假設(shè)有另一個(gè)解Z=(z1, z 2,- z n-1)是子問題的最優(yōu)解，則有：則：且，即(x0，z1, z 2,- z n-1)是最優(yōu)裝載問題的最優(yōu)解,與(x0,x1,-xn-

24、1)是最優(yōu)裝載問題的最優(yōu)解矛盾，所以, (x1,x2,-xn-1)是子問題的最優(yōu)解,故最優(yōu)裝載問題具有最優(yōu)子結(jié)構(gòu)特性。(4) 參考程序1 /*箱子信息結(jié)構(gòu)體*/struct goodinfofloat w; /*箱子重量*/int X; /*箱子存放的狀態(tài)*/int flag; /*箱子編號(hào)*/;/*按物品重量做升序排列*/void sort(goodinfo goods,int n)int j,i;for(j=2;j<=n;j+)goods0=goodsj;i=j-1;while (goods0.w<goodsi.w)goodsi+1=goodsi;i-;goodsi+1=goo

25、ds0;/*用貪心法對物品進(jìn)行選擇裝入*/void loading(goodinfo goods,float M,int n) float cu;int i,j;int A=0;/*對裝入箱子進(jìn)行計(jì)數(shù)*/for(i=1;i<=n;i+)/*賦初值*/goodsi.X=0;cu=M; /*船的剩余載重*/for(i=1;i<n;i+)if(goodsi.w>cu)/*當(dāng)該箱重量大于剩余載重跳出*/break;goodsi.X=1;A+;cu=cu-goodsi.w;/*確定船的剩余載重*/for(j=2;j<=n;j+)/*對箱子按序號(hào)大小作升序排列*/goods0=go

26、odsj;i=j-1;while (goods0.flag<goodsi.flag)goodsi+1=goodsi;i-;goodsi+1=goods0;cout<<" 最優(yōu)解為:"<<endl;/*輸出*/for(i=1;i<=n;i+)cout<<" 第"<<i<<"件物的存放狀態(tài):"cout<<goodsi.X<<endl;cout<<"<0：未裝入；1：裝入>"<<endl;c

27、out<<endl;cout<<" 最多能裝入的箱子數(shù)為:"cout<<A<<endl;(5) 首先，選擇最優(yōu)量度標(biāo)準(zhǔn)為重量;其次, 依據(jù)集裝箱重量的非減次序?qū)斎?物品)進(jìn)行排序 對集裝箱的排序結(jié)果為:5,2,0,3,1,4,6最后，進(jìn)行貪心選擇: X=(5) X=(5,2) X=(5,2,0) (剩余載重)U=24 U=21 U=17 X=(5,2,0,3) X=(5,2,0,3,1) X=(5,2,0,3,1) (剩余載重)U=12 U=6 所以，最優(yōu)解為X=(0,1,2,3, 5),最優(yōu)解值為5參考程序2 public

28、 static float loading(float c, float w, int x) int n=w.length; Element d = new Element n; for (int i = 0; i < n; i+) di = new Element(wi,i); MergeSort.mergeSort(d); float opt=0; for (int i = 0; i < n; i+) xi = 0; for (int i = 0; i < n && di.w <= c; i+) xdi.i = 1; opt+=di.w; c -=

29、di.w; return opt; 7-5設(shè)有4 個(gè)矩陣連乘積ABCD：A: 45*8, B: 8*40, C: 40*25, D: 25*10, ,請求出它們的最優(yōu)計(jì)算次序和計(jì)算量。解：p0=45，p1=8，p2=40，p3=25，p4=10 可只給出矩陣形式計(jì)算m矩陣為： m01= p0*p1* p2=45*8*40=14400;m12= p1*p2* p3=8*40*25=8000;m23= p2*p3* p4=40*25*10=11250; m02= m00+m12+p0*p1* p3=8000+45*8*25=8000+9000=17000= m01+m22+p0*p2* p3=14

30、400+45*40*25=14400+45000m13= m11+m23+p1*p2* p4=11250+8*40*10=11250+3200= m12+m33+p1*p3* p4=8000+8*25*10=10000m03= m00+m13+p0*p1* p4=10000+45*8*10=10000+3600=13600= m01+m23+p0*p2* p4=14400+11250+45*40*10=m02+m33+p0*p3* p4=17000+45*25*10=17000+11250=28250 0 0 0 0s= 1 1 22 23 0 14400 17000 13600m= 0 80

31、00 100000 11250 0這4個(gè)矩陣相乘需要的最小數(shù)量乘法的次數(shù)=13600最優(yōu)計(jì)算次序A（BC）D）7-9給定字符串A=“xzyzzyx”和B=“zxyyzxz”，使用LCS算法求最長公共子串，并給出一個(gè)最長公共子串。提示：從上到下，從左往右計(jì)算C矩陣，依據(jù)C矩陣，求得最長公共子序列解：計(jì)算求得C矩陣如下， 依矩陣C可求得兩個(gè)最長公共子序列分別為xyzz 和 zyyx （求一個(gè)即可）7-17設(shè)流水作業(yè)調(diào)度的實(shí)例為n=7，(a0, a1, a2, a3, a4, a5, a6)=(6,2,4,1,7,4,7), (b0, b1, b2, b3, b4, b5, b6)=(3,9,3,8

32、,1,5,6).請使用流水作業(yè)調(diào)度的Johnson算法求使完成時(shí)間最小的最優(yōu)調(diào)度,并求該最小完成時(shí)間。提示：依據(jù)調(diào)度規(guī)則，求得最優(yōu)調(diào)度次序解:；令mi=minai，bi 0<=i<7即得: m0=b0=3, m1=a1=2, m2=b2=3, m3=a3=1, m4=b4=1, m5=a5=4 m6=b6=6 考慮mi,對其從小到大排序得(m3,m4,m1,m0,m2,m5,m6) 考慮mi序列(如果序列中下一個(gè)數(shù)mi是ai,則作業(yè)i放在最左的空位，否則，作業(yè)i放在最右的空位)得:最優(yōu)調(diào)度順序(3,1,5,6,2,0,4)依據(jù)最優(yōu)調(diào)度在兩臺(tái)處理機(jī)上處理作業(yè)，最小完成時(shí)間:36(畫出

33、如教材P170的圖7-17的形式即可求得最小完成時(shí)間36)8-2 #include <iostream.h>#include <math.h>int count=0;/記錄可行解的個(gè)數(shù)/先將書中的遞歸變?yōu)槿缦路沁f歸函數(shù)，再在輸出一個(gè)可行解之后，加上break;int place(int k,int xk,int *x)for(int j=0;j<k;j+)if(xj=xk | abs(xj-xk)=abs(j-k)/相互沖突,return 0;return 0;return 1;/互不沖突,return 1void NQueens(int n,int *x)int k=0;xk=-1;while(k>=0) xk=xk+1;while (xk<n && !place(k,xk,x)/找安置第K個(gè)皇后的合法位置 xk=xk+1;if(xk<n)/找到安置第K個(gè)皇后合法的位置，if (k=n-1)/找到一個(gè)可行解，