算法试卷_答案ypf

优先选择顺序:要优先选择分治算法,回溯算法,贪心算法,动态规划算法和分支限界算法一、给定一个含有n个元素的集合，且存放在一维数组A[1…n]中，试利用分治算法设计算法，找出集合中前k个最小的元素，且结果存放在A[1….k]中。要求：给定任意的k（1=k=n），最好的时间复杂度为O（n）.假设：1）集合中没有重复的元素2）k不是常量，而是通过参数带入的参数3）前k个最小元素不需要排序思路分析:分治法的基本思想：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。利用快速排序的分治基本思想：设当前待数组的无序区为R[low..high]，需要查找前k个小的元素,数组长度为n.利用分治法可将问题的基本思想描述为：(1)分解在R[low..high]中任选一个记录作为基准（Pivot），以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1]和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均=基准记录的关键字pivot.key，右边的子区间中所有记录的关键字均=pivot.key，而基准记录pivot则位于正确的位置（pivotpos）上，它无须参加后续的排序。如果当前的基准位置恰好等于K,则无需进行第二步的快速排序,直接返回结果即可.(2)求解通过递归调用快速排序,如果当前的基准小于K则在K到high之间继续进行一次快速排序,找到K所在的位置,如果大于K,则在low-k之间继续进行一次快速排序,找打K所在的位置.(3)组合因为当“求解”步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，“组合”步骤无须做什么，可看做是空操作。//分治思想中的快速排序程序代码利用分治策略，在n个不同元素中找出第k个最小元素代码如下：#includestdio.h//一次快速排序intpartition(ints[],intlow,inthigh){if(lowhigh)return0;if(low==high)returnlow;s[0]=s[low];while(lowhigh){while(lowhigh&&s[high]s[0])high--;if(lowhigh)s[low++]=s[high];while(lowhigh&&s[low]s[0])low++;if(lowhigh)s[high--]=s[low];}s[low]=s[0];returnlow;}//分治找K-thNumberintSelect(ints[],intlow,inthigh,intk){//得到中间数的下标inti=partition(s,low,high);//j为左区间长度intj=i-low+1;//位置大就在左区间找，否则就在右区间找if(j==k)returns[i];elseif(kj)returnSelect(s,low,i,k);elsereturnSelect(s,i+1,high,k-j);}intmain(){intn;intlow,high,k;inta[20];printf(请输入数目\n);scanf(%d,&n);printf(请输入数据:\n);for(inti=1;i=n;i++)scanf(%d,&a[i]);printf(\n);printf(请输入第几个最小值:\n);scanf(%d,&k);printf(第%d个最小的数为:%d\n,k,Select(a,1,n,k));}二、动态规划算法在一个由n个数字组成的数字串中插入r个乘号（1=rn16），使它分成r+1个整数，找出一种乘号的插入方法，使得这r+1个整数的乘积最大，试用动态规划算法解决此问题，并分析算法的时间复杂度。算法分析:1.建立递推关系2.设f(i,k)表示在前i位数中插入k个乘号所得乘积的最大值，a(i,j)表示从第i个数字到第j个数字所组成的j-i+1(i=j)位整数值。为了寻求递推关系，先看一个实例：对给定的847313926，如何插入r=5个乘号，使其乘积最大？我们的目标是为了求取最优值f(9,5)。①设前8个数字中已插入4个乘号，则最大乘积为f(8,4)*6；②设前7个数字中已插入4个乘号，则最大乘积为f(7,4)*26；③设前6个数字中已插入4个乘号，则最大乘积为f(6,4)*926；④设前5个数字中已插入4个乘号，则最大乘积为f(5,4)*3926；比较最大值即为f(9,5)。依此类推，为了求f(8,4)：①设前7个数字中已插入3个乘号，则最大乘积为f(7,3)*2；②设前6个数字中已插入3个乘号，则最大乘积为f(6,3)*92；③设前5个数字中已插入3个乘号，则最大乘积为f(5,3)*392；④设前4个数字中已插入3个乘号，则最大乘积为f(4,3)*1392；比较以上4个数值的最大值即为f(8,4)。一般地，为了求取f(i,k)，考察数字串的前i个数字，设前j(k=ji)个数字中已插入k-1个乘号的基础上，在第j个数字后插入第t个乘号，显然此时的最大乘积为f(j,k-1)*a(j+1,i)。于是可以得递推关系式：f(i,k)=max(f(j,k-1)*a(j+1,i))(k=ji)前j个数字没有插入乘号时的值显然为前j个数字组成的整数，因而得边界值为：f(j,0)=a(1,j)(1=j=i)为简单计，在程序设计中省略a数组，用变量d替代。构造最优解为了能打印相应的插入乘号的乘积式，设置标注位置的数组t(k)与c(i,k)，其中c(i,k)为相应的f(i,k)的第k个乘号的位置，而t(k)标明第k个乘号“*”的位置，例如，t(2)=3，表示第2个“*”号在第3个数字后面。当给数组元素赋值f(i,k)=f(j,k-1)*d时，作相应赋值c(i,k)=j，表示f(i,k)的第k个乘号的位置是j。在求得f(n,r)的第r个乘号位置t(r)=c(n,r)=j的基础上，其他t(k)(1=k=r-1)可应用下式逆推产生：t(k)=c(t(k+1),k)根据t数组的值，可直接按字符形式打印表面积所求得的插入乘号的乘积式。程序代码:1.//在一个数中插入r个乘号，使其积最大2.//利用动态规划求解3.#includestdio.h4.#includestring.h5.6.intmain()7.{8.charnumStr[16];9.inti,j,k,len,u,r,b[16],t[16],c[16][16];10.doublef[17][17],d;11.12.printf(请输入整数：);13.scanf(%s,numStr);14.printf(请输入插入的乘号个数r:);15.scanf(%d,&r);16.len=strlen(numStr);17.if(len=r){18.printf(输入的整数位够数不够或r太大!/n);19.return0;20.}21.22.printf(在整数%s中插入%d个乘号，使乘积最大：/n,numStr,r);23.for(d=0,j=0;j=len-1;j++)24.b[j]=numStr[j]-'0';25.for(d=0,j=1;j=len;j++){26.d=d*10+b[j-1];//把b数组的一个字符转化为数值27.f[j][0]=d;//f[j][0]赋初始值28.}29.30.for(k=1;k=r;k++)31.for(i=k+1;i=len;i++)32.for(j=k;ji;j++){33.for(d=0,u=j+1;u=i;u++)34.d=d*10+b[u-1];35.if(f[i][k]f[j][k-1]*d){36.f[i][k]=f[j][k-1]*d;37.c[i][k]=j;38.}39.}40.41.t[r]=c[len][r];42.for(k=r-1;k=1;k--)43.t[k]=c[t[k+1]][k];//逆推出第k个*号的位置44.t[0]=0;t[r+1]=len;45.for(k=1;k=r+1;k++){46.for(u=t[k-1]+1;u=t[k];u++)47.putchar(numStr[u-1]);//输出最优解48.if(kr+1)49.putchar('*');50.}51.printf(=%.0f/n,f[len][r]);//输出最优值52.53.return0;54.}三、假设学校准备在某一天组织一系列学生活动，需要为每个活动分配一间教室。试利用贪心算法设计一个算法，为每个活动分配一间教室，要求使用的教室数量最少，并分析算法的时间复杂度。注意：算法不但需要给出所使用的教室数量，还需要给出为每个活动分配的教室编号。假设教室编号为1、2、3。。。。说明：1）假设学校中有足够多的教室2）教室的开放时间为8:00~22：00，且学生使用的教室的时间都介于这个时间界限内。3）第I个活动的开始时间为Si，结束时间为fi.问题分析:设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用教室，而在同一时间内只有一个活动能使用这一资源。每个活i都有一个要求使用该资源的起始时间si和一个结束时间fi,且sifi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当si=fj或sj=fi时，活动i与活动j相容。由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。贪心算法思路:活动安排运用贪心算法的思路为，尽可能多的使更多的事件得到资源的安排。按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。实现方法是在满足相容的条件下，使结束时间靠前的活动得到资源，这样就为后续时间留下更多的安排时间，以使更多的活动得到安排。算法分析：贪心算法的效率极高，当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以对队列进行递减排序，最简只要用O(nlogn)的时间。贪心算法的实现具体程序如下：//贪心算法实现代码n为活动个数s为活动开始起始时间队列f为活动结束队列A为已选入集合此时活动为以经过非递减排序队列#includeiostreamusingnamespacestd;voidGreedySelector(intn,ints[],intf[],boolA[],intnum[],intcount){//第一个活动为结束时间最早进入选入队列intj=0;for(inti=0;i11;i++){if(!A[i]){A[i]=true;j=i;num[i]=count;return;}}//循环控制，使与前一个活动相容的活动进入选入队列，由于队列已按非递减排列，所以即//把与前一个活动相容且结束时间最早的活动进入选入队列for(inti=1;in;i++){if(s[i]=f[j]){A[i]=true;num[i]=count;j=i;}elseA[i]=false;}}//排序将无序的活动按照结束时间递增进行排序voidsort(intn,ints[],intf[],intnum[]){intj,i,m;fo