实验报告

合肥师范学院实验报告册2016/ 2017 学年第 1 学期系别计算机学院实验课程算法设计与分析专业软件工程班级一班姓名杨文皇学号1310421071指导教师程敏实验一：分治算法一、实验目的1、理解分治策略的基本思想；2、掌握用分治法解决问题的一般技巧。

二、实验内容利用分治算法在含有n个不同元素的数组a[n]中同时找出它的最大的两个元素和最小的两个元素，编写出完整的算法，并分析算法的时间复杂度。

三、实验源程序。

1、算法设计思想利用分治法思想，n个不同元素的数组不断进行划分，化为若干个个子问题，其与原问题形式相；解决子问题规模较小而容易解决则直接解决：即当n的规模为只有一个或两个，三个或四个；否则再继续直至更小的子问题：即当n的规模大于四时。

将已求得的各个子问题的解，逐步合并原问题的解：即将左右两边求得的子问题进行比较，在四个数据中的得到两个最大（最小）值。

为了简化空间，采用了对每一个小规模问题的排序，以及合并原问题时，对四个数据进行排序，获得当前或合并的最大（最小）值2、算法实现#include<iostream>using namespace std;int a[10]={4,5,6,2,3,9,8,13,1};int b[4];int sort(int i,int j){int temp,k;for(;i<j;i++){for(k=i;k<j;k++)if(a[k]>a[k+1]){temp=a[k];a[k]=a[k+1];a[k+1]=temp;}}return 0;}int sort1(int lmin1,int lmin2,int rmin1,int rmin2){int i,j,temp;b[0]=lmin1;b[1]=lmin2;b[2]=rmin1;b[3]=rmin2;for(i=0;i<=1;i++)for(j=i;j<=3;j++){if(b[i]>b[j]){temp=b[i];b[i]=b[j];b[j]=temp;}}return 0;}int maxmin(int i,int j,int &fmin1,int &fmin2,int &fmax1,int &fmax2) {int mid;int lmin1,lmin2,lmax1,lmax2;int rmin1,rmin2,rmax1,rmax2;if(i==j || i==j-1){sort(i,j);fmin1=a[i];fmin2=a[i];fmax1=a[j];fmax2=a[j];}elseif(i==j-2 || i==j-3){sort(i,j);fmin1=a[i];fmin2=a[i+1];fmax1=a[j-1];fmax2=a[j];}else{mid=(i+j)/2;maxmin(i,mid,lmin1,lmin2,lmax1,lmax2);maxmin(mid+1,j,rmin1,rmin2,rmax1,rmax2);sort1(lmin1,lmin2,rmin1,rmin2);fmin1=b[0];fmin2=b[1];sort1(lmax1,lmax2,rmax1,rmax2);fmax1=b[2];fmax2=b[3];}return 0;}int main(){int fmin1,fmin2,fmax1,fmax2;int i;maxmin(0,8,fmin1,fmin2,fmax1,fmax2);cout<<endl;cout<<"该组数据为:";for(i=0;i<=8;i++)cout<<a[i]<<" ";cout<<endl<<endl<<"最小值是:"<<fmin1<<"，第二小值是:"<<fmin2<<endl;cout<<endl<<"第二大值是:"<<fmax1<<",最大值是:"<<fmax2<<endl<<endl;return 0;}3、程序结果4、算法分析用T（n）元素表示数，则导出的递推关系式是：在理想的情况下，即每一小规模的子问题中的数据都是递增序列，则:当n<=4时，T（n）=1; 当n>4时，T（n）= T（n/2）+ T（n/2）(均向下取整);在非理想情况下，即每一小规模的子问题中的数据都是递减序列，则：当n=1时，T（n）=1；当n=2时，T（n）=2；当n=3时，T（n）=3；当n=4时，T（n）=6；当n>4时，T（n）= T（n/2）+ T（n/2）(均向下取整)+12。

四、实验总结有待优化之处，任一组数据的同时找到最大的两个元素和最小的两个元素；在不进行排序的情况下，同时找到最大的两个元素和最小的两个元素。

在程序的能运行基础之上，再对程序进行优化，节约时间复杂度。

实验二：贪心算法一、实验目的1、理解贪心算法的基本思想；2、掌握用贪心算法解决问题的一般技巧。

二、实验内容对给定的n位高精度正整数,去掉其中k(k<n)个数字后，按原左右次序将组成一个新的正整数，使得剩下的数字组成的新数最大，编写出完整的算法，并分析算法的时间复杂度。

三、实验源程序。

1、算法设计思想每次从头开始，最多删除S次。

比较相邻两位的数据的大小，若高位比低位大则删除高位，并记录删除的数据所在位置，最后输出需要保留的位数的数据，及删除的数据。

2、算法实现#include <string.h>#include <iostream>#include<stdio.h>using namespace std;void delete1(char n[],int b,int k){int i;for(i=b;i<=strlen(n)-k;i=i+1)n[i] = n[i+k];}int main(){char n[100];int s,i,j,c,len,j1;cout << "请输入n[]=:";cin >> n;cout <<"请输入删除的元素个数s=";cin >> s;len = strlen(n);if(s>len){printf("data error");return 0;}j1=0;for(i=0;i<s;i=i+1){for(j=0;j<strlen(n);j=j+1)if(n[j]<n[j+1]){delete1(n,j,1);break;}if(j==strlen(n))break;}for(i=i-1;i<s;i=i+1){j=len-i-1;delete1(n,j,1);}while(n[0]=='0'&&strlen(n)>1)delete1(n,1,1);cout << n<<endl;return 0;}3、程序结果4、算法分析算法的主要的时间复杂度为处理数据，即贪心算法的部分的时间复杂度为：T（n）=s*len(其中，s表示删除的次数,len表示数据的长度)。

四、实验总结有待优化之处：对任意输入的数据进行多次的不同次数的删除，且在程序的运行基础之上，优化程序的时间、空间复杂度。

可行的发算法为：删除字符后不再从头开始比较，而是向前一位比较。

实验三：动态规划算法一、实验目的1、理解动态规划算法的基本思想；2、掌握用动态规划算法解决问题的一般技巧。

二、实验内容用动态规划求数列的最大子段和。

给定n个元素的整数列(可能为负整数)a1，a2，…，an，求形如ai，ai+1，aj，i，j=1，2，…，n，i<=j的子段，使其和为最大。

编写出完整的算法，并分析算法的时间复杂度。

三、实验源程序。

1、算法设计思想b[j]=max{a[i]++a[j]},1<=i<=j,且1<=j<=n,则所求的最大子段和为max b[j]，1<=j<=n。

由b[j]的定义可易知，当b[j-1]>0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]。

故b[j]的动态规划递归式为:b[j]=max(b[j-1]+a[j],a[j])，1<=j<=n。

2、算法实现#include <iostream>#include <vector>using namespace std;int MaxSum(int *v,int n){int sum=0,b=0;int i;for (i=1;i<=n;i++){if(b>0)b+=v[i];elseb=v[i];if(b>sum)sum=b;}return sum;}int main(){int p[10]={4,11,-9,13,-8,-3};cout<<"该数列是:"<<endl;for(int i=0;i<=5;i++){cout<<p[i]<<endl;}cout<<"数列的最大子段和是:"<<MaxSum(p,6)<<endl;return 0;}3、程序结果4、算法分析该算法的时间复杂度为:T(n)=O(n)。

四、实验总结优化之处，可以将对任意一数列用动态规划算法，对其进行求最大子段和。

注意程序的可读性，以及优化程序的时间、空间复杂度。

实验四：回溯算法一、实验目的1、理解回溯法的基本思想；2、掌握用回溯法解决问题的一般技巧。

二、实验内容给定正数wi(1≤i≤n)和m，要求寻找wi的所有子集，它们的和为m。

例如，如果n=4、（w1,w2,w3,w4）=（11，13，24，7）且m=31，那么想得到的子集为（11，13，7）和（24，7）。

编写出完整的算法，并分析算法的时间复杂度。

三、实验源程序。

1、算法设计思想确定问题的解空间；确定节点的拓展规则；搜索解空间。

从根节点开始，一深度优先的方式搜索整个空间。

这个开始的节点成为一个活的节点，同时也成为当前的拓展节点。

在当前的拓展节点处，搜索向纵深方向移至一个新的节点。