实验1 分治法 实验目的： 1. 掌握合并排序的基本思想 2. 掌握合并排序的实现方法 3. 学会分析算法的时间复杂度 4. 学会用分治法解决实际问题 实验内容： 分治法求几个大小不同整数的最大最小元。 主要仪器设备： 华硕笔记本、visual stdio2013 上机调试修改源程序： #include #include #define N 5 using namespace std; void getData(int a[], int n) { time_t t; srand((unsigned)time(&t)); int i; for (i = 0; i < n; i++) a[i] = rand() % 100; } void MaxMin(int i, int j, int l[],int &max, int &min) { int maxl, minl; if (i == j) max = min = l[j]; else if (i == j - 1) { if (l[i] < l[j]) { max = l[j]; min = l[i]; } else { max = l[i]; min = l[j]; } } else { int m = (i + j) / 2; MaxMin(i, m, l, max, min); MaxMin(m + 1, j, l, maxl, minl); if (max < maxl) max = maxl; if (min>minl) min = minl; } } void main() { int l[N], max, min; getData(l,N); for (int i = 0; i < N; i++) cout << l[i] << \ cout << endl; MaxMin(0, 4, l, max, min); cout << \ \} 输出结果： 讨论、心得（可选）: 分治算法是很有用的算法效率很高，分治法的设计一般是递归的。两路合并排序是一个典型的分治算法，其基本运算为元素比较，最坏情况下的时间为W(n)=O(nlogn)，在排序过程中需要使用与原序列相同长度的辅助数组temp，因此它所需的额外空间为O(n)。通过编写代码，我很好的掌握了分治法的步骤：划分；求解子问题；合并。对“分治策略”有了更深的体会，它将原问题划分为彼此独立的、规模较小而结构相同的子问题。 实验2贪心法 实验目的： 1.掌握贪心算法的基本思想 2.掌握贪心算法的典型问题求解 3.进一步多级调度的基本思想和算法设计方法 4.学会用贪心法分析和解决实际问题 实验内容： 利用贪心法来解决背包问题，使得具有有限空间的背包具有最大的价值。 主要仪器设备： 华硕笔记本、visual stdio2013 上机调试修改源程序： #include using namespace std; void DP(int c[50][50],int w[50],int v[50],int n,int C) { for(int i=0;i<=C;i++) { c[0][i]=0; } for(int t=1;t<=n;t++) { c[t][0]=0; for(int j=1;j<=C;j++) { if(w[t]<=j) { if(v[t]+c[t-1][j-w[t]]>c[t-1][j]) c[t][j]=v[t]+c[t-1][j-w[t]]; else c[t][j]=c[t-1][j]; } else c[t][j]=c[t-1][j]; } } } void Output(int c[50][50],int x[50],int w[50],int n,int C) { for(int k=n;k>=2;k--) { if(c[k][C]==c[k-1][C]) x[k]=0; else { x[k]=1; C=C-w[k]; } } x[1]=c[1][C]?1:0; } int main()