经典ACM算法合集经典ACM算法合集.docx

《经典ACM算法合集经典ACM算法合集.docx》由会员分享，可在线阅读，更多相关《经典ACM算法合集经典ACM算法合集.docx（58页珍藏版）》请在三一文库上搜索。

1、实验一统计数字问题实验二最大间隙问题实验三众数问题实验四半数集问题实验五集合划分问题实验六最少硬币问题实验七编辑距离问题实验八程序存储问题实验九最优效劳次序问题实验十汽车加油问题实验十一工作分配问题实验十二0-1背包问题实验十三最小重量机器设计问题实验十四最小权顶点覆盖问题实验十五集合相等问题实验十六战车问题实验一统计数字问题1、问题描述：一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6页用数字6表示，而不是06或006等。数字计数问题要求对给定书的总页码n,计算出书的全部页码中分别用到多少次数字0,1,2,.,9o2、题目

2、分析:考虑由0,1,2,.,9组成的所有n位数。从n个。到n个9共有个n位数，在这些n位数中，0,1,2,，9每个数字使用次数相同，设为。满足如下递归式：由此可知，。据此，可从低位向高位进行统计，再减去多余的0的个数即可。3、算法设计：定义数组a10存放。到9这10个数出现的次数，个位为第。位,第j位的数字为ro采用while循环从低位向高位统计：a.统计从个位算起前j位09个数；b.如果j+1位为0,去掉第j+1位补0个数；c.统计第j+1位出现1(r-l)个数；d.统计第j+1位出现r个数。4、源程序：#includeintmain()longintsn10;inti,n,c,k,s,po

3、wn;for(i=0;in;for(k=s=09pown=l;n0;k+,n/=10,pown*=10)c=n%10;for(i=0;i10;i+)sni+=c*k*(pown10);for(i=0;ic;i+)sni+=pown;snc+=l+s;sn0-=pown;s+=c*pown;)for(i=0;i10;i+)coutsnifnf;5、算法分析：函数CoUnt()的复杂度为0(1),主函数调用CoUlIt(),故该算法的时间复杂度为0(1)。实验二最大间隙问题1、问题描述：最大间隙问题：给定n个实数xl,x2,xn,求这n个数在实轴上相邻2个数之间的最大差值。假设对任何实数的下取整函

4、数耗时0(1),设计解最大间隙问题的线性时间算法。对于给定的n个实数xl,x2,.,xn,编程计算它们的最大间隙。2、题目分析：考虑到实数在实轴上按大小顺序排列，先对这n个数排序，再用后面的数减去前面的数，即可求出相邻两数的差值，找出差值中最大的即为最大差值。3、算法设计：a.用快速排序算法对这n个数排序，快速排序算法是基于分治策略的一个排序算法。其根本思想是，对于输入的子数组ap:r,按以下三个步骤进行排序：分解：以ap为基准元素将ap:H划分为3段ap:q-l,aq和aq+kr,使ap:q-l中任何一个元素小于等于ap,而aq+l:H中任何一个元素大于等于aq。下标q在划分过程中确定。递归

5、求解:通过递归调用快速排序算法分别对apql和aq+kr进行排序。合并：由于对ap:q-l和aq+l的排序是就地进行的，所以在ap:q-l和aq+l:r都已排好的序后,不需要执行任何计算,ap:r就已排好序。b.用函数maxtap()求出最大差值。4、源程序:#includeincludedoublea1000000;templatevoidswap(Type&x,TyPe&y)Typetemp=x;x=y;y=temp;templateintPartition(Type*a,intIowJnthigh)Typepivotkey;intmid=(low+high)2;if(alowamid&a

6、midamid&amidahigh)swap(alow9amid);if(alowahigh)|(alowahigh&amidahigh)swap(alow,ahigh);pivotkey=alow;inti=low;intj=high+l;while(true)while(a+ipivotkey);if(i=j)break;swap(ai9aj);alow=aj;aj=pivotkey;returnj;templatevoidQuicksort(Type*a,intIowJnthigh)if(lowhigh)intq=Partition(a9low9high);Quicksort(aJow,

7、q-1);Quicksort(a,q+1,high);)templateTypemaxtap(Type*a,intn)(Typemaxtap=0;for(inti=0;imaxtap?(ai+l-ai):maxtap;returnmaxtap;)main()(inti,n;scanf(11%d11n);for(i=0;imax,更新max和to4、源程序：includeusing?namespace?std;includemain()int?n，i，t,m=OSmaX=O,*a;scanf(11%d11n);a=new7intn;for(i=0;in;i+)scanf(11%d11ai);so

8、rt(a,a+n);for(i=0;imax)(t=m;max=s;)printf(%dn%dn,t,max);return70;5、算法分析:主函数内调用的库函数sort(a,a+n)的时间复杂度为，for循环的时间杂度为O(n),故该算法的时间杂度为。实验四半数集问题1、问题描述：?给定一个自然数n,由n开始可以依次产生半数集Set(II)中的数如下：(l)nset(n);(2)在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；(3)按此规那么进行处理，直到不能再添加自然数为止。例如：set(6)=6,16,26,126,36,136),半数集set(6)中有6个元素。注意半

9、数集是多重集，对于给定的自然数n,编程计算半数集set(n)中的元素个数。2、题目分析：题目要求输入有多行，每行给出一个整数n(0n1000),输入以文件结束标志EOF结束。半数集set(n)中的元素个数即为所有半数集set(j)(j=n2)的元素个数之和加1即将其自身添加到所求元素中)。3、算法设计:a.用数组CoUnti计算SeKi)中的元素个数,即计算所有j=i2的set(j)中的元素加其自身的个数之和；b.用数组CoUlIt_sumi计算所有j=i的set(j)中的元素个数之和；c.采用for循环分别对COUlIti、COUllt_sumi进行累加，即可求出半数集set(n)中的元素个

10、数。4、源程序：#includeintset(intn)inti9count1001,count_sum1001;countl=l;count_suml=l;for(i=2;i=n;i+)counti=count_sumi/2+l;count_sumi=count_sumi-l+counti;returncountn;main()intn;while(scanf(11%d11n)!=EOF)Printf(dnset(n);return0;5、算法分析：函数set(n)的时间复杂度为O(I),主函数调用函数set(n),故该算法的时间复杂度为O(n)。实验五集合划分问题2、题目分析：题目要求计算

11、11个元素的集合共有多少个划分其中每个划分都由不同的非空子集组成，n个元素的集合划分为m个块的划分数为F(n,m)=F(n-1,m-1)+m*F(n-1,m),m从1至!In的划分个数相加即可求得总的划分数。3、算法设计：a.这一题的结果数很大，需要使用64位长整型：_int64；b.函数div()采用递归的方式计算n个元素的集合划分为i个块的划分数：div(n,l)=Ldiv(n,n)=l;div(nJ)=div(n-l,i-l)+i*div(n-l,i)C.主函数采用for循环调用函数div(n,i)qn)对划分数进行累加统计。4、源程序：#includeint647div(int647n

12、9int647i)if(i=li=n)return?1;else?return?div(n-1，i-1)+i*div(n-1，i);main()int647i,n9s=0;scanf(11%I64d11n);for(i=l;i=n;i+)s=s+div(nj);printf(11%I64d119s);return70;5、算法分析：函数div()的时间复杂度为，主函数内for循环的时间复杂度为O(n),函数div()嵌套在for循环内，故该算法的时间复杂度为。实验七编辑距离问题1、问题描述：?设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括(1)删除一个

13、字符；(2)插入一个字符；(3)将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的2个字符串A和B,计算出它们的编辑距离d(A,B)2、题目分析：题目要求计算两字符串的编辑距离，可以采用动态规划算法求解,由最优子结构性质可建立递归关系如下：其中数组dij存储长度分别为i、j的两字符串的编辑距离;用edit标记所比拟的字符是否相同，相同为0,不同为1;用m、n存储字符串a、b的长度。3、算法设计：a.函数min()找出三个数中的最小值；b.函数d()计算两字符串的编辑距离：用edit标记所比拟的字符是否

14、相同，相同为0,不同为1；分别用m、Il存储字符串a、b的长度，用数组dij存储长度分别为i、j的两字符串的编辑距离，问题的最优值记录于dnm中；利用递归式写出计算dij的递归算法。4、源程序：#includeusingnamespacestd;intmin(inta,intb,intc)inttemp=(ab?a:b);return(tempc?temp:c);intd(char*a,char*b)intm=strlen（八）;intn=strlen(b);intij,temp;int*d;d=(int*)ma11oc(sizeof(int*)*(m+l);for(i=0;i=m;i+)di

15、int*)ma11oc(sizeof(int)*(n+l);)d00=0;for(i=1;i=m;i+)di0=i;for(j=l;j=n;j+)dOj=j;for(i=l;i=m;i+)for(j=l;j=n;j+)intedit=(ai-l=bj-l?O:1);dij=min(di-lj-l+edit),(dij-l+l),(di-lj+l);)temp=dmn;free(d);returntemp;)main()(charal00009bl0000;scanf(11%sn%s11,a,b);PrintfC%dd(a,b);return0;5、算法分析:函数d()采用了双重循环，里层的

16、for循环复杂度为O(n),外层的for循环复杂度为O(m),主函数调用了函数d(),故该算法的时间复杂度为O(mn)。实验八程序存储问题1、问题描述：设有n个程序1,2,.,n要存放在长度为L的磁带上。程序i存放在磁带上的长度是il,1ino程序存储问题要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。对于给定的n个程序存放在磁带上的长度，编程计算磁带上最多可以存储的程序数。2、题目分析：题目要求计算给定长度的磁带最多可存储的程序个数，先对程序的长度从小到大排序，再采用贪心算法求解。3、算法设计：a.定义数组an存储n个程序的长度，s为磁带的长度；b.调用库函数S

17、Ort(a,a+n)对程序的长度从小到大排序；c.函数most()计算磁带最多可存储的程序数，采用while循环依次对排序后的程序长度进行累加，用i计算程序个数，用SUm计算程序累加长度初始i=0,sum=0)： sum=sum+ai; 假设SUmV=S,i加1,否那么i为所求；i=n时循环结束；d.假设while循环结束时仍有sum=s,那么n为所求。4、源程序：#includeusingnamespacestd;includeinta1000000;intmost(int*a,intn,ints)inti=09sum=0;while(in)sum=ai+sum;if(sum=s)i+；el

18、sereturni;returnn;main()inti,n,s;scanf(11%d%dn&n，&s);for(i=0;in;i+)scanf(11%d11ai);sort(a,a+n);printf(11%d11,most(a9n,s);return0;)5、算法分析：函数most。的时间杂度为O(n),主函数调用的库函数sort(a,a+n)的时间复杂度为,且主函数调用函数most(),故该算法的时间杂度为。实验九最优效劳次序问题1、问题描述：设有n个顾客同时等待一项效劳。顾客i需要的效劳时间为tii11o应如何安排n个顾客的效劳次序才能使平均等待时间到达最小?平均等待时间是n个顾客等待

19、效劳时间的总和除以n。对于给定的n个顾客需要的效劳时间，编程计算最优效劳次序。2、题目分析：考虑到每个顾客需要的效劳时间已给定，要计算最优效劳次序，可以先对顾客需要的效劳时间由短到长排序，再采用贪心算法求解。3、算法设计：a.定义数组an存储n个顾客需要的效劳时间；b.调用库函数Sort(a,a+n)对顾客需要的效劳时间由短到长排序；c.函数time()计算最小平均等待时间，采用WhiIe循环依次对顾客等待效劳时间进行累加，用ai标记第i+1个顾客需要的效劳时间，用bi计算第i+1个顾客的等待效劳时间，用t计算前i+1个顾客等待效劳时间的总和初始i=l,t=a0,b0=a0):bi=ai+bi

20、l,t=bi+t;i+;i=n时循环结束；d.t/n为所求。4、源程序：includeusingnamespacestd;includeinta10000009b1000000;doubletime(int*a,intn)(inti=l,j=0;doublet=aO;b0=a0;while(in)(bi=ai+bi-l;t=bi+t;i+；)returnt/n;main()(inti,n;SCanf(%d&n);for(i=0;in,那么输出“NoSolution”；假设tai,那么加油一次：t=n,m+;行驶ai公里后，汽车还能行驶t-ai公里；i=k+l时循环结束；d.m即为所求。4、源

21、程序：#includemain()inti,n,km,a10000;scanf(11%d%d1111k);for(i=0;i=k;i+)scanf(11%d11ai);m=0;t=n;for(i=0;in)(printf(11NoSolution);break;)elseif(t=s,那么不是最优解，剪去相应子树，返回到i-1层继续执行；假设in,那么算法搜索到一个叶结点，用S对最优解进行记录，返回到i-1层继续执行；采用for循环针对n个人对工作i进行分配lj假设vj=l,那么第j个人已分配了工作，找第j+1个人进行分配；2假设vj=0,那么将工作i分配给第j个人即vj=l，对工作i+1调用

22、递归函数backtrack(i+l,total+cij)继续进行分配；3函数backtrack(i+l,total+cij)调用结束后那么返回vj=0,将工作i对第j+1个人进行分配；4当jn时，for循环结束；当i=l时，假设已测试完cij的所有可选值，外层调用就全部结束；C.主函数调用一次backtrack(l,O)即可完成整个回溯搜索过程，最终得到的s即为所求最小总费用。4、源程序：include#defineMAX1000;intn,c2121,v21,s,total;voidbacktrack(inti9inttotal)intj;if(total=s)return;if(in)s=

23、total;return;elsefor(j=l;j=n;j+)if(vj=l)continue;if(vj=0)vj=l;backtrack(i+1,total+Cij);vj=0;main()(inti,j;scanf(%dn);for(i=l;i=n;i+)(for(j=l;j0,wi0,vi0,lin,那么算法搜索到一个叶结点，判断当前总价值是否最优：1假设cpbestp,更新当前最优总价值为当前总价值即bestp=cp),更新装载方案即bestxi=xi(lin);采用for循环对物品i装与不装两种情况进行讨论(0jxi=j;2假设总重量不大于背包容量即cw+xi*wiv=c,那么更

24、新当前总价值和总重量即CW+=wi*xi,cp+=pi*xi,对物品i+1调用递归函数BaCktraCk(i+1,cp,cw)继续进行装载；3函数BaCktraCk(i+1,cp,cw)调用结束后那么返回当前总价值和总重量即cw-=wi*xi,cp-=pi*xi)；4当jl时，for循环结束；当i=l时，假设已测试完所有装载方案，外层调用就全部结束;c.主函数调用一次backtrack(l,O,O)即可完成整个回溯搜索过程,最终得到的bestp和bestxi即为所求最大总价值和最优装载方案。4、源程序：#includeintn,c,bestp;intp100009w100009x10000,b

25、estx10000;voidBacktrack(inti,intcp,intcw)intj;if(in)if(cpbestp)bestp=cp;for(i=0;i=n;i+)bestxi=xi;elsefor(j=0;j=l;j+)xi=j;if(cw+xi*wi=c)cw+=wi*xi;cp+=pi*xi;Backtrack(i+1,cp,cw);cw-=wi*xi;cp-=pi*xi;main()(inti;bestp=O;scanf(11%d%d1111c);for(i=l;i=n;i+)scanf(11%d11pi);for(i=l;i=n;i+)scanf(11%d11wi);Bac

26、ktrack(I9O9O);printf(nOptimalvalueisn11);printf(11%dn119bestp);for(i=l;id,那么为不可行解，剪去相应子树，返回到i-1层继续执行； 假设ws=bestw,那么不是最优解，剪去相应子树，返回至Ui-I层继续执行； 假设in,那么算法搜索到一个叶结点，用bestw对最优解进行记录，返回到i-1层继续执行； 采用for循环对部件i从m个不同的供给商购得的情况进行讨论(IgSm：1调用递归函KnaPSaCk(i+l,cs+cij,ws+wij)对部件i+1进行购置；2当jm时for循环结束；当i=l时，假设已测试完所有购置方案，外

27、层调用就全部结束；c.主函数调用一次KnaPSaCk(1,0,0)即可完成整个回溯搜索过程,最终得到的bestw即为所求最小总重量。4、源程序：#include#defineMIN1000intn,m,d,cs,ws,bestw;intw1001009c100100;voidKnapsack(inti,intcs9intws)intj；if(csd)return;elseif(ws=bestw)return;elseif(in)bestw=ws;return;)elsefor(j=1;j=m;j+)Knapsack(i+l,cs+cij,ws+wij);main()(inti,j;scanf(

28、11%d%d%d1111md);for(i=l;i=n;i+)for(j=l;j=m;j+)scanf(11%d11cij);)for(i=l;i=n;i+)(for(j=l;j=bestw,那么不是最优解，剪去相应子树，返回到i-1层继续执行； 假设in,那么算法搜索到一个叶结点，调用函数COVer()对图G进行判断：假设COVer()为真，那么用bestw对最优解进行记录，返回至Ji-1层继续执行； 对顶点i分在与不在顶点覆盖集中两种情况进行讨论：1假设顶点i不在顶点覆盖集中即ci=0),那么调用函数cut(i+l9s);2假设顶点i在顶点覆盖集中即ci=l),那么调用函数cut(i+l,

29、s+wi);当i=l时，假设已测试完所有顶点覆盖方案，外层调用就全部结束；d.主函数调用一次CUt(1,0)即可完成整个回溯搜索过程，最终得到的bestw即为所求最小顶点权之和。4、源程序：include#defineMIN100OOOintm,n,u,v,bestw;inte1001009w1009c100;intcover()(intij,t;i=l;while(i=n)t=0;if(ci=O)j=i;while(ji)if(e皿i=l&cj=l)t=l；j+；j+；while(j=bestw)return;if(in)if(cover()bestw=s;return;ci=0;cut(i