主题：第39次编程比赛题目
ccpp [专家分：9360] 发布于 2006-08-24 14:37:00
第1题：
半数问题，给定整型数组vote[], 其大小为n，数组中任一元素均为自然数i(i = 1,2,3,...)。
规定函数接口：int Majority (int vote[], int n)
在vote[]中，可能存在一个自然数i，其个数m 超过半数，即m > n/2。若存在这样的i，函数Majority返回m，否则函数返回0。
例：
vote[5] = {1,8,1,100,1}; 其大小为 5。
因为自然数1的个数为3，超过半数，那么调用Majority将返回 3。
题目要求：编写规定函数接口 Majority。
赠送题：
已知f[]和g[]两个数组，大小分别为m和n，其中的元素都已经从小到大排列，且每个数组内的元素都各不相同。
规定函数接口：int Count (int f[], int g[], int m, int n)
函数Count返回两个数组中有多少组元素相同。
例：
f[5] = {1,3,4,7,9}, g[4] = {3,5,7,8};
因为只有2组元素相同，分别是f[1]与g[0] 和 f[3]与g[2]，所以函数Count的返回值应为2。
题目要求：编写规定函数接口Count。
回复列表 （共57个回复）
41 楼
amen [专家分：140] 发布于 2006-08-25 15:53:00
#include<iostream>
using namespace std;
const int SIZE=100;
int Majority (int vote[], int n)
{
int i,j,k=0;
int a[SIZE],num[SIZE]={0};
for(i=0;i<n;i++)
{ for(j=0;j<k;j++)
if(a[j]==vote[i])
{ num[j]++;
break;
}
if(j==k)
{ a[j]=vote[i];
num[j]++;
k++;
}
}
for(i=0;i<k;i++)
if(num[i]>n/2)return num[i];
return 0;
}
int main()
{
int vote[20]={2,3,4,2,2,2,2,2,2,1,2,2,2,2,2,2,2,2,9,1};
cout<<Majority(vote,20)<<endl;
return 0;
}
赠送题:
#include<iostream>
using namespace std;
int Count (int f[], int g[], int m, int n)
{
int i,j,k=0,count=0;
for(i=0;i<m;i++)
for(j=k;j<n;j++)
{ if(f[i]==g[j])
{ count++;
k=j+1;
break;
}
if(f[i]<g[j])
{ k=j;
break;
}
if(j==n-1)return count;
}
return count;
}
int main()
{
int f[11] = {1,2,3,4,7,9,10,12,13,17,18}, g[9] = {2,3,5,7,8,11,13,15,16};
cout<<Count (f,g,11,9)<<endl;
return 0;
}
42 楼
forjane [专家分：5670] 发布于 2006-08-25 16:08:00
int Majority (int vote[], int n)
{
int *p=new int[n/2];
int *q=new int[n/2];
int i,j,max,cnt=1,found=0;
for(p[0]=vote[0],q[0]=1,i=1;i<n;i++)
{
for(found=0,j=0;j<cnt;j++)
if(vote[i]==p[j])
{
q[j]++;
found=1;
}
if(!found)
{
cnt++;
if(cnt>n/2)
return 0;
p[cnt-1]=vote[i];
q[cnt-1]=1;
}
}
for(max=0,j=0;j<cnt;j++)
if(q[max]<q[j])
max=j;
if(max<=n/2)
return 0;
else
return p[max];
}
43 楼
forjane [专家分：5670] 发布于 2006-08-25 16:08:00
int Count (int f[], int g[], int m, int n)
{
int i=0,j=0,cnt=0;
while(i<m && j<n)
{
if(f[i]==g[j])
{
cnt++;
i++;
j++;
}
else
if(f[i]<g[j])
i++;
else
j++;
}
return cnt;
}
44 楼
wshong [专家分：1880] 发布于 2006-08-25 16:31:00
#include<stdio.h>
#include<stdlib.h>
typedef struct num{
int count,number;
struct num *next;
}num;
int Majority (int vote[], int);
num *local(num *h,int vote)
{
num *s;
s=h;
while(s!=NULL)
{if(s->number==vote)
{return s;
exit (0);
}
s=s->next;
}
return 0;
}
void main()
{
int vote[5]={1,8,1,100,1};
printf("%d",Majority (vote,5));
}
int Majority (int vote[], int n)
{
int sort=0;
num *q,*p,*r,*h;
p=(num *)malloc(sizeof(num));
p->number=vote[0];
p->next=NULL;
p->count=1;
sort++;
h=p;
r=p;
if(n<=2)
{
if(n==1)
return 1;
else{
if(vote[1]==p->number)
return 2;
else return 0;
}
}
else{
for(int i=1;i<n;i++)
{
if(local(h,vote[i]))
{
q=local(h,vote[i]);
q->count+=1;
if(q->count>(n/sort))
break;
}
else
{ sort++;
p=(num *)malloc(sizeof(num));
p->number=vote[i];
p->next=NULL;
p->count=1;
r->next=p;
r=p;
}
if(sort>(n/2+1))
{
return 0;
exit (0);
}
}
for(i+=1;i<n;i++)
{
if(vote[i]==q->number)
q->count++;
}
if(q->count>(n/2))
return q->count;
return 0;
}
}
45 楼
wshong [专家分：1880] 发布于 2006-08-25 16:31:00
#include<stdio.h>
#include<stdlib.h>
int search(int a[],int first,int last,int find)
{
int mid;
while(first<=last)
{
mid =(first+last)/2;
if(find==a[mid])
return mid;
else
if(find>a[mid])
first=mid+1;
else last=mid-1;
}
return 1000;
}
int Count (int f[], int g[], int m, int n)
{
int count=0;
int i,j=0,wshong;
if(m>n)
{
for(i=0;i<n;i++)
{
wshong=search(f,j,m,g[i]);
if(wshong==1000)
{
continue;}
j=wshong+1;
count+=1;
printf("%d\n",count);
}
}
else{
for(i=0;i<m;i++)
{
wshong=search(g,j,n,f[i]);
if(wshong==1000)
continue;
j=wshong+1;
count+=1;
}
}
return count;
}
void main()
{
int f[5] = {1,3,4,7,9}, g[4] = {3,5,7,8};
printf("%d", Count(f,g,5,4));
}
46 楼
qingfengjianke [专家分：740] 发布于 2006-08-25 17:23:00
限于水平只能做这样了。。
int Majority(int vote[],int n)
{
int *p= vote;
int m;
for(int i = 0;i < n-1;i++)
{
m = 1;
for(int j = i+1;j < n;j++)
{
if(p[i] == *(p+j))
m++;
}
if(m > n/2)
return m;
}
return 0;
}
47 楼
wksuper [专家分：660] 发布于 2006-08-25 17:32:00
#include <map>
int Majority(int vote[], int n)
{
std::map<int, int> table;
for(int i = 0; i < n; ++i)
{
int tmp = ++table[vote[i]];
if(tmp > n/2) return tmp;
}
return 0;
}
48 楼
侍鱼 [专家分：80] 发布于 2006-08-25 18:21:00
//算法核心:每查找一次就删除已查找元素,减少第二次查找元素个数
#include <iostream>
using namespace std;
int Majority(int vote[], int n)
{
int i,j,iCount,iHalf,iJudge;
iHalf=n/2; //元素个数的一半
iCount=1; //计数器
j=0;
while(iCount<=n)
{
iJudge=vote[0]; //以数组第一个元素作为判断
for(i=1;i<n;i++)
{
if(iJudge==vote[i]) //相同元素更新计数器
iCount++;
else vote[j++]=vote[i]; //不相同更新数组,减少第二次查找元素个数
}
if(iCount>iHalf) return iCount;
if(j>iHalf) //初始化下次查找
{
n=j;
j=0;
iCount=1;
}
else return 0;
}
}
int main(int argc, char *argv[])
{
int a[15]={9,1,3,2,6,2,2,4,2,7,2,4,2,2,2}; //测试数组
int result; //记录函数返回值
result=Majority(a,15); //判断半数
if(result==0) cout<<"不存在!"<<endl; //打印结果
else cout<<"这个数有"<<result<<"个"<<endl;
system("PAUSE");
return 0;
}
49 楼
yelv [专家分：0] 发布于 2006-08-25 19:22:00
int Majority (int vote[], int n)
{
int i, j;
int count;
int result = 0;
for (i=0; i<(n+1)/2; i++)
{
count = 1;
for (j=i+1; j<n; j++)
{
if(vote[j] == vote[i])
{
count++;
}
if (count >= (n/2+1))
{
result = vote[i];
break;
}
} //end for(j)
if (count >= (n/2+1))
{
break;
}
}//end for(i)
return result;
}
50 楼
yelv [专家分：0] 发布于 2006-08-25 19:31:00
赠送题：
int Count (int f[], int g[], int m, int n)
{
int i, j;
int count= 0;
for (i=0; i<m; i++)
{
for (j=0; j<n; j++)
{
if(f[i] == g[j])
{
count++;
}
}
}
return count;
}
我来回复
您所在位置：