2022年算法與分析平時(shí)作業(yè)

1、平時(shí)作業(yè)1、給定下述二分搜索算法，請(qǐng)判斷算法的對(duì)的性，指出錯(cuò)誤算法的產(chǎn)生因素。 a) int BinarySearch(Type a, const Type& x, int l, int r) while (r = l) int m = (l+r)/2; if (x = am) return m; if (x = l) int m = (l+r)/2; if (x = am) return m; if (x am) r = m+1; else l = m-1; return -1; 答：錯(cuò)誤，if (x l) int m = (l+r)/2; if (x = am) return m; if

2、(x = l)2、O(1)空間子數(shù)組環(huán)衛(wèi)算法：設(shè)a0:n-1是一種n維數(shù)組，k（1 k n-1）是一種非負(fù)整數(shù)。試設(shè)計(jì)一種算法將子數(shù)組a0 : k-1與ak+1 : n-1換位。規(guī)定算法在最壞狀況下耗時(shí)O(n)，且只用O(1)的輔助空間。答：算法分析： 當(dāng)vk左邊子數(shù)組的長(zhǎng)度等于右邊的子數(shù)組長(zhǎng)度時(shí)，直接將兩個(gè)子數(shù)組相應(yīng)的元素互換即可 當(dāng)左邊子數(shù)組長(zhǎng)度不不小于右邊子數(shù)組長(zhǎng)度時(shí)，將左邊子數(shù)組與右邊子數(shù)組右邊的等長(zhǎng)子數(shù)組對(duì)換，再對(duì)成果遞歸調(diào)用對(duì)換函數(shù) 當(dāng)右邊子數(shù)組長(zhǎng)度不不小于左邊子數(shù)組長(zhǎng)度時(shí)，將右邊子數(shù)組與左邊子數(shù)組左邊的等長(zhǎng)子數(shù)組對(duì)換，再對(duì)成果遞歸調(diào)用對(duì)換函數(shù) 通過(guò)度析，可知只需要運(yùn)用保存元素對(duì)換

3、時(shí)的互換空間即可，空間復(fù)雜度為O(1)，子數(shù)組對(duì)換時(shí)時(shí)間復(fù)雜度不會(huì)超過(guò)O(n)#include #include #include #include using namespace std; /相應(yīng)互換v的left_low-left_high 和 right_low - right_high void Swap(vector & v,int left_low,int left_high,int right_low,int right_high) int temp; while(left_low = left_high) temp = vleft_low; vleft_low = vright_

4、low; vright_low = temp; +left_low; +right_low; return; /分治算法，每次選最小的子數(shù)組相應(yīng)互換 void Exchange(vector & v,int k,int low,int high) if(lowhigh) if(k-low+1)=(high-k)/vk左右兩個(gè)子數(shù)組長(zhǎng)度相等，直接互換 Swap(v,low,k,k+1,high); else if(k-low+1)(high-k)/vk左邊子數(shù)組長(zhǎng)度不不小于右邊子數(shù)組，將左邊的子數(shù)組互換到右邊子數(shù)組的右邊Swap(v,low,k,low+high-k,high); Exchang

5、e(v,k,low,low+high-k-1); else /vk右邊子數(shù)組換到左邊子數(shù)組前部分 Swap(v,low,high+low-k-1,k+1,high); Exchange(v,k,high+low-k,high); return; int main() vector v; int n,k; while(scanf(%d%d,&n,&k)=2) v.resize(n); for(int i=0;in;+i) scanf(%d,&vi); printf(Before exchange subarray:n); for(int j=0;jn;+j) printf(%d ,vj); pr

6、intf(n); Exchange(v,k,0,n-1); printf(After exchange subarray:n); for(int k=0;kn;+k) printf(%d ,vk); printf(n); return 0; 3、定義： 給定一種自然數(shù)n，由n開(kāi)始依次產(chǎn)生半數(shù)集set(n)中的元素如下： 1）； 2）在n的左邊加上一種自然數(shù)，但該自然數(shù)不能超過(guò)近來(lái)添加的數(shù)的一半； 3）按此規(guī)則進(jìn)行解決，直至不能再添加新的自然數(shù)為止。 例如 。其中共有6個(gè)元素。 半數(shù)集問(wèn)題：對(duì)于給定的n，求半數(shù)集set(n) 中元素的個(gè)數(shù)。答：#includeusing namespace st

7、d;int a1001;int comp(int n) int i; for( i=2;i=n;i+) if(i%2=0) ai=ai/2+ai-1; else ai=ai-1; return an;int main() int n; coutn; for(int i=0;i=n;i+) ai=i; if(n1000) coutendl輸入錯(cuò)誤，請(qǐng)注意輸入值n的范疇.endl; else coutendl半數(shù)集set(n)中的元素個(gè)數(shù)為：; coutcomp(n)endl; return 0; 4、設(shè)計(jì)一種算法，找出由n個(gè)數(shù)構(gòu)成的序列的最長(zhǎng)單調(diào)遞增子序列的長(zhǎng)度。答：#include#defin

8、em10/迅速排序voidQuickSort(intR,ints,intt)inti=s,j=t;inttmp;if(si&Rj=tmp)j-;Ri=Rj;while(ij&Ri=tmp)i+;Rj=Ri;Ri=tmp;QuickSort(R,s,i-1);QuickSort(R,i+1,t);/找出最長(zhǎng)公共子序列voidLCSLength(intx,inty,intn,intcmm,intbmm)inti,j;for(i=0;in;i+)c0i=0;ci0=0;for(i=0;in;i+)for(j=0;j=cij-1)cij=ci-1j;bij=2;elsecij=cij-1;bij=3;

9、voidLCS(inti,intj,int*x,intbmm)if(i0|j0)return;if(bij=1)LCS(i-1,j-1,x,b);coutxi;elseif(bij=2)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b);voidmain()intxm,ym,d;cout請(qǐng)輸入元素個(gè)數(shù)d;cout請(qǐng)輸入元素endl;for(inti=0;ixi;yi=xi;intcmm=0,bmm=0;QuickSort(x,0,d-1);LCSLength(x,y,d,c,b);cout最長(zhǎng)單調(diào)遞增子序列為：endl;LCS(d-1,d-1,x,b); 5、會(huì)場(chǎng)安排問(wèn)題：假設(shè)

10、要在足夠多的會(huì)場(chǎng)里安排一批活動(dòng)，并但愿使用盡量少的會(huì)場(chǎng)。設(shè)計(jì)一種有效的貪心算法進(jìn)行安排。對(duì)于給定的n個(gè)待安排的活動(dòng)，計(jì)算使用至少會(huì)場(chǎng)的個(gè)數(shù)。每個(gè)活動(dòng)i均有一種開(kāi)始時(shí)間和結(jié)束時(shí)間，分別表達(dá)為b(i)，f(i)。答：#includeusingnamespacestd;#defineM50/最大活動(dòng)數(shù)structActiveintb;/開(kāi)始時(shí)間intf;/結(jié)束時(shí)間intno;/預(yù)安排會(huì)場(chǎng)號(hào)aM;/兩元素互換位置voidswap(Active&a,Active&b)Activet;t=a;a=b;b=t;voidmain()intk;inti,j;cout輸入待安排活動(dòng)數(shù):k;cout輸入待安排活動(dòng)的

11、開(kāi)始時(shí)間和結(jié)束時(shí)間:endl;/輸入活動(dòng)時(shí)間for(i=1;iai.bai.f;ai.no=0;/活動(dòng)時(shí)間排序for(i=1;i=k;i+)for(j=i;jaj.b)swap(ai,aj);if(ai.b=aj.b)if(ai.faj.f)swap(ai,aj);intsum=1;/使用的會(huì)場(chǎng)數(shù)初始化intn;a1.no=sum;for(i=2;i=k;i+)for(n=1;ni;n+)if(an.no!=0&an.f=ai.b)ai.no=an.no;an.no=0;/已經(jīng)安排過(guò)的活動(dòng)就不再比較break;if(n=i)sum+=1;ai.no=sum;cout輸出至少會(huì)場(chǎng)數(shù):nsumen

12、dl;system(pause);6、最優(yōu)分解問(wèn)題：設(shè)n是一種正整數(shù)?，F(xiàn)規(guī)定將n分解為若干個(gè)互不相似的自然數(shù)的和，使得這些自然數(shù)的乘積最大。設(shè)計(jì)一種算法，得到最優(yōu)分解方案。 分析：我們懂得如果a+b=常數(shù)，則|a-b|越小，a*b越大。 貪心方略：將n提成從2開(kāi)始的持續(xù)自然數(shù)的和。如果最后剩余一種數(shù)，將此數(shù)在后項(xiàng)優(yōu)先的方式下均勻地分給前面各項(xiàng)。答：void dicomp(int n, int a) int k = 1; if (n 3) a1 = 0; return; if (n ak) k+; ak = ak - 1 + 1; n -= ak; if (n = ak) ak+; n-; fo

13、r (int i = 0; i n; i+) ak - i+; 7、子集和問(wèn)題：設(shè)是n個(gè)正整數(shù)的集合，c是一種正整數(shù)。那么與否存在S的一種子集S1，使得子集中元素之和等于c，即。答：#includeintn,c;inta100;intcurrent100;/寄存目前選擇的狀況intbest100;/寄存最后選擇的子集合，besti=1，表達(dá)涉及，反之即不涉及。intd=1;/判斷有無(wú)滿(mǎn)足的狀況intd2=0;/與否已經(jīng)選出子集和voidBack(intm,intcount);intmain()inti,j;scanf(%d%d,&n,&c);for(i=0;in;i+)scanf(%d,&ai

14、);currenti=besti=0;Back(0,0);if(d)printf(nosolutionn);for(j=0;jn)return;if(count=c)d=0;/有滿(mǎn)足的子集和if(d2)return0;for(k=0;k 0 xi = yi 時(shí) , cij = ci-1j-1 + 1 當(dāng) i , j 0 xi != yi 時(shí) , cij = max cij-1 , ci-1j public class LSC private int c,b;private int m,n;private char A,B;public LSC(char A,char B) this.A=A;

15、this.B=B; m=A.length; n=B.length; c=new intm+1n+1; b=new intm+1n+1;for(inti=0;in+1;i+) c0i=0; for(intj=0;jm+1;j+)cj0=0;public LSC() public int LSCLength() for(int i=1;im+1;i+) for(int j=1;j=cij-1) cij=ci-1j; bij=1; /* * 狀況 */ else cij=cij-1; bij=2; return cmn; public void print(int i,int j) if(i=0|j

16、=0) return; else if(bij=0) print(i-1,j-1); System.out.print(Ai-1); else if(bij=1) print(i-1,j); else print(i,j-1); public int LSCLength2(int i,int j) if(i0|ja2?a1:a2; public static void main(String args) char A=g,f,d,a,s,d,a,c; char B=g,c,f,a,t,0,c,c; LSC lsc=new LSC(A,B); System.out.println(lsc.LSC

17、Length2(7,7); 9、記矩陣連乘積 。 擬定計(jì)算A1:n的最優(yōu)計(jì)算順序，使得所需數(shù)乘的次數(shù)至少。 1、闡明矩陣連乘計(jì)算順序問(wèn)題的最優(yōu)解涉及著其子問(wèn)題的最優(yōu)解，即最優(yōu)子構(gòu)造性質(zhì)。 2、該問(wèn)題具有子問(wèn)題的重疊性質(zhì)。 3、闡明采用動(dòng)態(tài)規(guī)劃措施可以解決該問(wèn)題。 4、設(shè)計(jì)該算法，分析算法的復(fù)雜性。答：計(jì)算Ai:j的最優(yōu)順序所涉及的計(jì)算矩陣子鏈Ai:k和Ak+1:j的順序也是最優(yōu)的。設(shè)計(jì)算Ai:j，1ijn，所需要的至少數(shù)乘次數(shù)mi,j，則原問(wèn)題的最優(yōu)值為m1,n當(dāng)i=j時(shí)，Ai:j=Ai，無(wú)需計(jì)算，因此，mi,j=0，i=1,2,n當(dāng)ij時(shí)，運(yùn)用最優(yōu)子構(gòu)造性質(zhì)計(jì)算mi,j . 設(shè)Ai:j的最優(yōu)

18、順序在Ak和Ak1之間斷開(kāi)，則其中Ai的維數(shù)為pi-1pjk的位置只有j-i 種也許, i, i+1, , j-1，其中使計(jì)算量最小的那個(gè)位置為最優(yōu)解，數(shù)乘次數(shù)mi,j最小值為問(wèn)題的最優(yōu)值可以遞歸地定義mi,j為：將最優(yōu)值mi j相應(yīng)的斷開(kāi)位置記為si j，則可遞歸的由si j構(gòu)造出相應(yīng)的最優(yōu)解對(duì)于1ijn不同的有序?qū)?i,j)相應(yīng)于不同的子問(wèn)題。因此，不同子問(wèn)題的個(gè)數(shù)最多只有 由此可見(jiàn)，在遞歸計(jì)算時(shí)，許多子問(wèn)題被反復(fù)計(jì)算多次。這也是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的又一明顯特性。用動(dòng)態(tài)規(guī)劃算法解此問(wèn)題，可根據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過(guò)程中，保存已解決的子問(wèn)題答案。每個(gè)子問(wèn)題只計(jì)算一

19、次，而在背面需要時(shí)只要簡(jiǎn)樸查一下，從而避免大量的反復(fù)計(jì)算最后得到多項(xiàng)式時(shí)間的算法matrixChain 已經(jīng)記錄了構(gòu)造最優(yōu)解所需的所有信息。從s1n 可知，計(jì)算A1:n的最優(yōu)加括號(hào)方式為( A 1 : s1n ) (As1n+1: n )計(jì)算A 1 : s1n 的最優(yōu)加括號(hào)方式為(A 1 : s1s1n )(A s1s1n +1 : s1n )10、考慮分?jǐn)?shù)背包問(wèn)題，定義如下：給出n 個(gè)大小為 s1, s2, , sn , 價(jià)值為v1, v2, , vn 的物品， 并設(shè)背包容量為C, 要找到非負(fù)實(shí)數(shù)x1, x2, , xn, 使和 在約束下最大。寫(xiě)出求解問(wèn)題的貪心算法，估計(jì)算法的時(shí)間復(fù)雜性。答：從問(wèn)題的某一初始解出發(fā)；while能朝給定總目的邁進(jìn)一步do求出可行解的一種解元素