经典ACM算法合集经典ACM算法合集

《经典ACM算法合集经典ACM算法合集》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、>intmain(){longintsn[10];inti,n,c,k,s,pown;for(i=0;i<10;i++)sn[i]=0;cin>>n;for(k=s=0,pown=1;n>0;k++,n/=10,pown*=10){c=n%10;for(i=0;i<10;i++)sn[i]+=c*k*(pown/10);for(i=0;i

4、count()，故该算法的时间复杂度为O(1)。实验二最大间隙问题1、问题描述：最大间隙问题：给定n个实数x1,x2,...,xn,求这n个数在实轴上相邻2个数之间的最大差值。假设对任何实数的下取整函数耗时O(1)，设计解最大间隙问题的线性时间算法。对于给定的n个实数x1,x2,...,xn，编程计算它们的最大间隙。2、题目分析：考虑到实数在实轴上按大小顺序排列，先对这n个数排序，再用后面的数减去前面的数，即可求出相邻两数的差值，找出差值中最大的即为最大差值。3、算法设计：a.用快速排序算法对这n个数排序，快速排序算法是基于分治策略的一个排序算法。其基本思想是，对于输入的子

5、数组a[p:r]，按以下三个步骤进行排序：①分解：以a[p]为基准元素将a[p:r]划分为3段a[p:q-1]，a[q]和a[q+1:r]，使a[p:q-1]中任何一个元素小于等于a[p]，而a[q+1:r]中任何一个元素大于等于a[q]。下标q在划分过程中确定。②递归求解：通过递归调用快速排序算法分别对a[p:q-1]和a[q+1:r]进行排序。③合并：由于对a[p:q-1]和a[q+1:r]的排序是就地进行的，所以在a[p:q-1]和a[q+1:r]都已排好的序后，不需要执行任何计算，a[p:r]就已排好序。b.用函数maxtap()求出最大差值。4、源程序：#incl

6、ude#includedoublea[1000000];templatevoidswap(Type&x,Type&y){Typetemp=x;x=y;y=temp;}templateintPartition(Type*a,intlow,inthigh){Typepivotkey;intmid=(low+high)/2;if((a[low]

7、

8、(a[low]>a[mid]&&a[mid]>a[high]))swap(a[low],a[mid])

9、;if((a[low]a[high])

10、

11、(a[low]>a[high]&&a[mid]pivotkey);if(i>=j)break;swap(a[i],a[j]);}a[low]=a[j];a[j]=pivotkey;returnj;}templat