算法设计与分析复习资料.docxVIP

算法设计与分析复习资料：背包问题的贪心算法：（贪心法）void?Knapsack(int?n,float?M,float?v[],float?w[],float?x[])?{? ?Sort(n,v,w);??int?i;? ?for?(i=1;i=n;i++)?x[i]=0;??float?c=M;? ?for?(i=1;i=n;i++)?{??if?(w[i]c)?break;??x[i]=1;??c?-?=w[i];??}? ?if?(i=n)?x[i]=c/w[i];?}? 快速排序（分治法）void?QuickSort?(Type?a[],?int?p,?int?r)? {? ?if?(pr)?{? ?int?q=Partition(a,p,r);? ?QuickSort?(a,p,q-1);?//对左半段排序?QuickSort?(a,q+1,r);?//对右半段排序?}?}?n后问题（回溯法）int?n;?//皇后个数 int?sum?=?0;?//可行解个数 int?x[N];?//皇后放置的列数 int?place(int?k){?int?i;?for(i=1;ik;i++)?if(abs(k-i)==abs(x[k]-x[i])?||?x[k]?==?x[i])?return?0;?return?1;}int?queen(int?t){?if(tn??n0)?//当放置的皇后超过n时，可行解个数加1，此时n必须大于0?sum++;?else ?for(int?i=1;i=n;i++)?{?x[t]?=?i;?//标明第t个皇后放在第i列 ?if(place(t))?//如果可以放在某一位置，则继续放下一皇后 ?queen(t+1);?}?return?sum;}归并排序void MergeSort(int array[], int? start, int? end){?if (start end)?{?int i;?i = (end + start) / 2;??????????//对前半部分进行排序?MergeSort(array, start, i);?????????????//对后半部分进行排序?MergeSort(array, i + 1, end);?????????????//合并前后两部分?Merge(array, start, i, end);?}}void Merge(int? array[], int start, int? mid, int end){?int temp1[10], temp2[10];?int n1, n2;?n1 = mid - start + 1;?n2 = end - mid;???//拷贝前半部分数组?for (int i = 0; i n1; i++)?temp1[i] = array[start + i];???//拷贝后半部分数组?for (int? i = 0; i n2; i++)?temp2[i] = array[mid + i + 1];//把后面的元素设置的很大?temp1[n1] = temp2[n2] = 1000;???//逐个扫描两部分数组然后放到相应的位置去?for (int? k = start, i = 0, j = 0; k = end; k++)?{?if (temp1[i] = temp2[j])?{?array[k] = temp1[i];?i++;?}?else?{?array[k] = temp2[j];?j++;?}?}}堆排序1.堆?堆实际上是一棵完全二叉树，其任何一非叶节点满足性质： Key[i]=key[2i+1]Key[i]=key[2i+2]或者Key[i]=Key[2i+1]key=key[2i+2] 即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。 堆分为大顶堆和小顶堆，满足Key[i]=Key[2i+1]key=key[2i+2]称为大顶堆，满足 Key[i]=key[2i+1]Key[i]=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。2.堆排序的思想 利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。 其基本思想为(大顶堆)： 1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区； 2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]=R[n];? 3)由于交换后新的堆顶R[1]可能违反堆的性