exercise2ACM

第二次作业（计1202蒋信厚）贪心算法：在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。贪心算法的基本步骤包括：1.从问题的某个初始解出发。2.采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。3.将所有部分解综合起来，得到问题的最终解。时间序列问题：1、已知N个事件的发生时刻和结束时刻（见下表，表中事件已按结束时刻升序排序）。一些在时间上没有重叠的事件，可以构成一个事件序列，如事件{2，8，10}。事件序列包含的事件数目，称为该事件序列的长度。请编程找出一个最长的事件序列。输入：第一行为事件的个数N，以下共输入N行，每一行都有两个整数构成，第一个整数为事件开始时间，第二个整数为事件结束时间，时间的编号为其所在的行数(从0开始计数)。输出：输出一个最长的时间序列输入示例：121334073829510612414101581815191520输出示例：015810解：用Begin[i]和End[i]表示事件i的开始时刻和结束时刻。则原题的要求就是找一个最长的序列a1a2…an，满足：Begin[a1]End[a1]=…=Begin[an]End[an]；可以证明，如果在可能的事件a1a2…an中选取在时间上不重叠的最长序列，那么一定存在一个包含a1（结束最早）的最长序列（序列长度是指事件个数而不是时间长度！！！）。示例中结束最早的事件是13，所以该事件就作为贪心算法中的初始解。因为目标是使时间序列中的事件尽可能多，所以每一步贪心算法都是将不重叠的结束最早的事件加入时间序列。程序实现：//1.时间序列问题#defineMax100//事件个数上限voidmain(){intNumber;//事件个数NumberintBegin[Max];//事件开始时刻//下标表示事件编号intEnd[Max];//事件结束时刻intresult[Max];//存储最长的时间序列intr=0;//存储result[]的下标cinNumber;//判断事件个数是否超出上限if(NumberMax){cout事件个数超出上限！endl;exit(1);}//输入时间序列for(intj=0;jNumber;j++)cinBegin[j]End[j];//寻找最长的时间序列//首先将第一个最早结束的事件加入最长时间序列result[0]=0;//继续循环遍历所有事件构造最长时间序列for(inti=1;iNumber;i++){if(Begin[i]=End[result[r]])result[++r]=i;}//输出最长时间序列编号for(intk=0;k=r;k++)coutresult[k]'\t';coutendl;}区间覆盖问题：2、用i来表示x轴上坐标为[i-1,i]的区间（长度为1），并给出M(1=M=200)个不同的整数，表示M个这样的区间。现在让你画几条线段覆盖住所有的区间，条件是：每条线段可以任意长，但是要求所画线段之和最小，并且线段的数目不超过N(1=N=50)。例如：M=5个整数1、3、4、8和11表示区间，要求所用线段不超过N=4条1234567891011输入：第一行为一个整数K，表示区间编号的最大数，当K=0时，程序结束，第二行为两个整数M和N，M表示需要覆盖的区间个数，N表示最大线段的数目，第三行包括M个正整数(不大于K),表示k个需要覆盖的区间编号。输出：在给定条件下所画线段之和的最小值。输入示例：11541348110输出示例：5解：方法一：（传统的一般解法）先用一条最长的线段把整个区间覆盖起来，然后把区间点之间的空隔线段按照先长后短的顺序一一去掉，也就是贪心地使总线段长度尽可能短，知道线段的数量增加到到规定的数目停止；方法二：（个人原创想到的思路）其实思想与方法一一样，只不过这里逆向思考不是先用一条最长的线段把整个区间覆盖，二是用最短的线段把所有的区间点覆盖，也就是每个区间点用一条单位长度的线段覆盖，那么有n个区间点,就需要总长度为n的线段，然后把每个小线段一一连接起来，还是贪心地线连接距离最短的，尽量使总长度最短，直到线段数量减少到规定数目停止。程序实现：//2.区间覆盖问题//方法一//降序排列函数指定，sort库函数默认是升序的intdescend(inta,intb){returnab;}intmain(){intn,m,minLength,max;//区间点的个数n和所需的线段数m,覆盖线段的最短总长度minLength,区间点编号的最大数maxintpoint[200],distance[200];//区间点数组point与区间点之间的距离数组distancewhile(cinnm)//用户输入区间点的个数n和所需的线段数m{cinmax;//输入区间点编号的最大数，为0程序退出if(!max)break;for(inti=0;in;i++){cinpoint[i];}sort(point,point+n);//升序排列minLength=point[n-1]-point[0]+1;//全部覆盖的最长的一条线段的长度for(i=0;in-1;i++)distance[i]=point[i+1]-point[i]-1;//将每两个区间点之间的距离存入distance数组intnn=n-1;//距离数组的实际长度sort(distance,distance+nn,descend);//将区间距离数组降序排列for(i=0;im-1;i++)minLength-=distance[i];//将链接区间点之间的线段按先去长后去短的顺序一一去掉知道线段条数达到要求coutminLengthendl;}return0;}/*//方法二intmain(){intn,m,minLength,max;//区间点的个数n和所需的线段数m,覆盖线段的最短总长度minLength,区间点编号的最大数maxintpoint[200],distance[199];//区间点数组point与区间点之间的距离数组distancewhile(cinnm)//用户输入区间点的个数n和所需的线段数m{for(inti=0;in;i++){cinpoint[i];}sort(point,point+n);//升序排列minLength=n;//每个区间点用一个单位的线段覆盖时的线段的总长度for(i=0;in-1;i++)distance[i]=point[i+1]-point[i]-1;//将每两个区间点之间的距离存入distance数组intnn=n-1;//距离数组的实际长度sort(distance,distance+nn);//将区间距离数组升序排列for(i=0;in-m;i++)minLength+=distance[i];//将每一段单位线段按照距离最近一一连接起来，直到线段数目达到要求coutminLengthendl;}return0;}*/胜者败者问题：（ThegameofNim）3、两名参与者交替从一堆石子中取出若干数目,其个数由参与者自已决定.但是要求参与者每次至少取出一个,至多取出一半,然后另一名参与者继续.拿到最后一个石子的参与者将输掉该游戏.输入：输入开始时石子的个数输出：如果先取者输，则输出“lose”，否则输出“win”解：由题意分析得必败点为1,3,7,15......,也就是2^n-1,其中n0,其余的都是必胜点。//3.取石子（TheGameofNim）//判断是不是2的幂boolisPowerOf2(intn){intnumber=n;while(number){if(number==1)returntrue;if(number%2)returnfalse;number/=2;}returntrue;}voidmain(){//石子的初始数目intNumber;cinNumber;if(Number==0)coutwin!endl;if(isPowerOf2(Number+1))coutlose!endl;elsecoutwin!endl;}【估计也不会考这个】母函数：4、GivensomeChineseCoins(threekinds--1,2,5),andtheirnumberisnum_1,num_2andnum_5respectively,pleaseoutputtheminimumvaluethatyoucannotpaywithgivencoins.InputInputcontainsmultipletestcases.Eachtestcasecontains3positiveintegersnum_1,num_2andnum_5(0=num_i=1000).Atestcasecontaining000terminatestheinputandthistestcaseisnottobeprocessed.OutputOutputtheminimumpositivevaluethatonecannotpaywithgivencoins,onelineforonecase.题目大意为给你三种不同价值的硬币，分别为一、二、五，告诉你各自的数量，求由这些钱币所不能组成的最小财富这并不是连续的数值，所以在进行表达式的展开时，用的是数组，而不是小标i。解：constintMAX=1000;constinttype[3]={1,2,5};boolans[MAX],tmp[MAX];intcnt[3];voidSearch(){inti,j,k;//全部初始化为0memset(ans,0,sizeof(ans));memset(tmp,0,sizeof(tmp));for(i=0;i=cnt[0];++i){ans[i]=true;}for(i=1;i3;++i){for(j=0;j=MAX;++j){for(k=0;k=cnt[i]&&j+k*type[i]=MAX;++k){//tmp[j+k*type[i]]+=ans[j];if(tmp[j+k*type[i]]||ans[j])tmp[j+k*type[i]]=true;}}for(j=0;j=MAX;++j){ans[j]=tmp[j];tmp[j]=false;}}}intmain(){intres=0;while(cincnt[0]cnt[1]cnt[2]){if(cnt[0]==0&&cnt[1]==0&&cnt[2]==0)break;Search();for(inti=0;i=MAX;++i){if(!ans[i]){res=i;break;}}coutresendl;}return0;}5、写出完整的二分查找程序，要求：（1）先将给定的数据利用快速排序进行排序（采用复杂度为nlg(n)的算法）。（2）利用二分查找法判断给定的数据是否在数据集中。解：快速排序算法：对于包含n个数的输入数组来说，快速排序是一种最坏情况时间复杂度为O（n^2）的排序算法，他的平均性能非常好，期望时间复杂度为nlgn.与归并排序一样，快速排序也使用了分治思想：快速排序是找出一个元素（理论上可以随便找一个）作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值都不小于基准值，如此作为基准的元素调整到排序后的正确位置。递归快速排序，将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正确位置，排序完成。所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。//快速排序voidquicksort(i