经典ACM算法合集经典ACM算法合集.docx
实验一统计数字问题实验二最大间隙问题实验三众数问题实验四半数集问题实验五集合划分问题实验六最少硬币问题实验七编辑距离问题实验八程序存储问题实验九最优效劳次序问题实验十汽车加油问题实验十一工作分配问题实验十二0-1背包问题实验十三最小重量机器设计问题实验十四最小权顶点覆盖问题实验十五集合相等问题实验十六战车问题实验一统计数字问题1、问题描述：一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6页用数字6表示，而不是06或006等。数字计数问题要求对给定书的总页码n,计算出书的全部页码中分别用到多少次数字0,1,2,.,9o2、题目分析:考虑由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、源程序：#include<iostream.h>intmain()longintsn10;inti,n,c,k,s,pown;for(i=0;i<10;i+)sni=0;cin>>n;for(k=s=09pown=l;n>0;k+,n/=10,pown*=10)c=n%10;for(i=0;i<10;i+)sni+=c*k*(pown10);for(i=0;i<c;i+)sni+=pown;snc+=l+s;sn0-=pown;s+=c*pown;)for(i=0;i<10;i+)cout<<sni<<fnf;5、算法分析：函数CoUnt()的复杂度为0(1),主函数调用CoUlIt(),故该算法的时间复杂度为0(1)。实验二最大间隙问题1、问题描述：最大间隙问题：给定n个实数xl,x2,xn,求这n个数在实轴上相邻2个数之间的最大差值。假设对任何实数的下取整函数耗时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在划分过程中确定。递归求解:通过递归调用快速排序算法分别对apql和aq+kr进行排序。合并：由于对ap:q-l和aq+l的排序是就地进行的，所以在ap:q-l和aq+l:r都已排好的序后,不需要执行任何计算,ap:r就已排好序。b.用函数maxtap()求出最大差值。4、源程序:#include<iostream.h>include<stdio.h>doublea1000000;template<classType>voidswap(Type&x,TyPe&y)Typetemp=x;x=y;y=temp;template<classType>intPartition(Type*a,intIowJnthigh)Typepivotkey;intmid=(low+high)2;if(alow<amid&&amid<ahigh)|(alow>amid&&amid>ahigh)swap(alow9amid);if(alow<ahigh&&amid>ahigh)|(alow>ahigh&&amid<ahigh)swap(alow,ahigh);pivotkey=alow;inti=low;intj=high+l;while(true)while(a+i<pivotkey);while(a-j>pivotkey);if(i>=j)break;swap(ai9aj);alow=aj;aj=pivotkey;returnj;template<classType>voidQuicksort(Type*a,intIowJnthigh)if(low<high)intq=Partition(a9low9high);Quicksort(aJow,q-1);Quicksort(a,q+1,high);)template<classType>Typemaxtap(Type*a,intn)(Typemaxtap=0;for(inti=0;i<n-l;i+)maxtap=(ai+l-ai)>maxtap?(ai+l-ai):maxtap;returnmaxtap;)main()(inti,n;scanf(11%d11n);for(i=0;i<n;i+)scanf(11%lf11ai);Quicksort(a909n-1);printf(11%lf11,maxtap(a,n);returnO;5、算法分析：快速排序的运行时间与划分是否对称有关，其最坏情况发生在划分过程产生的两个区域分别包含n-1个元素和1个元素的时候。由于函数Partition的计算时间为On),所以如果算法Partition的每一步都出现这种不对称划分，那么其计算时间复杂性TU)满足：解此递归方程可得。在最好情况下，每次划分所取得基准都恰好为中值，即每次划分都产生两个大小为n/2的区域，此时，Partition的计算时间T(Il)满足：其解为。可以证明，快速排序算法在平均情况下的时间复杂性也是。实验三众数问题1、问题描述：给定含有n个元素的多重集合S,每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如，S=l,2,2,2,3,5o多重集S的众数是2,其重数为3。对于给定的由n个自然数组成的多重集S,编程计算S的众数及其重数。2、题目分析：题目要求计算集合中重复出现最多的数以及该数出现的次数，假设两个数出现的次数相同，那么取较小的数。先对集合中的元素从小到大排序，再统计重数，找出最大的重数以及它对应的元素。3、算法设计：a.建立数组an存储集合中的元素；b.调用库函数Sort(a,a+n)对集合中的元素从小到大排序；c.采用for循环依次对排序后的元素进行重数统计：用m标记元素，用s统计该元数的重数，分别用max和t标记出现的最大重数和该重数对应的元素。假设当前元素不同于前一个元素，且前一个元素的重数s>max,更新max和to4、源程序：include<iostream>using?namespace?std;include<algorithm>main()int?n，i，t,m=OSmaX=O,*a;scanf(11%d11n);a=new7intn;for(i=0;i<n;i+)scanf(11%d11ai);sort(a,a+n);for(i=0;i<n;i+)(if(m!=ai)s=l;elses+;m=ai;if(s>max)(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个元素。注意半数集是多重集，对于给定的自然数n,编程计算半数集set(n)中的元素个数。2、题目分析：题目要求输入有多行，每行给出一个整数n(0<n<1000),输入以文件结束标志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)中的元素个数。4、源程序：#include<stdio.h>intset(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个元素的集合共有多少个划分其中每个划分都由不同的非空子集组成，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、源程序：#include<stdio.h>int647div(int647n9int647i)if(i=li=n)return?1;else?return?div(n-1，i-1)+i*div(n-1，i);
