给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重
集S中重数最大的元素称为众数。
例如，S={1，2，2，2，3，5}。
多重集S的众数是2，其重数为3。
«编程任务：
对于给定的由n 个自然数组成的多重集S，编程计算S 的众数及其重数。
«数据输入：
输入数据由文件名为input.txt的文本文件提供。
文件的第1行多重集S中元素个数n；接下来的n 行中，每行有一个自然数。
«结果输出:
程序运行结束时，将计算结果输出到文件output.txt中。输出文件有2 行，第1 行给
出众数，第2 行是重数。
输入文件示例 输出文件示例
input.txt
6
1
2
2
2
3
5
output.txt
2
3
这是算法...
但我还看不懂...
我认为文件操作还好弄.就算法,它是用递归来做的.
void mode(int LL,int RR)
{
int L1,R1;
int med=median(a,LL,RR);
split(a,med,LL,RR,L1,R1);
if(largest<R1-L1+1) largest=R1-L1+1;element=med;
if(L1-LL>largest) mode(LL,L1-1);
if(RR-R1>largest) mode(R1+1,RR);
}
//median用于找中位数,split用中位数将数组分2为段.
[此问题还有待解决,谢谢各位的参与!]
//首先在此文件夹下建立名为qingsongin2.txt的文件
//其内容为6 1 2 2 2 3 5 之格式.其中第一的数为数组表长度
#include<iostream>
#include<fstream>
#define MAXSIZE 20
using namespace std;
typedef int KeyLype;
typedef int Status;
typedef struct {
KeyLype key;
} RedType;
typedef struct {
RedType r[MAXSIZE + 1];
int length;
} SqList;
int SelectSort(SqList &L)
{
int i,j,t;
for(j=0;j<L.length;j++)
for(i=1;i<=L.length-j;i++)
if(L.r[i].key<L.r[i-1].key)
{
t=L.r[i].key;
L.r[i].key=L.r[i-1].key;
L.r[i-1].key=t;
}
return 0;
}//简单选择排序
int median(SqList L,int a,int b)
{
int med;
if((a+b)%2==0)
med=(a+b)/2;
else
med=(a+b-1)/2;
return med;
}
int L1(SqList L,int med)
{
while(med>=1&&med<=L.length)
{ if(L.r[med].key==L.r[med-1].key)
med--;
else
return med-1;
}
}
int R1(SqList L,int med)
{
while(med>=1&&med<=L.length)
{ if(L.r[med].key==L.r[med+1].key)
med++;
else
return med+1;
}
}
void mode(SqList L,int a,int b,int &max_num,int &max_count)
{
if(a==b)
return ;
else
{
int l1,r1;
int med,j,k;
k=j=med=median(L,a,b);
l1=L1(L,med);
r1=R1(L,j);
if(max_count<r1-l1-1)
{
max_count=r1-l1-1;
max_num=L.r[k].key;
}
if(l1-a+1>max_count)
mode(L,a,l1,max_num,max_count);
if(b-r1+1>max_count)
mode(L,r1,b,max_num,max_count);
}
}
int main()
{
ifstream fin("qingsongin2.txt");
ofstream fout("qingsongout2.txt");
SqList L;
int max_num;//众数
int max_count;//众数的个数
if (fin.fail())
{
cout<<"输入qingsongin2.txt文件出错!"<<endl;
return -1;
}
if (fout.fail())
{
cout<<"fout(\"qingsongout2.txt\");"<<endl;
return -2;
}
int n;//n是数组表的长度
fin>>n;
int i;
for(i=1;i<=n;i++)
//cin>>L.r[i].key;
fin>>L.r[i].key;
L.length=n;
//cout<<endl;
SelectSort(L);
mode(L,1,L.length, max_num,max_count);
//cout<<"众数是:"<<max_num<<endl;
//cout<<"重复次数是:"<<max_num<<endl;
fout<<"众数是:"<<max_num<<endl;
fout<<"它的个数是:"<<max_count<<endl;
cout<<"请查看此文件夹下的qingsongout2.txt文件"<<endl;
return 0;
}
但它的前提是已排好序的.
如果不排呢?又该怎样做?
[此贴子已经被作者于2007-10-30 21:31:29编辑过]
