16个ACM经典算法介绍(优选.)

实验一统计数字问题实验二最大间隙问题实验三众数问题实验四半数集问题实验五集合划分问题实验六最少硬币问题实验七编辑距离问题实验八程序存储问题实验九最优服务次序问题实验十汽车加油问题实验十一工作分配问题实验十二0-1背包问题实验十三最小重量机器设计问题实验十四最小权顶点覆盖问题实验十五集合相等问题实验十六战车问题实验一统计数字问题1、问题描述：一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6页用数字6表示，而不是06或006等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，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、源程序：#includeiostream.hintmain(){longintsn[10];inti,n,c,k,s,pown;for(i=0;i10;i++)sn[i]=0;cinn;for(k=s=0,pown=1;n0;k++,n/=10,pown*=10){c=n%10;for(i=0;i10;i++)sn[i]+=c*k*(pown/10);for(i=0;ic;i++)sn[i]+=pown;sn[c]+=1+s;sn[0]-=pown;s+=c*pown;}for(i=0;i10;i++)coutsn[i]'\n';}5、算法分析：函数count()的复杂度为O(1)，主函数调用count()，故该算法的时间复杂度为O(1)。实验二最大间隙问题1、问题描述：最大间隙问题：给定n个实数x1,x2,...,xn,求这n个数在实轴上相邻2个数之间的最大差值。假设对任何实数的下取整函数耗时O(1)，设计解最大间隙问题的线性时间算法。对于给定的n个实数x1,x2,...,xn，编程计算它们的最大间隙。2、题目分析：考虑到实数在实轴上按大小顺序排列，先对这n个数排序，再用后面的数减去前面的数，即可求出相邻两数的差值，找出差值中最大的即为最大差值。3、算法设计：a.用快速排序算法对这n个数排序，快速排序算法是基于分治策略的一个排序算法。其基本思想是，对于输入的子数组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、源程序：#includeiostream.h#includestdio.hdoublea[1000000];templateclassTypevoidswap(Type&x,Type&y){Typetemp=x;x=y;y=temp;}templateclassTypeintPartition(Type*a,intlow,inthigh){Typepivotkey;intmid=(low+high)/2;if((a[low]a[mid]&&a[mid]a[high])||(a[low]a[mid]&&a[mid]a[high]))swap(a[low],a[mid]);if((a[low]a[high]&&a[mid]a[high])||(a[low]a[high]&&a[mid]a[high]))swap(a[low],a[high]);pivotkey=a[low];inti=low;intj=high+1;while(true){while(a[++i]pivotkey);while(a[--j]pivotkey);if(i=j)break;swap(a[i],a[j]);}a[low]=a[j];a[j]=pivotkey;returnj;}templateclassTypevoidQuicksort(Type*a,intlow,inthigh){if(lowhigh){intq=Partition(a,low,high);Quicksort(a,low,q-1);Quicksort(a,q+1,high);}}templateclassTypeTypemaxtap(Type*a,intn){Typemaxtap=0;for(inti=0;in-1;i++)maxtap=(a[i+1]-a[i])maxtap?(a[i+1]-a[i]):maxtap;returnmaxtap;}main(){inti,n;scanf(%d,&n);for(i=0;in;i++)scanf(%lf,&a[i]);Quicksort(a,0,n-1);printf(%lf,maxtap(a,n));return0;5、算法分析：快速排序的运行时间与划分是否对称有关，其最坏情况发生在划分过程产生的两个区域分别包含n-1个元素和1个元素的时候。由于函数Partition的计算时间为O（n），所以如果算法Partition的每一步都出现这种不对称划分，则其计算时间复杂性T（ｎ）满足:解此递归方程可得。在最好情况下，每次划分所取得基准都恰好为中值，即每次划分都产生两个大小为ｎ／２的区域，此时，Partition的计算时间Ｔ（ｎ）满足：其解为。可以证明，快速排序算法在平均情况下的时间复杂性也是。实验三众数问题1、问题描述：给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如，S={1，2，2，2，3，5}。多重集S的众数是2，其重数为3。对于给定的由n个自然数组成的多重集S，编程计算S的众数及其重数。2、题目分析：题目要求计算集合中重复出现最多的数以及该数出现的次数，若两个数出现的次数相同，则取较小的数。先对集合中的元素从小到大排序，再统计重数，找出最大的重数以及它对应的元素。3、算法设计：a.建立数组a[n]存储集合中的元素；b.调用库函数sort(a,a+n)对集合中的元素从小到大排序；c.采用for循环依次对排序后的元素进行重数统计：①用m标记元素，用s统计该元数的重数，分别用max和t标记出现的最大重数和该重数对应的元素。②若当前元素不同于前一个元素，且前一个元素的重数smax,更新max和t。4、源程序：#includeiostreamusing?namespace?std;#includealgorithmmain(){int?n,i,t,m=0,s,max=0,*a;scanf(%d,&n);a=new?int[n];for(i=0;in;i++)scanf(%d,&a[i]);sort(a,a+n);for(i=0;in;i++){if(m!=a[i])s=1;elses++;m=a[i];if(smax){t=m;max=s;}}printf(%d\n%d\n,t,max);return?0;}5、算法分析：主函数内调用的库函数sort(a,a+n)的时间复杂度为，for循环的时间杂度为Ο(n)，故该算法的时间杂度为。实验四半数集问题1、问题描述：?给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下：(1)n∈set(n)；(2)在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；(3)按此规则进行处理，直到不能再添加自然数为止。例如：set(6)={6,16,26,126,36,136}，半数集set(6)中有6个元素。注意半数集是多重集，对于给定的自然数n，编程计算半数集set(n)中的元素个数。2、题目分析：题目要求输入有多行，每行给出一个整数n(0n1000)，输入以文件结束标志EOF结束。半数集set(n)中的元素个数即为所有半数集set(j)(j=n/2)的元素个数之和加1（即将其自身添加到所求元素中）。3、算法设计：a.用数组count[i]计算set(i)中的元素个数，即计算所有j=i/2的set(j)中的元素加其自身的个数之和；b.用数组count_sum[i]计算所有j=i的set(j)中的元素个数之和；c.采用for循环分别对count[i]、count_sum[i]进行累加，即可求出半数集set(n)中的元素个数。4、源程序：#includestdio.hintset(intn){inti,count[1001],count_sum[1001];count[1]=1;count_sum[1]=1;for(i=2;i=n;i++){count[i]=count_sum[i/2]+1;count_sum[i]=count_sum[i-1]+count[i];}returncount[n];}main(){intn;while(scanf(%d,&n)!=EOF)printf(%d\n,set(n));return0;}5、算法分析：函数set(n)的时间复杂度为Ο(n)，主函数调用函数set(n)，故该算法的时间复杂度为Ο(n)。实验五集合划分问题2、题目分析：题目要求计算n个元素的集合共有多少个划分（其中每个划分都由不同的非空子集组成），n个元素的集合划分为m个块的划分数为F(n,m)=F(n-1,m-1)+m*F(n-1,m),m从1到n的划分个数相加即可求得总的划分数。3、算法设计：a.这一题的结果数很大，需要使用64位长整型：__int64；b.函数div()采用递归的方式计算n个元素的集合划分为i个块的划分数：①div(n,1)=1，div(n,n)=1;②div(n,i)=div(n-1,i-1)+i*div(n-1,i)c.主函数采用for循环调用函数div(n,i)（1≤i≤n）对划分数进行累加统计。4、源程序：#includestdio.h__int64?div(__int64?n,__int64?i){if(i==1||i==n)return?1;else?return?div(n-1,i-1)+i*div(n-1,i);}main(){__int64?i,n,s=0;scanf(%I64d,&n);for(i=1;i=n;i++)s=s+div(n,i);printf(%I64d,s);return?0;}5、算法分析：函数div()的时间复杂度为，主函数内for循环的时间复杂度为O(n)，函数div()嵌套在for循环内，故该算法的时间复杂度为。实验七编辑距离问题1、问题描述：?设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括(1)删除一个字符；(2)插入一个字符；(3)将一个字符改为另一个字符。将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的2个字符串A和B，计算出它们的编辑距离d(A,B)。2、题目分析：题目要求计算两字符串的编辑距离，可以采用动态规划算法求解，由最优子结构性质可建立递归关系如下：其中数组d[i][j]存储长度分别为i、j的两字符串的编辑距离