算法导论习题

2-1：//在合并排序中对小数组采用插入排序#include<stdio.h>voidmain(){voidMERGE_SORT(inta[],intp,intr,intk); inta[12];//={3,0,1,10,9,5,4,12,7,8,2,6}; intk=3,n=12; inti,j,s; inttmp=0;printf("请输入12个正整数：\n"); for(i=0;i<12;i++)scanf("%d",&a[i]); for(i=0;i<=3;i++) { for(j=i*3+1;j<i*3+3;j++) { s=j; while(s>=i*3+1) {if(a[s]<a[s-1]) tmp=a[s],a[s]=a[s-1],a[s-1]=tmp; s--; } } } printf("第一步对4个长度3的子列表进行插入排序的结果为：\n"); for(i=0;i<12;i++) printf("%d,",a[i]); printf("\n"); MERGE_SORT(a,0,3,3); printf("第二步对4个子列表进行合并排序的结果为：\n");for(i=0;i<12;i++) printf("%d,",a[i]);printf("\n");}voidMERGE_SORT(inta[],intp,intr,intk){voidMERGE(inta[],intp,intq,intr,intk); intq; if(p<r) { q=(p+r)/2; MERGE_SORT(a,p,q,k); MERGE_SORT(a,q+1,r,k); MERGE(a,p,q,r,k); }}voidMERGE(inta[],intp,intq,intr,intk){ intn1=(q-p+1)*k,n2=(r-q)*k; inti,j,s; int*L=newint[n1]; int*R=newint[n2]; for(i=0;i<n1;i++) L[i]=a[p*k+i]; for(j=0;j<n2;j++) R[j]=a[(q+1)*k+j]; i=0; j=0; for(s=p*3;s<=(r+1)*3-1;s++) { if(i>n1-1) a[s]=R[j++]; elseif(j>n2-1) a[s]=L[i++]; elseif(L[i]<R[j]) a[s]=L[i++]; else a[s]=R[j++]; }}2-4：//用分治法在数组中查找逆序对#include<stdio.h>voidmain(){ intcount_inversion(inta[],intp,intr); inta[5]={5,4,3,2,1};printf("数组的逆序对是%d个\n",count_inversion(a,0,4));}intmerge_inversion(inta[],intp,intq,intr){intn1=q-p+1;intn2=r-q;int*L=newint[n1];int*R=newint[n2];inti,j,k,v;for(i=0;i<n1;++i)L[i]=a[p+i];for(j=0;j<n2;++j)R[j]=a[q+1+j];i=0;j=0;v=0;for(k=p;k<=r;++k){if(i>n1-1)a[k]=R[j++];elseif(j>n2-1)a[k]=L[i++];elseif(L[i]>R[j]){a[k]=R[j++];v+=n1-i;}elsea[k]=L[i++];}deleteL;deleteR;returnv;}intcount_inversion(inta[],intp,intr){intv=0,q;if(p<r){q=(p+r)/2;v+=count_inversion(a,p,q);v+=count_inversion(a,q+1,r);v+=merge_inversion(a,p,q,r);}returnv;}6-1：//用插入方法建堆#include"stdio.h"voidHEAP_INCREASE_KEY(inta[],inti,intkey){ inttmp; if(key>a[i-1]) a[i-1]=key; while(i>1&&a[i/2-1]<a[i-1]) { tmp=a[i/2-1],a[i/2-1]=a[i-1],a[i-1]=tmp; i=i/2; }}voidMAX_HEAP_INSERT(inta[],intkey,intheap_size){ heap_size+=1; a[heap_size-1]=0; HEAP_INCREASE_KEY(a,heap_size,key);}voidBUILD_MAX_HEAP(inta[],intlengh){ intheap_size=1; inti; for(i=2;i<=lengh;i++) { MAX_HEAP_INSERT(a,a[i-1],heap_size); heap_size++;//堆的长度要随着循环的次数增长 }}voidmain(){ intj; inta[10]={15,84,62,16,29,35,6,18,9,17}; BUILD_MAX_HEAP(a,10); for(j=0;j<10;j++) printf("%d\n",a[j]);}6-2c：#include"stdio.h"voidMAX_D_HEAPIFY(inta[],inti,intd,intheap_size){ intn=d,j,largest; inttmp; int*child=newint[n]; for(j=0;j<n;j++) child[j]=(i-1)*d+2+j; if(child[0]<=heap_size&&a[child[0]-1]>a[i-1]) largest=child[0]; else largest=i; for(j=1;j<n;j++) { if(child[j]<=heap_size&&a[child[j]-1]>a[largest-1]) largest=child[j]; } if(largest!=i) { tmp=a[largest-1],a[largest-1]=a[i-1],a[i-1]=tmp; MAX_D_HEAPIFY(a,largest,d,heap_size); }}voidBUILD_MAX_D_HEAP(inta[],intd,intheap_size){ inti,j; j=heap_size%d; if(j==0||j==1) i=heap_size/d; else i=heap_size/d+1;//由叶子节点求父节点有两种情况 for(i;i>=1;i--) MAX_D_HEAPIFY(a,i,d,heap_size);}intEXTRACT_MAX(inta[],intd,intheap_size){ inttmp; tmp=a[heap_size-1];a[heap_size-1]=a[0];a[0]=tmp; heap_size--; MAX_D_HEAPIFY(a,1,d,heap_size); returna[heap_size];}voidmain(){ inta[20]={52,47,16,58,23,26,14,18,59,68,47,19,35,29,61,82,74,75,98,81};//intb[18]={25,11,15,9,8,17,21,40,18,11,10,20,14,15,19,21,7,10}; intd=5,j,largest; BUILD_MAX_D_HEAP(a,5,20);//BUILD_MAX_D_HEAP(b,5,18); for(j=0;j<20;j++) printf("%d\n",a[j]);largest=EXTRACT_MAX(a,5,20);for(j=0;j<20;j++) printf("%d\n",a[j]); printf("%d\n",largest);/*for(j=0;j<18;j++) printf("%d\n",b[j]);*/6-2d：#include"stdio.h"voidMAX_D_HEAPIFY(inta[],inti,intd,intheap_size){ intn=d,j,largest; inttmp; int*child=newint[n]; for(j=0;j<n;j++) child[j]=(i-1)*d+2+j; if(child[0]<=heap_size&&a[child[0]-1]>a[i-1]) largest=child[0]; else largest=i; for(j=1;j<n;j++) { if(child[j]<=heap_size&&a[child[j]-1]>a[largest-1]) largest=child[j]; } if(largest!=i) { tmp=a[largest-1],a[largest-1]=a[i-1],a[i-1]=tmp; MAX_D_HEAPIFY(a,largest,d,heap_size); }}voidBUILD_MAX_D_HEAP(inta[],intd,intheap_size){ inti,j; j=heap_size/d; if(j==0||j==1) i=heap_size/d; else i=heap_size/d+1;//由叶子节点求父节点有两种情况 for(i;i>=1;i--) MAX_D_HEAPIFY(a,i,d,heap_size);}voidHEAP_INCREASE_KEY(inta[],inti,intd,intkey){ inttmp,j; if(a[i-1]<=key) a[i-1]=key; while(i>1) { if(i%d==0||i%d==1) j=i/d; else j=i/d+1; if(a[j-1]<a[i-1]) { tmp=a[j-1],a[j-1]=a[i-1],a[i-1]=tmp; i=j; } elsebreak; }}voidINSERT(inta[],intkey,intd,intheap_size){ heap_size+=1; a[heap_size-1]=0;HEAP_INCREASE_KEY(a,heap_size,d,key);}voidmain(){inta[20]={52,47,16,58,23,26,14,18,59,68,47,19,35,29,61,82,74,75,98,81}; intj,s=0;BUILD_MAX_D_HEAP(a,5,19);for(j=0;j<20;j++) { printf("%d,",a[j]); s+=1; if(s%6==0) printf("\n"); }INSERT(a,a[19],5,19); s=0;printf("\n");for(j=0;j<20;j++) { printf("%d,",a[j]); s+=1; if(s%6==0) printf("\n"); }}6-2e：#include"stdio.h"voidMAX_D_HEAPIFY(inta[],inti,intd,intheap_size){ intn=d,j,largest; inttmp; int*child=newint[n]; for(j=0;j<n;j++) child[j]=(i-1)*d+2+j; if(child[0]<=heap_size&&a[child[0]-1]>a[i-1]) largest=child[0]; else largest=i; for(j=1;j<n;j++) { if(child[j]<=heap_size&&a[child[j]-1]>a[largest-1]) largest=child[j]; } if(largest!=i) { tmp=a[largest-1],a[largest-1]=a[i-1],a[i-1]=tmp; MAX_D_HEAPIFY(a,largest,d,heap_size); }}voidBUILD_MAX_D_HEAP(inta[],intd,intheap_size){ inti,j; j=heap_size/d; if(j==0||j==1) i=heap_size/d; else i=heap_size/d+1;//由叶子节点求父节点有两种情况 for(i;i>=1;i--) MAX_D_HEAPIFY(a,i,d,heap_size);}voidHEAP_DECREASE_KEY(inta[],inti,intd,intkey,intheap_size){ if(a[i-1]>=key) a[i-1]=key;MAX_D_HEAPIFY(a,i,d,heap_size);}voidmain(){inta[20]={52,47,16,58,23,26,14,18,59,68,47,19,35,29,61,82,74,75,98,81}; intkey=1,s=0,j;BUILD_MAX_D_HEAP(a,5,20);for(j=0;j<20;j++) { printf("%d,",a[j]); s+=1; if(s%6==0) printf("\n"); }printf("\n"); s=0;HEAP_DECREASE_KEY(a,3,5,key,20);for(j=0;j<20;j++) { printf("%d,",a[j]); s+=1; if(s%6==0) printf("\n"); }}6-5-7：#include"stdio.h"voidmain(){ //inta[10]={6,4,12,7,9,11,5,13,18,8}; inta[10]={20,18,17,14,16,10,8,9,8,15};inti=9,j; intheap_size;voidBULD_MAX_HEAP(inta[]);intHEAP_DELETE(inta[],inti); BULD_MAX_HEAP(a); heap_size=HEAP_DELETE(a,i); printf("删除第i个元素后的堆是：\n"); for(j=0;j<heap_size;j++) printf("%d\n",a[j]);}voidBULD_MAX_HEAP(inta[]){voidMAX_HEAPIFY(inta[],intj,intheap_size); intheap_size=10; intj; for(j=4;j>=0;j--) MAX_HEAPIFY(a,j,heap_size);printf("堆a是：\n");for(j=0;j<heap_size;j++) printf("%4d",a[j]);printf("\n");}voidMAX_HEAPIFY(inta[],intj,intheap_size){ intleft=2*(j+1); intright=2*(j+1)+1;//结点与数组下标之间要转换 intlargest=0,temp; if(left<=heap_size&&a[left-1]>a[j]) largest=left-1;else largest=j; if(right<=heap_size&&a[right-1]>a[largest]) largest=right-1; if(largest!=j) { temp=a[largest];a[largest]=a[j];a[j]=temp; MAX_HEAPIFY(a,largest,heap_size); }}intHEAP_DELETE(inta[],inti){ inttemp,key=a[9],key1=a[i-1]; intheap_size=10;temp=a[9];a[9]=a[i-1];a[i-1]=temp;heap_size--; if(key>key1) { while(i>1&&a[i/2-1]<a[i-1])//如果a[9]大于i结点的值，则通过不断与父结点的比较//来确它的位置 { temp=a[i/2-1],a[i/2-1]=a[i-1],a[i-1]=temp; i=i/2; } } else MAX_HEAPIFY(a,i-1,heap_size);//如果a[9]比i结点的值要小，则从i结点开始堆维护 returnheap_size;}6-最小堆：//建立最小堆#include"stdio.h"voidMIN_HEAPIFY(inta[],inti,intheap_size){ intsmall,tmp; intleft=2*i,right=2*i+1; if(left<=heap_size&&a[left-1]>a[i-1]) small=left; else small=i; if(right<=heap_size&&a[right-1]>a[small-1]) small=right; if(small!=i) { tmp=a[small-1],a[small-1]=a[i-1],a[i-1]=tmp; MIN_HEAPIFY(a,small,heap_size); }}voidBUILD_MIN_HEAP(inta[],intheap_size){ inti; for(i=(heap_size/2);i>=1;i--) MIN_HEAPIFY(a,i,heap_size);}voidHEAPSORT(inta[],intlengh){ inti,tmp; intheap_size=lengh;BUILD_MIN_HEAP(a,heap_size); for(i=lengh;i>=2;i--) { tmp=a[i-1],a[i-1]=a[0],a[0]=tmp; heap_size--;MIN_HEAPIFY(a,1,heap_size); }}voidmain(){ inta[10]={23,6,21,3,7,5,8,54,14,10}; inti; HEAPSORT(a,10); for(i=0;i<10;i++) printf("%d\n",a[i]);}7-1：//PARTITION的最初版本#include"stdio.h"intHOARE_PARTITION(inta[],intp,intr){ intx,tmp; inti,j; x=a[p-1]; i=p-1; j=r+1; while(1) { while(a[--j-1]>x); while(a[++i-1]<x); if(i<j) tmp=a[i-1],a[i-1]=a[j-1],a[j-1]=tmp; else returnj; }}voidQUICK_SORT(inta[],intp,intr){ intq; if(p<r) { q=HOARE_PARTITION(a,p,r);QUICK_SORT(a,p,q);QUICK_SORT(a,q+1,r); }}voidmain(){ inti; inta[20]={10,58,46,23,26,48,47,59,68,23,12,19,17,24,43,81,76,72,98,46}; QUICK_SORT(a,1,20);for(i=0;i<20;i++) printf("%d\n",a[i]);}7-4-5：/*对插入排序来说，当其输入已“几乎”排好序时，运行时间是很快的。在实践中，可以充分利用这一特点来改善快速排序的运行时间。当在一个长度小于k的子数组上调用快速排序时，不让他做任何排序就返回。当顶层的快速排序调用返回后，堆对整个数组运行插入排序来完成排序过程。证明这一排序算法的期望运行时间是O(nk+nlg(n/k))。在理论上和实践中，应如何选择k?*/#include"stdio.h"intPARTITION(inta[],intp,intr){ inti=p-1,j; intx,tmp; x=a[r-1]; for(j=p;j<r;j++) { if(a[j-1]<=x) { i++; tmp=a[j-1],a[j-1]=a[i-1],a[i-1]=tmp; } } i++; tmp=a[r-1],a[r-1]=a[i-1],a[i-1]=tmp; returni;}voidQUICK_SORT(inta[],intp,intr,intk){ intq; if(r-p>k) { q=PARTITION(a,p,r);QUICK_SORT(a,p,q-1,k);QUICK_SORT(a,q+1,r,k); }}voidINSERT_SORT(inta[],intlength){ inti,j; inttmp; for(i=1;i<length;i++) { j=i; while(j>0&&a[j-1]>=a[j]) { tmp=a[j-1],a[j-1]=a[j],a[j]=tmp; j--; } }}voidQUICK_INSERT_SORT(inta[],intlength,intk){ if(length>k) { QUICK_SORT(a,1,length,k); INSERT_SORT(a,length); } else INSERT_SORT(a,length);}voidmain(){ inti,k=5; inta[20]={10,58,46,23,26,48,47,59,68,23,12,19,17,24,43,81,76,72,98,46};QUICK_INSERT_SORT(a,20,k);for(i=0;i<20;i++) printf("%d\n",a[i]);}7-4-6：/*考虑对PARTITION过程做这样的修改：从数字A中随机的选出三个元素，并围绕着三个数的中数（即这三个元素的中间值）对它们进行划分。求出以a的函数形式表示的、最坏情况中a:a(1-a)划分的近似概率。*/#include"stdio.h"#include"stdlib.h"intPARTITION(inta[],intp,intr){ inti=p-1,j; intb[3],tmp,x; for(j=0;j<3;j++) b[j]=(int)rand()%(r-p+1)+p; if(a[b[0]-1]>a[b[1]-1]) tmp=a[b[0]-1],a[b[0]-1]=a[b[1]-1],a[b[1]-1]=tmp; if(a[b[1]-1]>a[b[2]-1])tmp=a[b[1]-1],a[b[1]-1]=a[b[2]-1],a[b[2]-1]=tmp; if(a[b[0]-1]>a[b[1]-1]) tmp=a[b[0]-1],a[b[0]-1]=a[b[1]-1],a[b[1]-1]=tmp; tmp=a[r-1],a[r-1]=a[b[1]-1],a[b[1]-1]=tmp; x=a[r-1]; for(j=p;j<r;j++) { if(a[j-1]<=x) { i++; tmp=a[j-1],a[j-1]=a[i-1],a[i-1]=tmp; } } i++; tmp=a[r-1],a[r-1]=a[i-1],a[i-1]=tmp; returni;}voidQUICK_SORT(inta[],intp,intr){ intq; if(p<r) { q=PARTITION(a,p,r);QUICK_SORT(a,p,q-1);QUICK_SORT(a,q+1,r); }}voidmain(){ inti; inta[20]={10,58,46,23,26,48,47,59,68,23,12,19,17,24,43,81,76,72,98,46}; QUICK_SORT(a,1,20);for(i=0;i<20;i++) printf("%d\n",a[i]);}7-4：随机快速排序：//随机化快速排序#include"stdio.h"#include"stdlib.h"intPARTITION(inta[],intp,intr){ inti=p-1,j; intx,tmp; x=a[r-1]; for(j=p;j<r;j++) { if(a[j-1]<=x) { i++; tmp=a[j-1],a[j-1]=a[i-1],a[i-1]=tmp; } } i++; tmp=a[r-1],a[r-1]=a[i-1],a[i-1]=tmp; returni;}intRANDOMIZED_PARTITION(inta[],intp,intr){ inti; inttmp; i=(int)rand()%(r-p+1)+p; tmp=a[r-1],a[r-1]=a[i-1],a[i-1]=tmp; returnPARTITION(a,p,r);}voidRANDOMIZED_QUICKSORT(inta[],intp,intr){ intq; if(p<r) { q=RANDOMIZED_PARTITION(a,p,r);RANDOMIZED_QUICKSORT(a,p,q-1);RANDOMIZED_QUICKSORT(a,q+1,r); }}voidmain(){ inti; inta[20]={10,58,46,23,26,48,47,59,68,23,12,19,17,24,43,81,76,72,98,46};/*for(j=1;j<=10;j++) {i=(int)rand()%7+4; printf("%4d",i); }*/RANDOMIZED_QUICKSORT(a,1,20); for(i=0;i<20;i++) printf("%d\n",a[i]);}8-2-4：#include"stdio.h"intCOUNTING_SORT(inta[],intb[],intk,intn,intx,inty){ inti; int*c=newint[k+1]; for(i=0;i<=k;i++) c[i]=0; for(i=0;i<n;i++) c[a[i]]++; for(i=1;i<=k;i++) c[i]+=c[i-1];/*for(i=n-1;i>=0;i--)//i从n-1到0是为了不改变相同元素的相对顺序，基数排序的稳定性 { b[c[a[i]]-1]=a[i];//这个地方要减一，c[a[i]]表示a[i]在数组中的排序数，放在b数组中要减一 c[a[i]]--; }*/ returnc[y]-c[x-1];}voidmain(){ inta[20];//={12,3,2,5,4,6,7,8,8,6,5,4,9,7,0,14,14,15,16,12},b[20]={0}; intb[20]; inti,k,s; printf("Inputk:\n");scanf("%d",&k); printf("Input20positivenumbersranged0tok:\n"); for(i=0;i<20;i++) scanf("%d",&a[i]); s=COUNTING_SORT(a,b,20,20,4,18);// printf("Thesortednumbers:\n");//for(i=0;i<20;i++)// printf("%d\n",b[i]); printf("%d",s);}8-2-e：#include"stdio.h"voidCOUNTING_SORT(inta[],intk,intn){ inti,tmp; int*c=newint[k+1]; for(i=0;i<=k;i++) c[i]=0; for(i=0;i<n;i++) c[a[i]]++; for(i=1;i<=k;i++) c[i]+=c[i-1]; for(i=n-1;i>0;i--) { if(i!=(c[a[i]]-1)) { tmp=a[i],a[i]=a[c[a[i]]-1],a[c[a[i]]-1]=tmp; c[a[i]]--; i++; } }}voidmain(){ inta[20]={12,3,2,5,4,6,7,8,8,6,5,4,9,7,0,14,14,15,16,12}; inti,k;// printf("Inputk:\n");//scanf("%d",&k);// printf("Input20positivenumbersranged0tok:\n");// for(i=0;i<20;i++)// scanf("%d",&a[i]);COUNTING_SORT(a,20,20);// printf("Thesortednumbers:\n");for(i=0;i<20;i++) printf("%d\n",a[i]);}8-3-4#include"stdio.h"voidRADIX_SORT(inta[],intd[],intn){ int*c=newint[n+1]; int*b=newint[n]; inti; for(i=0;i<=n;i++) c[i]=0; for(i=0;i<n;i++) c[a[i]%n]++; for(i=1;i<n;i++) c[i]+=c[i-1]; for(i=n-1;i>=0;i--) { b[c[a[i]%n]-1]=a[i]; c[a[i]%n]--; }for(i=0;i<=n;i++) c[i]=0; for(i=0;i<n;i++) c[(b[i]/n)%n]++; for(i=1;i<n;i++) c[i]+=c[i-1];for(i=n-1;i>=0;i--) { d[c[(b[i]/n)%n]-1]=b[i]; c[(b[i]/n)%n]--; }}voidmain(){ intn=10; inti; //inta[10]={58,40,15,42,43,69,49,19,52,13},d[10]={0}; int*a=newint[n]; int*d=newint[n]; printf("Inputn:\n"); scanf("%d",&n); printf("Inputnpositivenumbersranged0ton*n-1:\n"); for(i=0;i<n;i++) scanf("%d",&a[i]); RADIX_SORT(a,d,n); for(i=0;i<n;i++) printf("%4d",d[i]);}9-2-3：//写出RANDOMIZED-SELECT的一个迭代版本#include"stdio.h"#include"stdlib.h"intRANDOMIZED_PARTITION(inta[],intp,intr){ inti,j,x; inttmp; i=rand()%(r-p+1)+p;tmp=a[i-1],a[i-1]=a[r-1],a[r-1]=tmp; x=a[r-1]; i=p-1; for(j=p-1;j<r-1;j++) { if(a[j]<=x) { i++; tmp=a[i-1],a[i-1]=a[j],a[j]=tmp; } } i++; tmp=a[r-1],a[r-1]=a[i-1],a[i-1]=tmp; returni;}intRANDOMIZED_SELECT(inta[],intp,intr,inti){ intq,k; while(1) { if(p==r) returna[p-1]; q=RANDOMIZED_PARTITION(a,p,r); k=q-p+1; if(i==k) returna[q-1]; elseif(i<k) r=q-1; else { p=q+1; i=i-k; } }}voidmain(){ inta[20]={45,28,17,46,39,58,49,14,13,98,6,75,40,36,30,9,4,54,71,25}; inti,key; key=RANDOMIZED_SELECT(a,1,20,2); printf("%d\n",key);}9-3-7：#include"stdio.h"intPARTITION(inta[],intp,intr){ intx,i,j,tmp; x=a[r-1]; i=p-1; for(j=p-1;j<r-1;j++) { if(a[j]<=x) { i++; tmp=a[j],a[j]=a[i-1],a[i-1]=tmp; } } i++; tmp=a[r-1],a[r-1]=a[i-1],a[i-1]=tmp; returni;}intRANDOMIZED_SELECT(inta[]