算法设计报告二.doc

西 安 邮 电 大 学 （计算机学院）算法设计与分析课内实验报告实验名称： 动态规划与贪心算法 专业名称： 网络工程班 级： 学生姓名： 学号（8位）： 指导教师： 实验日期： 2014年 5 月 15 日一. 实验目的及实验环境 目的：进一步掌握动态规划与贪心算法的设计思想，通过实际问题来应用动 态规划与贪心算法。 环境：VC+6.0二. 实验内容1.设计复杂度为O(n)算法，找出由n个数组成的序列的最长单调递增子序列2.将上题的复杂度降为O(nlogn)3.会场安排问题4.多次最优服务次序问题三方案设计1. 这个算法的角度是，遍历一遍原始数组，如果假设当前遍历的元素是第i个，那么只要考虑i号元素之前的最大递增子序列，如果该子序列最后一个元素resultcurLongestLength - 1 arrayi 那么自动把arrayi 加入到变更后的最长递增子序列，由于每一次判断都要遍历i号元素之前所有的j i ，从而获取i之前的最长递增子序列所以时间复杂度为O(n2)。2. 一个长度为i的候选子序列的最后一个元素至少与一个长度为i-1的候选子序列的最后一个元素一样大。每遍历一个元素对结果元素进行二分查找进一步判断是否放入结果数组中。3. 将会场的开始时间以及结束时间存储在二维数组中的第一维，并对开始时间标0，结束时间标1存储在第二维，第一维对升序排序，对第二维0、1状况统计，遇到0 count+,遇到1 count-,遍历后count（max）即为所需会场数4. 将所需时间升序排序，轮流进行，保证时间短的先进行，不会出现短时间的在后面排队等时间长的的情况，以减少总的等待时间。四测试数据及运行结果1. 最长子序列（复杂度O(n)）2. 最长子序列（复杂度O(nlogn)）3. 会场安排问题4. 多处最优服务问题.五总结 要用好一种算法，首先要理解它的思想，就这次实验而言，要理解动态规划与贪心算法思想，清楚算法思想后问题就迎刃而解了。还有就是多练习用动态规划与贪心算法来解决一些实际问题对于更好地掌握动态规划与贪心算法是有很大帮助的。要掌握它，我还要多练习写这方面的程序。六附录：源代码（电子版）1. #include #define N 100 void prin(int i); void fun(int n); int pN,aN; void main() int i,n; printf(input n:); scanf(%d,&n); printf(input the array.n); for(i=0;in;i+) scanf(%d,&ai); fun(n); void fun(int n) int mN; int i,k,max; m0=1; p0=-1; for(i=1;in;i+) max=0; pi=-1; for(k=0;kmax&akai) pi=k; max=mk; mi=max+1; i=0; for(k=1;kmi) i=k; prin(i); printf(nlen=%dn,mi); void prin(int i) if(pi0) printf(%d,ai); return; prin(pi); printf(,%d,ai); 2. #include#include#include#define N 9int arrayN= 2,1,6,3,5,4,8,7,9;int BN;int len;int Bisearch(int *b,int len,int w);int LIS(int *array,int n);int Bisearch(int *b,int len,int w) int left=0,right=len-1; int mid; while(leftw) right=mid-1; else if(bmidw) left=mid+1; else return mid; return left;int LIS(int *array,int n) int i,pos=0; len=1; B0=array0; for(i=1;iBlen-1) Blen=arrayi; +len; else pos=Bisearch(B,len,arrayi); Bpos=arrayi; return len;int main() int i; printf(LIS:%dn,LIS(array,N); for(i=0;ilen;+i) printf(B%d=%dn,i,Bi); 3. #includevoid greedyselector(int a220,int n) int count=1; int i=1; int max=0; for(;imax)max=count; count-; printf(n所需会场数：%dn,max);void sort(int a220,int n) int i,j,min,t; for(i=0;i2*n-1;i+) min=i; for(j=i+1;ja0j) min=j; if(min!=i) t=a0i;a0i=a0min;a0min=t;t=a1i;a1i=a1min;a1min=t; printf(the sorted number is:n);for(i=0;i2*n;i+) printf(%5d,a0i);void main() int n,i=0; int a220; printf(input amount of the meetings:n); scanf(%d,&n); printf(input start time and end time:n); for(i=0;i2*n;i+) scanf(%d,&a0i); a1i=i%2; sort(a,n); greedyselector(a,n);4. #includevoid greedyselector(int a20,int n,int s) int r,i,j=0,t,sum,Sum=0,yushu; r=n/s; for(i=r;i0;i-) sum=0; do sum+=aj; j+; while(j%s!=0); Sum+=i*sum; yushu=n-r*s; for(i=0;iyushu;i+) for(j=i;jr*s;j+=s) t+=aj; Sum+=t; printf(n所需最优服务时间：%dn,Sum/n);void sort(int a20,int n) int i,j,min,t; for(i=0;in-1;i+) min=i; for(j=i+1;jaj) min=j; if(min!=i) t=ai;ai=amin;amin=t; printf(the sorted number is:n);for(i=0;in;i+) printf(%5d,ai);void main() int n,i,s,t20; printf(input people