经典ACM算法合集经典ACM算法合集(4)

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

，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标记出现的最大重数和该重数对应的元素。
②若当前元素不同于前一个元素，且前一个元素的重数s>max,更新max和t。

4、源程序：

#include<iostream>
using?namespace?std;
#include<algorithm>

main()
{
int?n,i,t,m=0,s,max=0,*a;
scanf("%d",&n);
a=new?int[n];
for(i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
for(i=0;i<n;i++)
{
if(m!=a[i])
s=1;
else
s++;
m=a[i];
if(s>max)
{
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 (0 < n < 1000) ，输入以文件结束标志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、源程序：

#include <stdio.h>

int set(int n)
{
int i,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];
}
return count[n];
}

m
ain()
{
int n;
while(scanf("%d",&n)!=EOF)
printf("%d\n",set(n));
return 0;
}


5、算法分析：
函数set(n)的时间复杂度为Ο(n)，主函

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科经典ACM算法合集经典ACM算法合集(4)全文阅读和word下载服务。