王晓东_算法整理

递归与分治算法1.递归插入排序Voidinsert_sort(typeA[],intn){intk;typea;n=n-1;if(n0){insert_sort(A,n);a=A[n];k=n-1;while(k=0)&&A[k]a)){A[k+1]=A[k];k=k-1;}A[k+1]=a;}}2.合并排序publicstaticvoidmergeSort(Comparablea[],intleft,intright){if(leftright){//至少有2个元素inti=(left+right)/2;//取中点mergeSort(a,left,i);mergeSort(a,i+1,right);merge(a,b,left,i,right);//合并到数组bcopy(a,b,left,right);//复制回数组a}}templateclassTypevoidmerge(Typec[],Typed[],intl,intm,intr){inti=l,j=m+1,k=l;while((i=m)&&(j=r)){if(c[i]=c[j]){d[k++]=c[i++];}else{d[k++]=c[j++];}}if(im){for(intq=j;q=r;q++){d[k++]=c[q];}}else{for(intq=i;q=m;q++){d[k++]=c[q];}}}3.快速排序privatestaticvoidqSort(intp,intr){if(pr){intq=partition(a,p,r);//以a[p]为基准元素将a[p:r]划分成3段//a[p:q-1],a[q]和a[q+1:r]，使得a[p:q-1]中任何元素小于等于a[q]，//a[q+1:r]中任何元素大于等于a[q]。下标q在划分过程中确定。qSort(p,q-1);//对左半段排序qSort(q+1,r);//对右半段排序}}intpartition(ints[],intl,intr)//返回调整后基准数的位置{inti=l,j=r;intx=s[l];//s[l]即s[i]就是第一个坑while(ij){//从右向左找小于x的数来填s[i]while(ij&&s[j]=x)j--;if(ij){s[i]=s[j];//将s[j]填到s[i]中，s[j]就形成了一个新的坑i++;}//从左向右找大于或等于x的数来填s[j]while(ij&&s[i]x)i++;if(ij){s[j]=s[i];//将s[i]填到s[j]中，s[i]就形成了一个新的坑j--;}}//退出时，i等于j。将x填到这个坑中。s[i]=x;returni;}4.整数划分publicstaticintdivide(intn,intm){if(n1||m1){return0;}elseif(n==1||m==1){return1;}elseif(n==m){return1+divide(n,n-1);}elseif(nm){returndivide(n,n);}else{returndivide(n,m-1)+divide(n-m,m);}}分治1.最大数最小数Voidmaxmin(intA[],int&e_max,int&e_min,intlow,inthigh){intmid,x1,y1,x2,y2;if((high-low)=1){if(A[high]A[low]){e_max=A[high];e_min=A[low];}else{e_max=A[low];e_min=A[high];}}else{mid=(high+low)/2;maxmin(A,x1,y1,low,mid)maxmin(A,x2,y2,mid+1,high);e_max=max(x1,x2);e_min-min(y1,y2);}}2.二进制大整数乘法functionMULT(X，Y，n);{X和Y为2个小于2n的整数，返回结果为X和Y的乘积XY}beginS:=SIGN(X)*SIGN(Y);{S为X和Y的符号乘积}X:=ABS(X);Y:=ABS(Y);{X和Y分别取绝对值}ifn=1thenif(X=1)and(Y=1)thenreturn(S)elsereturn(0)elsebeginA:=X的左边n/2位;B:=X的右边n/2位;C:=Y的左边n/2位;D:=Y的右边n/2位;ml:=MULT(A,C,n/2);m2:=MULT(A-B,D-C,n/2);m3:=MULT(B,D,n/2);S:=S*(m1*2n+(m1+m2+m3)*2n/2+m3);return(S);end;end;3.线性时间选择1.Typeselect(TypeA[],intn,intk){2.inti,j,s,t;3.Typem,*p,*q,*r;4.if(n38){//如果元素个数小于38：则直接排序5.sort(A,A+n);6.returnA[k-1];7.}8.p=newType[3*n/4];9.q=newType[3*n/4];10.r=newType[3*n/4];11.for(i=0;in/5;i++){//五个一组，把每组的中值元素存放进数组p12.mid(A,i,p);13.}14.m=select(p,i,i/2+i%2);//递归调用，取得中值元素存入m15.i=j=s=0;16.for(t=0;tn;i++){//按m、=m、m把数组分成三组17.if(A[t]m){18.p[i++]=A[t];19.}else{20.if(A[t]==m){21.q[j++]=A[t];22.}else{23.r[s++]=A[t];24.}25.26.}27.}28.if(ik){//若ki，则该元素就在数组p中，进入p继续查找29.returnselect(p,i,k);30.}else{31.if(i+j=k){//若iki+j，则该元素在q数组中，即值为m32.returnm;33.}else{//若ki+j，则该元素在r数组中，进入r继续寻找34.returnselect(r,s,k-i-j);35.}36.}37.}动态规划1.货郎担#includeiostream#includeiomanipusingnamespacestd;intn;intcost[20][20]={};booldone[20]={1};intstart=0;//从城市0开始intimin(intnum,intcur){if(num==1)//递归调用的出口returncost[cur][start];//所有节点的最后一个节点，最后返回最后一个节点到起点的路径intmincost=10000;for(inti=0;in;i++){coutii:done[i]endl;if(!done[i]&&i!=start)//该结点没加入且非起始点{if(mincost=cost[cur][i]+cost[i][start]){continue;//其作用为结束本次循环。即跳出循环体中下面尚未执行的语句。区别于break}done[i]=1;//递归调用时，防止重复调用intvalue=cost[cur][i]+imin(num-1,i);if(mincostvalue){mincost=value;}done[i]=0;//本次递归调用完毕，让下次递归调用}}returnmincost;}intmain(){//cinn;n=4;intcc[4][4]={{0,4,1,3},{4,0,2,1},{1,2,0,5},{3,1,5,0}};for(inti=0;in;i++){for(intj=0;jn;j++){//cincost[i][j];cost[i][j]=cc[i][j];}}coutimin(n,start)endl;return0;}2.多段图的最短路径voidfgraph(intcost[],intpath[],intd[]){intr,j,temp,min;for(j=0;j=n;j++)cost[j]=0;for(j=n-1;j=1;j--){temp=0;min=c[j][temp]+cost[temp];for(r=0;r=n;r++){if(c[j][r]!=MAX){if((c[j][r]+cost[r])min){min=c[j][r]+cost[r];temp=r;}}}cost[j]=c[j][temp]+cost[temp];d[j]=temp;}path[1]=1;path[k]=n;for(j=2;jk;j++)path[j]=d[path[j-1]];}3.最长公共子序列AlgorithmlcsLength(x,y,b)mx.length-1;ny.length-1;c[i][0]=0;c[0][i]=0;for(inti=1;i=m;i++)for(intj=1;j=n;j++)if(x[i]==y[j])c[i][j]=c[i-1][j-1]+1;b[i][j]=1;elseif(c[i-1][j]=c[i][j-1])c[i][j]=c[i-1][j];b[i][j]=2;elsec[i][j]=c[i][j-1];b[i][j]=3;构造最长公共子序列Algorithmlcs(inti,intj,char[]x,int[][]b){if(i==0||j==0)return;if(b[i][j]==1){lcs(i-1,j-1,x,b);System.out.print(x[i]);}elseif(b[i][j]==2)lcs(i-1,j,x,b);elselcs(i,j-1,x,b);}4.0-1背包问题动态规划法O(nc)m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。voidKnapSack(intv[],intw[],intc,intn,intm[][11]){intjMax=min(w[n]-1,c);for(j=0;j=jMax;j++)/*m(n,j)=00=jw[n]*/m[n][j]=0;for(j=w[n];j=c;j++)/*m(n,j)=v[n]j=w[n]*/m[n][j]=v[n];for(i=n-1;i1;i--){intjMax=min(w[i]-1,c);for(j=0;j=jMax;j++)/*m(i,j)=m(i+1,j)0=jw[i]*/m[i][j]=m[i+1][j];for(j=w[i];j=c;j++)/*m(n,j)=v[n]j=w[n]*/m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}m[1][c]=m[2][c];if(c=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}5.资源分配1.//数组c存放i台机器分配给j号车间可获得的利润2.//数组v存放i台机器分配给前j个车间可获得的最大的利润3.//数组d存放分配给前j个车间的分配数4.intC[N+1][M+1],V[N+1][M+1],D[N+1][M+1];5.//初始化数组6.memset(C,0,sizeof(int));7.memset(V,0,sizeof(int));8.memset(D,0,sizeof(int));9.inti=0,j=0,k=0;10.////////////////////////////这段代码随机产生并输出C[i][j];11.couti台机器分配给j号车间可获得的利润：endl;12.for(i=0;i=M;i++){13.coutsetw(4)