算法设计与分析复习资料

《算法设计与分析复习资料》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析复习资料：1、背包问题的贪心算法：（贪心法）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;         

2、  c - =w[i];           }        if (i<=n) x[i]=c/w[i]; } 2、快速排序（分治法）void QuickSort (Type a[], int p, int r) {       if (p

3、nt n; //皇后个数  int sum = 0; //可行解个数  int x[N]; //皇后放置的列数  int place(int k)  {      int i;      for(i=1;i

4、

5、 x[k] == x[i])          return 0;      return 1;  }  int queen(int t)  {      if(t>n && n>0) //当放置的皇后超过n时，可行解个数

6、加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;  }  1、归并排序voidMergeSort(intarray[],intstart,intend)

7、{      if(start

8、  }}voidMerge(intarray[],intstart,intmid,intend){      inttemp1[10],temp2[10];      intn1,n2;      n1=mid-start+1;      n2=end-mid;   //拷贝前半部分数组      for(inti=0;i

9、temp2[i]=array[mid+i+1];//把后面的元素设置的很大      temp1[n1]=temp2[n2]=1000;   //逐个扫描两部分数组然后放到相应的位置去      for(intk=start,i=0,j=0;k<=end;k++)      {             if(temp1[i]<=temp2[j])             {                    array[k]=temp1[i];                    i++;         

10、    }             else             {                    array[k]=temp2[j];                    j++;             }      }}1、堆排序1.堆  堆实际上是一棵完全二叉树，其任何一非叶节点满足性质： Key[i]<=key[2i+1]&&Key[i]<=key