主题：第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个回复）
沙发
liyanguestc [专家分：90] 发布于 2006-08-24 10:37:00
#include <algorithm>
int Majority (int vote[], int n)
{int i,tmp;
tmp=n/2;
int flag=0;
sort(vote,vote+n);
for(i=1;i<=(n+1)/2;i++)
if(vote[i-1]==vote[i+tmp-1])
{flag=vote[i-1];
break;
}
return flag;
}
晕啊!没隐藏
板凳
batmanlf [专家分：0] 发布于 2006-08-24 10:45:00
晕 我先看到的
3 楼
jackin0627 [专家分：1270] 发布于 2006-08-24 10:46:00
晕怎么没隐藏
//Vc++6.0
//////////////////////////////
int Majority(int vote[],int n)
{
int maxt=0; //最多的出现次数
int atms=0;
int t,m;
int i,j;
for(i=0;i<n;i++) //逐个计算并比较,实际上i不会超过n/2就会跳出
{
m=vote[i];
if(!m)continue; //若m==0说明vote[i]已经计算过了
t=1;
for(j=i+1;j<n;j++)
{
if(vote[j]==m)
{
vote[j]=0; //置0,表示已经计算过
t++;
}
}
if(t>maxt)
{
maxt=t;
atms+=maxt;
}
if(maxt>n/2)
{
return maxt;
}
else if(atms>n/2) //atms为已经计算过的数的总个数,若此数超过n/2,
//那么就算剩下的数全是一个数,也不会满足条件.
{
return 0;
}
}
return 0;
}
4 楼
wlsss [专家分：150] 发布于 2006-08-24 11:06:00
第一题答案：
int Majority (int vote[], int n)
{
int num,count;
int i,j;
for(i=n-2;i>=0;i--)
{
for(j=0;j<=i;j++)
{
if(vote[j]>vote[j+1])
{
int t;
t=vote[j];
vote[j]=vote[j+1];
vote[j+1]=t;
}
}
}
if(n%2==0)
{
if(vote[n/2-1]==vote[n/2])
{
num=vote[n/2-1];
count=2;
for(i=n/2-2;vote[i]==num;i--,count++);
for(i=n/2+1;vote[i]==num;i++,count++);
}
else
return 0;
}
else
{
num=vote[(n-1)/2];
count=1;
for(i=(n-1)/2-1;vote[i]==num;i--,count++);
for(i=(n-1)/2+1;vote[i]==num;i++,count++);
}
if(count>n/2)
return count;
return 0;
}
5 楼
batmanlf [专家分：0] 发布于 2006-08-24 11:10:00
刚写好没
第一次参赛
void QuickSort(int * array,int left,int right);
int Divide(int * array,int left,int right);
void Maopao(int *arry, int n);
int Majority (int vote[], int n)
{
if(n > 50)
{
QuickSort(vote, 0, n-1);
}
else
{
Maopao(vote, n);
}
int buf = 1;
for(int i =0; i < n; i++)
{
for(int k = i+1; k < n; i++)
{
if(vote[i] == vote[k])
{
buf++;
}
else
{
if(buf > n/2)
{
return buf;
}
else
{
buf = 1;
}
break;
}
}
}
return 0;
}
void QuickSort(int * array,int left,int right)
{
if(left<right)
{
int pivotIndex = Divide(array,left,right);
QuickSort(array,left,pivotIndex-1);
QuickSort(array,pivotIndex+1,right);
}
}
int Divide(int * array,int left,int right)
{
int x = array[left];/*选择基准记录*/
int low = left ,high = right;
while(low < high)
{
while(low < high && array[high] >= x) high--; /*high从右到左找小于x的记录*/
if(low < high)/*找到小于x的记录则交换*/
{
array[low] = array[high];
low++;
}
while(low < high && array[low] < x) low++; /*low从左到右照大于x的记录*/
if(low < high)/*找到大于x的记录则交换*/
{
array[high] = array[low];
high--;
}
array[low] = x; /*将基准记录保存到 low=high的位置*/
return low;
}
}
void MaoPao(int *array, int n)
{
int temp;
for(int i = 0; i < n; i++)
{
for( int k = i+1; k < n; k++)
if (array[i] > array[k])
{
temp = array[i];
array[i] = array[k];
array[k] = temp;
}
}
}
6 楼
01835cwj [专家分：1900] 发布于 2006-08-24 11:16:00
///////////////////////////////////////////////////////////////
//半数问题:
// vote[5] = {1,8,1,100,1}; 其大小为 5。
// 因为自然数1的个数为3，超过半数，那么调用Majority将返回 3。
// 题目要求：编写规定函数接口 Majority。
///////////////////////////////////////////////////////////////
#include<iostream>
#include<algorithm>
using namespace std;
int Majority(int vote[], int n)
{
int m = 0;
sort(vote,vote+n); //对数组排序
int length=1;
for(int i=1;i<n;i++)//求出相同元素的最大数目
{
if(vote[i]==vote[i-length])
length++;
}
if(length > n/2)
return m = length;
return m;
}
//测试函数
void main()
{
int b[5] = {1,8,1,100,1};
cout<<Majority(b,5)<<endl;
int a[8] = {1,8,1,100,1,3,7,6};
cout<<Majority(a,8)<<endl;
}
[em5]
7 楼
tenm [专家分：330] 发布于 2006-08-24 11:22:00
int Majority (int vote[], int n)
{
int i,j,iCount;
for(i=0;i<n;i++){
iCount=0;
for(j=i+1;j<n;j++){
if(vote[i]==vote[j]) iCount++;
if((iCount+1)>n/2) return (iCount+1);
}
}
return 0;
}
int Count (int f[], int g[], int m, int n)
{
int i,j,iCount=0,iFlag=0;
for(i=0;i<m;i++){
for(j=iFlag;j<n;j++){
if(f[i]==g[j]){
iCount++;
iFlag=j+1;
break;
}
}
}
return iCount;
}
8 楼
wlsss [专家分：150] 发布于 2006-08-24 11:24:00
赠送题答案：
int Count (int f[], int g[], int m, int n)
{
int count=0;
int i,j;
for(i=0,j=0;i<m && j<n;)
{
if(f[i]==g[j])
{
i++;
j++;
count++;
}
else if(f[i]<g[j])
i++;
else
j++;
}
return count;
}
9 楼
BigCarrot [专家分：10] 发布于 2006-08-24 11:29:00
给个n的范围
10 楼
batmanlf [专家分：0] 发布于 2006-08-24 11:30:00
这个才对
void QuickSort(int * array,int left,int right);
int Divide(int * array,int left,int right);
void MaoPao(int *arry, int n);
int Majority (int vote[], int n)
{
if(n > 50)
{
QuickSort(vote, 0, n-1);
}
else
{
MaoPao(vote, n);
}
int buf = 1;
for(int i =0; i < n; i++)
{
for(int k = i + 1; k < n; k++)
{
if(vote[i] == vote[k])
{
buf++;
}
else
{
if(buf > n/2)
{
return buf;
}
else
{
buf = 1;
}
break;
}
}
}
return 0;
}
void QuickSort(int * array,int left,int right)
{
if(left<right)
{
int pivotIndex = Divide(array,left,right);
QuickSort(array,left,pivotIndex-1);
QuickSort(array,pivotIndex+1,right);
}
}
int Divide(int * array,int left,int right)
{
int x = array[left];/*选择基准记录*/
int low = left ,high = right;
while(low < high)
{
while(low < high && array[high] >= x) high--; /*high从右到左找小于x的记录*/
if(low < high)/*找到小于x的记录则交换*/
{
array[low] = array[high];
low++;
}
while(low < high && array[low] < x) low++; /*low从左到右照大于x的记录*/
if(low < high)/*找到大于x的记录则交换*/
{
array[high] = array[low];
high--;
}
array[low] = x; /*将基准记录保存到 low=high的位置*/
return low;
}
}
void MaoPao(int *array, int n)
{
int temp;
for(int i = 0; i < n; i++)
{
for( int k = i+1; k < n; k++)
if (array[i] > array[k])
{
temp = array[i];
array[i] = array[k];
array[k] = temp;
}
}
}
我来回复
您所在位置：