1、實驗標題實驗目的實驗內容與源碼1矩陣連乘 2、最長公共子序列3 、最大子段和4、凸多邊形最優三角剖分5、流水作業調度6、0-1背包問題 7、最優二叉搜索樹掌握動態規劃法的基本思想和算法設計的基本步驟。1、矩陣連乘#in clude<iostream>#in clude<cstdlib>using n amespace std;const int size=4;ra,ca和rb,cb分別表示矩陣 A和B的行數和列數void matriMultiply(i nta4,i nt b4,i nt c4,i nt ra ,int ca,i ntrb ,int cb )if(ca!

2、=rb) cerr<<"矩陣不可乘"for(i nt i=0;i<ra;i+)for(i nt j=O;j<cb;j+)int sum=ai0*b0j;for(i nt k=1;k<ca;k+)sum+=aik*bkj;cij=sum;void MatrixChai n(int *p,i nt n,i nt m4,i nt s4)for(i nt i=1;i<=n;i+) mii=0;對角線for(i nt r=2;r<=n;r+)外維for(i nt i=1;i<=n-r+1;i+)上三角int j=i+r-1;mij=mi

3、+1j+pi-1*pi*pj;sij=i;for(i nt k=i+1;k<j;k+)int t=mik+mk+1j+pi-1*pk*pj;if(t<mij)mij=t;sij=k;void Traceback(i nt i,i nt j,i nt s4)if(i = j) cout<<"A"<<i;else if(i+1 = j)cout<<"(A"<<i<<"A"<<j<<")"elsecout<<&qu

4、ot;("Traceback(i,sij,s);Traceback(sij+1,j,s);cout<<")"int mai n()int w;cout<<" 矩陣個數："cin> >w;int pw,sww;cout<<"輸入矩陣A1維數："cin >>pO»p1；for(i nt i=2 ; i<=w ; i+)int m = pi-1;cout<<" 輸入矩陣A"<<i<<"維數：

5、"cin> >pi_1»pi;if(pi-1 != m)"<<e ndl;cout<<e ndl<<"維數不對，矩陣不可乘!exit(1);Traceback(1,w,s);return 0;運行結果上«法8日巳矩陣連乘1巳炬叵卜數：勺陣蛆維數：2 3陣朋維數；3 4庫A3維數：4 S (A1A2JA3)Mm 丄 c_丄:_on_ogA_.2、最長公共子序列#in clude<cstri ng>#in clude<iostream>#defi ne N 100using n

6、 amespace std;str1存儲字符串x, str2存儲字符串ychar str1N,str2N;/lcs存儲最長公共子序列char lcsN;cij存儲str11.i 與str21.j的最長公共子序列的長度int cNN;flagij=O/flagij=1 flagij=-1為 str1i=str2j為 ci-1j>=sij-1為 ci-1j<sij-1 int flagNN;/求長度int LCSLe ngth(char *x, char *y) int i,j;分別取得x,y的長度int m = strle n(x);int n = strle n( y); for(

7、i=1;i<=m;i+) ci0 = 0;for(i=0;i<=n ;i+) c0i = 0;for(i=1;i<=m;i+)for(j=1;j<=n ;j+)if(xi-1=yj-1)cij = ci-1j-1 +1; flagij = 0;else if(ci-1j>=cij-1)cij = ci-1j; flagij = 1;elsecij = cij-1; flagij = -1;return cm n;/求出最長公共子序列char* getLCS(char *x, char *y,i nt le n, char *lcs) int i = strle n

8、( x);int j = strle n( y);while(i&&j)if(flagij=0)lcs-le n = xi-1;i-;j-;else if(flagij=1)i-;elsej-;return lcs; int mai n()int i;cout<<"請輸入字符串x: "<<endl;cin> >str1;cout<<"請輸入子符串y： "<<endl;cin> >str2;in t IcsLe n = LCSLe ngth(str1,str2);cou

9、t<<"最長公共子序列長度："<<lcsLe * <e ndl;char *p = getLCS(str1,str2,lcsLe n,lcs);cout<<"最長公共子序列為："for(i=0;i<lcsLe n;i+) cout<<lcsi<<""return 0;運行結果6 e亠-J :s 度：亠 列列 序序.-:子子 宇Eh字滬共共 入Lef入cf冬公 ab/ 產 1嗇se口IFK圭-3、最大子段和/分治法求最大子段和#in clude<iostrea

10、m>using n amespace std;int MaxSubSum(int *a,int left,int right)int sum=0;if(left=right) sum=aleft>O?aleft:O;elseint cen ter = (left+right)/2;/最大子段和在左邊int leftsum=MaxSubSum(a,left,center);/最大子段和在右邊int rightsum=MaxSubSum(a,ce nter+1,right);/最大子段和在中間int s1=0;int lefts=0;for(int i=center;i>=lef

11、t;i-)lefts+=ai;if(lefts>s1) s1=lefts;int s2=0;int rights=O;for(i nt i=cen ter+1;i<=right;i+)rights+=ai;if(rights>s2) s2=rights;sum=s1+s2;前后子段和相加/判斷最大子段和if(sum>leftsum)sum=leftsum;if(sum>rightsum) sum=rightsum;return sum;int MaxSum(i nt *a,i nt n)return MaxSubSum(a,1, n-1);int mai n()i

12、nt a8=2,-3,-5,4,1,7,1,-5;cout<<"最大子段和為："<<MaxSum(a,8); return 0;/動態規劃法#in clude<iostream>using n amespace std;int MaxSum(i nt *a,i nt n)int sum=0,b=0;for(i nt i=1;i< n;i+)此處不能=n，if(b>0) b+=ai;else b=ai;if(b>sum) sum=b;return sum;int mai n()int a8=2,-3,-5,4,1,7,1,

13、-5;cout<<"最大子段和為："<<MaxSum(a,8); return 0;運行結果賞大子段W為：13'Pracess returned 0 (0k0) ©Kecution time : 6 274 s Press any key to continue4、凸多邊形最優三角剖分#in clude<iostream>#in clude<cmath>#in clude<cstdlib>#defi ne N 50using n amespace std;struct pointint x;int

14、 y;int dista nce(poi nt X, poi nt Y)兩點距離int dis = (Y.x-X.x)*(Y.x-X.x) + (Y.y-X.y)*(Y.y-X.y); return (in t)sqrt(dis);int w(po int a, point b, point c)/權值retur n dista nce(a,b) + dista nce(b,c) + dista nce(a,c); 判斷是否能構成凸多邊形point *v;/bool Judge In put()int *total;/記錄凸多邊形各頂點坐標記錄坐標在直線方程中的值int m,a,b,c;cou

15、t<<"請輸入凸多邊形頂點個數：”；cin»m;int M = m-1;for(i nt i=0 ; i<m ; i+)cout<<"輸入頂點v"<<i<<"的坐標："cin> >vi.x»vi.y;/根據頂點坐標判斷是否能構成一個凸多邊形for(i nt j=0 ; j<m ; j+)int p = 0;int q = 0;if(m-1 = j)a = vm-1.y - v0.y;b = vm-1.x - v0.y;c = b * vm-1.y - a

16、 * vm-1.x;elsea = vj.y - vj+1.y;b = vj.x - vj+1.x;c = b * vj.y - a * vj.x;for(i nt k=0 ; k<m ; k+)totalk = a * vk.x - b * vk.y + c;if(totalk > 0)p = P+1;else if(totalk < 0)q = q+1;if(p>0 && q>0) | (p=0 && q=0)cout<<"無法構成凸多邊形！"<<e ndl;exit(1);bool

17、mi nWeightTria ngulatio n()計算最優值算法int M;int *t, *s;point *v;for(i nt i=1 ; i<=M ; i+)tii = 0;for(i nt r=2 ; r<=M ; r+)for(i nt i=1 ; i<=M-r+1 ; i+)int j = i+r-1;tij = ti+1j + w(vi-1,vi,vj);sij = i;for(i nt k=i+1 ; k<i+r-1 ; k+)int u = tik + tk+1j + w(vi-1,vk,vj);if(u < 圳j)tij = u;sij

18、= k;return true; void Traceback(i nt i, i nt j, i nt *s)if(i = j)return;Traceback(i,sij,s);Traceback(sij+1,j,s);cout<<"三角形：v"<<i-1<<"v"<<sij<<"v"<<j<<e ndl; int mai n()記錄最優三角剖分中所有三角形信息記錄最優三角剖分所對應的權函數值 記錄凸多邊形各頂點坐標記錄坐標在直線方程中的值int

19、*s;/int *t;/point *v;/int *total;/int M=0;t = new int *N;s = new int *N;for(int i=0 ; i<N ; i+)ti = new in tN;si = new in tN;v = new poi ntN;total = new in tN;if(Judgel nput()if(mi nWeightTria ngulatio n()Traceback(1,M,s);cout<<e ndl;cout<<"最優權值之和為:return 0;運行結果:l'I I:MJScode

20、3.50邊形最優三角剖分心e0122126慣輸入凸級邊形頂點個數=T 輸入頂點詢的坐標：8 26 輸入頂點ML的坐標：0 20 輸入頂點說的坐標：0 10 輸入頂點說的坐標：10 輸入觸點嘰的坐棕：22 輸入頂點詡的坐標：27 樹入頂點v6的坐標：15 二角形：v0vlv2 匚甬麻：v2v3v4 三角形：v0v2v4 巨角形：v4v5ir 二角形：v0v4v6 |最優和值之和為：22SProcess returned 0 (OjtO) execution time I 49965 s Press any key to continue.5、流水作業調度#in clude<iostream

21、>#defi ne N 100 using n amespace std;class Jobtypepublic:/* i nt operator<=(Jobtype a)c onstreturn(key<=a.key);*/int key;int in dex;bool job;； void sort(Jobtype *d,i nt n)int i,j;Jobtype temp;最多做n-1趟排序本趟排序開始前，交換標志應為假發生了交換，故將交換標志置為真本趟排序未發生交換，提前終止算法bool excha nge; /交換標志for(i = 0;i < n;i +)

22、 /excha nge = false; /for(j = n - 1;j >= i;j -) if(dj+1.key < dj.key) temp = dj+1;dj+1 = dj; dj = temp;excha nge=true; /if(!excha nge) /return;int FlowShop(i nt n,i nt *a,i nt *b,i nt *c)Jobtype *d = new Jobtype n;for(i nt i=0;i< n;i+)初始化執行時間di.key=ai>bi?bi:ai; di.job=ai<=bi;作業組di.i n

23、dex=i;作業序號sort(d, n);int j=0;int k=n-1;for(i nt i=0;i< n;i+)最優調度if(di.job)cj+=di.i ndex;elseck-=di.i ndex;j=acO;k=j+bcO;for(i nt i=1;i< n; i+)j+=aci; k=j<k?k+bci:j+bci;delete d;回收空間return k;返回調度時間int mai n()int n ,*a,*b,*c;cout<<"作業數："cin»n;Jobtype *d = new JobtypeN;a=n

24、ew in tN;b=new in tN;c=new in tN;cout<<"請輸入作業號和時間："for(i nt i=0;i <n ;i+)cin> >di.i ndex»di.key;cout << en dl;int k=FlowShop( n, a,b,c);cout<<"n調度時間："<<k<<e ndl;輸出最優調度序列cout<<" 最優調度序列:"for (int i = 0; i < n; i+)/cout

25、<< ci << ""return 0;運行結果:篡法code3.9流水作業調S.exe口 回 S3和時間:executron- tiiiLe ! 27.283 s調度時間：385319& 最優調度序列：2 3 0 1 Process returned 0 (0x0)Press any key to continue.6、0-1背包問題#in elude <iostream> #i nclude <ioma nip> using n amespace std;const int C=10;容量const int N=5

26、;個數int max(c onst int a,c onst int b) retur n a>b?a:b; int min(const int a,c onst int b) retur n a<b?a:b; /*m為記錄數組mij代表在剩有j容量的條件下，從i開始往后的物品中可以取得的最大價值w為重量數組，v為價值數組n為物品個數，c為開始容量則m1c即此背包能剩下的最大價值*/void kn apsack(i nt *m,i nt n, int c,i nt *w, int *v)int jMax = min(wn-1,c);前 n-1 個物品for(i nt j=0;jv=

27、jMax;j+)m nj=0;for(i nt j=w n ;j<=c;j+)m nj=v n;for(i nt i=n-1;i>1;i-)jMax=mi n(wi-1,c);for(i nt j=O;jv=jMax;j+)mij = mi+1j;for(i nt j=wi;j<=c;j+)mij = max(mi+1j,mi+1j-wi+vi);m1c=m2c;if(c>=w1) m1c=max(m1c,m2c-w1+v1);/找出最優解，0表示不能裝，1表示能裝 void traceback(i nt *m,i nt n ,i nt c,i nt *x,i nt *

28、w) for(i nt i=1;i <n ;i+)if(mic=mi+1c) xi=0; elsexi=1;c-=wi;x n=(m nc=0)?0:1;int mai n()int *v=new in tN+1;int *w=new in tN+1;int *m=new in t* N+1;int *x=new in t N+1;for(i nt i=0;i<N+1;i+)mi=new in tC+1;coutvv"輸入重量序列,"<<N<<"個"<<endl;for(i nt i=1;i<=N;i

29、+)ci n> >wi;cout«"輸入價值序列,"<<N<<"個"<<endl;for(i nt i=1;i<=N;i+)cin> >vi;kn apsack(m,N,C,w,v);traceback(m,N,C,x,w);cout«"最優值："<<m1Cvvendl; coutvv"是否裝入背包的情況："for(i nt i=1;i<=N;i+)cout<<xi;for(int i=0;i<

30、N+1;i+)delete mi;delete m;return 0;運行結果! 1 "l：W£code3,10| 口 | 回| S3輸A重量序列/個俞入價值序列,5個3 4 2 7 1聶價值* id是否裝入背包的情況；11010proc亡s凸 工亡turri亡d 0 （0x0）亡xacirtio垃血匚：IN 丁2呂 srrr7、最優二叉搜索樹#in clude<iostream>#in clude<cmath>#i nclude<limits>#defi ne N 100using n amespace std;const double MAX = nu meric_limits<double>:max(); /double的最大值 ai為結點i被訪問的概率bi為“虛結點” i被訪問的概率/mij用來存放子樹（i,j）的期望代價wij用來存放子樹（i,j）的所有結點（包括虛結點）的 a,b概率之和/sij用來跟蹤root的void Opt