经典ACM算法合集经典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、源程序：

#include <iostream.h>
int main()
{
long int sn[10];
int i,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<c;i++)
sn[i]+=pown;
sn[c]+=1+s;
sn[0] -=pown;
s+=c*pown;
}
for(i=0;i<10;i++)
cout<<sn[i]<<'\n';
}

5、算法分析：
函数count()的复杂度为O(1)，主函数调用count()，故该算法的时间复杂度为O(1)。
实验二 最大间隙问题

1、问题描述：
最大间隙问题：给定n 个实数x1 , x2 ,... , xn,求这n 个数在实轴上相邻2 个数之间的最大差值。假设对任何实数的下取整函数耗时O(1)，设计解最大间隙问题的线性时间算法。 对于给定的n 个实数x1 , x2 ,... , xn，编程计算它们的最大间隙。

2、题目分析：
考虑到实数在实轴