(完整word版)算法實(shí)驗(yàn)(word文檔良心出品)

1、算法設(shè)計(jì)實(shí)驗(yàn)報(bào)告遞歸與分治策略問(wèn)題描述:給定數(shù)組a0:n-1,試設(shè)計(jì)一個(gè)算法，在最壞情況下用3n/2-2次比較找出a0:n-1中元素的最大值和最小值。解決方法：先將數(shù)組前一半的元素與后一半的元素分別逐個(gè)進(jìn)行比較，如第1個(gè)與第n/2+1個(gè)，將較小者在前較大者在后交換好，則通過(guò)n/2次比較后最大值在后一半，最小值在前一半；然后在前一半與后一半中分別經(jīng)過(guò)n/2-1次比較得到最大值與最小值。整個(gè)算法經(jīng)過(guò)n/2+2*(n/2-1)=3/2*n-2 次比較。代碼實(shí)現(xiàn)：#i ncludevstdio.h>int mai n()int max,mi n;int i,n,t;int a100;scan f

2、("%d",&n); for(i=0;i vn ;i+) sca nf("%d",&ai);for(i=0;i< n/2;i+) if(ai>a n/2+i) t=ai; ai=a n/2+i; a n/2+i=t;max=a n-1;mi n=a0;for(i=1;i< n/2;i+) if(mi n> ai)mi n=ai;for(i=n-1;i>=n /2;i-)if(maxvai)max=ai; prin tf("the max is %dn",max); prin tf(&quo

3、t;the min is %dn",mi n); return 0;運(yùn)行截圖：52 5 7 8 4 the nax is C七 he nin is 2 請(qǐng)按任意鍵繼續(xù)*.PLl.nax IS Vthe nin is 1情按枉意鍵繼續(xù)-實(shí)驗(yàn)心得：本實(shí)驗(yàn)要點(diǎn)在于運(yùn)用分治法的思想，將 N個(gè)數(shù)之間的問(wèn)題分割成一些小規(guī)模的相同問(wèn)題，以便減少計(jì)算的復(fù)雜度。16問(wèn)題描述：Gray碼是一個(gè)長(zhǎng)度為25的序列。序列中無(wú)相同元素，每個(gè)元素都是長(zhǎng)度為n位的串，相鄰元素恰好只有一位不同。用分治策略設(shè)計(jì)一個(gè)算法對(duì)任意的n構(gòu)造相應(yīng)的Gray碼。解決方法：當(dāng)n=1時(shí),Gray 碼:0,1當(dāng)n=2時(shí),Gray 碼:0

4、0， 10， 11， 01當(dāng)n=3時(shí),Gray 碼:000, 010，011，001，101，111,110, 100當(dāng)n=4時(shí),Gray 碼:0000，0010，0011，0001，0101,0111,1101,0110, 0100, 1100, 1110, 1111, 1001, 1011, 1010, 1000可以看出,從n=2開(kāi)始，每個(gè)n的Gray碼由兩部分組成。后一位的Gray碼可以從前一位的Gray碼求出。即在n的Gray碼的前半部分是n-1的所有Gray碼順次在前面加0得到；n的Gray碼的后半部分是n-1的所有Gray碼逆序在前面加1得到。代碼實(shí)現(xiàn)：#i ncludevstdi

5、o.h>int str10000040;int n;int f(int x)int y=1;for(i nt i=1;i<=x;i+) y*=2;return y;void gray(i nt a,i nt b) if(b=O)return ; for(i nt i=0;iva/2;i+) stri n-b=0; stri+a/2 n-b=1; gray(a/2,b-1);for(i nt i=a/2;i<a;i+)for(i nt j=n-b+1;j vn ;j+) strij=stra-i-1j;int mai n()while(sca nf("%d"

6、,&n), n)gray(f( n),n);for(i nt i=0;i<f( n);i+, printf("") for(i nt j=O;j vn ;j+) prin tf("%d",strij);prin tf("n");return 0;運(yùn)行截圖:0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000實(shí)驗(yàn)心得：本實(shí)驗(yàn)要點(diǎn)是對(duì)Gray (int a, int b)遞歸調(diào)用，著重后一半的逆序在前面加1 .遞歸的使用

7、使得程序簡(jiǎn)短明了。問(wèn)題描述:動(dòng)態(tài)規(guī)劃在一個(gè)圓形操場(chǎng)的四周擺放著 n堆石子，現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的兩堆石子合并成新的一堆,并將新的一堆石子數(shù)記為該次合并的得分。 試設(shè)計(jì)一個(gè)算法，計(jì)算出將n堆石子合并成一堆的最小得分和最大得分。解決方法：將圓形斷開(kāi)得aii=jMaxij= ai+aji=j-1Maxik+maxk+1j+ai+ai+1+aji<jai i=jMi nij= ai+aji=j-1Min ik+mi n k+1j+ai+ai+1+ +aji<j用動(dòng)規(guī)自底向上計(jì)算。代碼實(shí)現(xiàn)：#i ncludevstdio.h>#defi ne inf 100

8、000000int a1000,sum1000;int n;int dp 100010002;int mai n()int i,j,k,h;while(sca nf("%d",&n )!=EOF)for(i=1;i<=n ;i+)sca nf("%d",&ai);int amin=inf;int amax=-i nf;for(h=1;hv=n ;h+)sum0=0;for(i=1;i<=n ;i+)sumi=sumi-1+ai;for(i=1;i<=n ;i+)dp ii0=d p ii1=0;for(i=1;i<

9、 n;i+)dp ii+10=d pii+11=ai+ai+1; for(j=3;j<=n;j+)for(i=1;i<=n-j+1;i+)int nmin=inf;int nm ax=-i nf;for(k=i;k<=i+j-2;k+)if(nmin >d pikO+d p k+1i+j-10+sumj+i-1-sumi-1) nmin=d pikO+dp k+1i+j-10+sumj+i-1-sumi-1;if(nm ax<d pik1+d pk+1i+j-11+sumj+i-1-sumi-1) nm ax=d pik1+d pk+1i+j-11+sumj+i-

10、1-sumi-1;dp ii+j-10=nmin;dp ii+j-11=nm ax;if(ami n>d p1 nO)ami n=d p1 n0; if(amax<d p1 n 1)amax=d p1 n1; an+1=a1;for(i=1;i<=n ;i+)ai=ai+1;prin tf("the min value is %dn",ami n); prin tf("the max value is %dn",amax);return 0;運(yùn)行截圖：世 3-1 氏i上；3 4 S nin value rax valuemin valu

11、e irtax ualueIsisisis3350.Jp;占7 nin value WAX valueISis2327實(shí)驗(yàn)心得：本實(shí)驗(yàn)用動(dòng)態(tài)規(guī)劃方法求解，關(guān)鍵在于先找出直線排列的最優(yōu)解,然后再刻畫(huà)圓排列時(shí)的最優(yōu)解，在計(jì)算中保存已經(jīng)計(jì)算過(guò)的結(jié)果，每個(gè)子問(wèn)題只計(jì)算一次，從而避免大量的計(jì)算。 問(wèn)題描述：長(zhǎng)江游艇俱樂(lè)部在長(zhǎng)江上設(shè)置了n個(gè)游艇出租站1, 2, ，n。游客可在這些游艇出租站租用游艇，并在下游的任何一個(gè)游艇出租站歸還游艇。游艇出租站i到游艇出租站j之間的租金為r(i,j)，1<=i<j<=n。試設(shè)計(jì)一個(gè)算法，計(jì)算出從游艇出租站i到游艇出租站j所需的最少租金。解決方法：用dp

12、ij表示從i到j(luò)的最小費(fèi)用j-i=1j-i>1,i<k<jdp ij=rij dp ij=mi n(rij,mi n(dp ik+d pkj代碼實(shí)現(xiàn)：#i ncludevstdio.h>#defi ne inf 100000000in t r100100;int dp 100100;int n;int mai n()int i,j,k;scan f("%d",&n);for(i=1;i vn ;i+) for(j=i+1;j<=n ;j+) sca nf("%d",&rij);for(i=1;i<=n

13、;i+)dp ii=0;for(i=1;i <n ;i+)dp ii+1=rii+1;for(k=3;k<=n ;k+) for(i=1;i<=n-k+1;i+) dp ii+k-1=rii+k-1; for(j=i+1;jv=i+k-2;j+)if(dp ii+k-1>d p ij+d pji+k-1) dp ii+k-1=d pij+d pji+k-1;while(sca nf("%d%d",&i,&j)!=EOF) prin tf("%dn",d pij);return 0;運(yùn)行截圖：實(shí)驗(yàn)心得：本實(shí)驗(yàn)運(yùn)用動(dòng)態(tài)

14、規(guī)劃方法，由原先構(gòu)造好的最優(yōu)解結(jié)構(gòu)編程實(shí)現(xiàn),減小計(jì)算量。貪心算法 問(wèn)題描述:利用優(yōu)先隊(duì)列及并查集這兩個(gè)抽象數(shù)據(jù)類(lèi)型實(shí)現(xiàn)Kruskal 算法。解決方法：首先將n個(gè)頂點(diǎn)看成n個(gè)孤立的連通分支，利用優(yōu)先隊(duì)列將所有邊按權(quán)從小到大排列。然后從第一條邊開(kāi)始，依邊權(quán)遞增的順序查看每一條邊，若該邊的兩個(gè)頂點(diǎn)分屬于不同分支，則用邊將其連起來(lái),否則看下一條。用到集合的查找與合并，即并查集數(shù)據(jù)類(lèi)型。代碼實(shí)現(xiàn)：#i ncludevstdio.h>#defi ne MAX_TREE_SIZE 100typedef struct PTNode /樹(shù)的雙親表示 int data;int parent;P TNode;

15、typ edef structP TNode n odesMAX_TREE_SIZE; int n;P Tree;typedef PTree MFSet; / 并查集int in it_mfset(MFSet S)int fin d_mfset(MFSet S,i nt i) if(i<1 II i>S .n) return -1; int j;for(j=i;S. no desj. paren t>O;j=S. no desj. parent); return j;int merge_mfset(MFSet & S, i nt i,i nt j) if(i<1

16、 II i>S.n | j<1 | j>S .n)return -1;if(S. no desi. paren t>S. no desj. paren t) S.no desj. paren t+=S .no desi. parent; S.no desi. parent=j;elseS.no desi. paren t+=S .no desj. parent; S.no desj. paren t=i;return 1;/ "mfset.h"#i nclude <stdio.h>#i nclude "mfset.h"

17、#in clude <queue>using n ames pace std; struct bia ndouble weight;int u,v;frie nd bool op erator< (bia n n1, bia n n2) return n 1.weight > n 2.weight;edge100;bian t100;int n,e,k;void kruskal()p riority_queue <bia n> Q;for(i nt i=0;i<e;i+)Q.pu sh(edgei);MFSet S;S. n=n;for(i nt i=

18、1;i<=n ;i+)S.no desi. paren t=0;k=0;while(!Q.e mp ty() && kvn-1)bia n x=Q.t op();Q. pop ();int a=fi nd_mfset(S,x.u);int b=fi nd_mfset(S,x.v);if(a!=b)tk+=x;merge_mfset(S,a,b);int mai n()scan f("%d%d",&n,&e);for(i nt i=0;i<e;i+)sca nf("%d%d%lf",&edgei.u,&edgei.v,&edgei.weight); kruskal();for(i nt i=0;i<k;i+)prin tf("%d->%d %.3lfn",ti.u,ti.v,ti.weight);運(yùn)行截圖：3 313 52 3 &X->2 4.030l->3 5.000請(qǐng)按任意鍵繼續(xù)實(shí)驗(yàn)心得：本實(shí)驗(yàn)為使代碼簡(jiǎn)潔將并查集代碼寫(xiě)到了"mfset.h"作為頭文件使Kruskal用，利用優(yōu)先隊(duì)列簡(jiǎn)單地實(shí)現(xiàn)了排序。用貪心的