衆數的求法

★問題描述：

給定含有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 output.txt

6 2

1 3

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

1、數組的衆數求法

這回是對上次發帖後改用分治法解決的，還有待改進之處。

#include<iostream>
#include<fstream>
using namespace std;
//結構體用來儲存衆數的元素與重數
typedef struct
{
int element;//元素
int sum;//重數
}zs;
//記錄中位數的起始下标
typedef struct
{
int low;
int high;
}node;
//快排
zs x;
//int data=1;
void sort(int a[],int s,int t)//對a[s]到a[t]的元素排序
{
int i=s,j=t;
int temp;
if(s<t)//區間裡至少存在一個元素的情況
{
temp=a[s];//用區間的第一個元素做基準
while(i!=j)//區間兩端交替向中間掃描，知道I=J
{
while(j>i&&a[j]>temp)
j--;//從右向左掃描，找到第一個小于temp的a[j]
if(i<j)//表示找到a[j],則a[i],a[j]交換
{
a[i]=a[j];
i++;
}
while(i<j&&a[i]<temp)
i++;//從左向右掃描，找到第一個大于temp的a[i]
if(i<j)//表示找到a[i],則a[i],a[j]交換
{
a[j]=a[i];
j--;
}
}
a[i]=temp;
sort(a,s,i-1);//對左遞歸
sort(a,i+1,t);//對右遞歸
}
}
//中位數
int madian(int *a,int l,int r)
{
int x=r+l+1;
// if(x%2)
return a[x/2];//為奇數時
// else
// return (a[x/2]+a[x/2+1])/2;//為偶數時
}
//傳回中位數的起始點
node spalit(int *a,int med,int l,int r)
{
node m;
m.low=l;m.high=r;
for(int i=0;i<=r;i++)
{
if(med==a[i])
{
m.low=i;
break;
}
}
for(int j=r;j>=0;j--)
{
if(med==a[j])
{
m.high=j;
break;
}
}
return m;
}
//衆數的重數求取
void mode(int *a,int l,int r)
{
if(l>=r)return;
//x.sum=0;
else
{
node n;
int temp=0;
int med;
med=madian(a,l,r);
n=spalit(a,med,l,r);
temp=n.high-n.low+1;
if(x.sum<temp)
{
x.element=med;
x.sum=temp;
}
if(n.low-l>temp)//
{
if(x.sum<temp)
{
x.element=med;
x.sum=temp;
}
mode(a,l,n.low-1);
}
if(r-n.high>temp)
{
if(x.sum<temp)
{
x.element=med;
x.sum=temp;
}
mode(a,n.high+1,r);
}
}
}
void main()
{
x.sum=0;
int n;
int *a;
ifstream in("C://inputdate.txt");
if(!in)
{
cout<<"the file can\'t open!"<<endl;
}
in>>n;
a=new int[n];
for(int i=0;i<n;i++)
{
in>>a[i];
}
sort(a,0,n-1);
mode(a,0,n-1);
cout<<x.element<<" "<<x.sum<<endl;
delete []a;
}

第二種

void mode(int l,int r）{

int l1,r1;

int med=median(a,l,r);

split(a,med,l,r,l1,r1);

if(largest<r1-l1+1){

largest=r1-l1+1;

element=med;

}

if(l1-1>largest)

mode(1,l1-1);

if(r-r1>largest)

mode(r1+1,r);

}

3、利用先排序，然後統計個數。考慮時間效率，采用快排，count (統計個數)，maxCount(最多的個數),element(重數最大的數即衆數)

4.可以利用散列法。

發表于

2015-01-09 17:09

想總結卻停留不前？

閱讀(852)

評論(0)

編輯

舉報