主题：第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个回复）
11 楼
01835cwj [专家分：1900] 发布于 2006-08-24 11:42:00
////////////////////////////////////////////////////////////////////////
//赠送题：
// 已知f[]和g[]两个数组，大小分别为m和n，其中的元素都已经从小到大排列，
// 且每个数组内的元素都各不相同。
// 规定函数接口：int Count (int f[], int g[], int m, int n)
// 函数Count返回两个数组中有多少组元素相同。
/////////////////////////////////////////////////////////////////////////
#include<iostream>
using namespace std;
int Count (int f[], int g[], int m, int n)
{
int i = 0;
int j = 0;
int cnt = 0;
while(i != m&&j!=n)//数组已经排列好了，只需考虑三种情况
{
if(f[i] > g[j])
j ++;
else if(f[i] < g[j])
i ++;
else //f[i] ==g[j]
{
i++;
j++;
cnt++;
}
}
return cnt;
}
//测试函数
void main()
{
int a[5] = {1,3,4,7,9};
int b[4] = {3,5,7,8};
cout << Count(a,b,5,4) <<endl;
}
我自我感觉这到题的算法还是蛮好的。
很欣赏自己了，呵呵~~~~~~
12 楼
batmanlf [专家分：0] 发布于 2006-08-24 11:42:00
/////////////////////////////////////////////////////////////////////////////
//赠送题：
// 已知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。
//////////////////////////////////////////////////////////////////////////////////////
int Count (int f[], int g[], int m, int n)
{
int flag = 0;
int temp = 0;
for(int i = 0; i < m; i++)
{
for( int k = temp; k < n; k++)
{
if(f[i] == g[k])
{
flag++;
temp = k;
break;
}
}
}
return flag;
}
13 楼
01835cwj [专家分：1900] 发布于 2006-08-24 11:46:00
伤感情。
我以为我这么好的算法就我一个人，没想到8楼的兄弟捷足先登了。
唉~~~~~~~
14 楼
elva6401 [专家分：1920] 发布于 2006-08-24 13:24:00
怎么搞的?没有隐藏,题目是不是有点简单.
还有赠送题代码怎么这么像
if(f[i]==g[j])
{
i++;
j++;
count++;
}
else if(f[i]<g[j])
i++;
else
j++;
第35次编程比赛第一题的代码.........
if(X[p1]<Y[p2])
{
car++;
p1++;
}
else if(X[p1]==Y[p2])
{
p1++;
p2++;
}
else
{
if(car>0)
car--;
p2++;
}
15 楼
wlsss [专家分：150] 发布于 2006-08-24 13:37:00
第一题答案（改进）：
#include <stdio.h>
int Majority (int vote[], int n);
int GetFirstNum(int vote[],int num,int first,int last);
int GetLastNum(int vote[],int num,int first,int last);
void main()
{
//添加测试函数
}
int Majority (int vote[], int n)
{
int num;
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;
}
}
}
num=vote[n/2];
return GetLastNum(vote,num,n/2,n-1)-GetFirstNum(vote,num,0,n/2)+1;
}
int GetFirstNum(int vote[],int num,int first,int last)
{
if(first+1==last)
{
if(vote[first]==num)
return first;
return last;
}
else
{
int n=(first+last)/2;
if(vote[n]==num)
return GetFirstNum(vote,num,first,n);
else
return GetFirstNum(vote,num,n,last);
}
}
int GetLastNum(int vote[],int num,int first,int last)
{
if(first+1==last)
{
if(vote[last]==num)
return last;
return last;
}
else
{
int n=(first+last)/2;
if(vote[n]==num)
return GetFirstNum(vote,num,n,last);
else
return GetFirstNum(vote,num,first,n);
}
}
16 楼
neverPE [专家分：1620] 发布于 2006-08-24 13:51:00
麻烦各位，回复隐藏之前不要再提交了。
17 楼
joekings [专家分：550] 发布于 2006-08-24 15:50:00
//第一题
#include <stdio.h>
#include <stdlib.h>
int compare( const void *arg1, const void *arg2 );//辅助函数
int Majority (int vote[], int n)
{
int i;
int count=1;
qsort((void*)vote,n,sizeof(int),compare);
for(i=1;i<n;i++)
{
if(vote[i]==vote[i-1])
{
count++;
if(count>n/2)
break;
}
else
count=1;
}
if(count>n/2)
return count;
else
return 0;
}
int compare( const void *arg1, const void *arg2 )
{
int *p1=(int*)arg1;
int *p2=(int*)arg2;
if(*p1>*p2)
return 1;
if(*p1<*p2)
return -1;
return 0;
}
//编译器VC6.0
int main()//自己写的测试函数
{
int arry[] = {6,5,6,8,1,6,6};
int n,m;
n=sizeof(arry)/sizeof(int);
m=Majority(arry,n);
printf("\n %d \n",m);
return 0;
}
18 楼
rickone [专家分：15390] 发布于 2006-08-24 16:09:00
1.
#include <memory.h>
typedef struct {
int n;
int count;
}hnode;
#define hashLength (0x100000)
#define hashBoard (0xfffff)
hnode hashTable[hashLength];
int GetZobristKey(int n)
{
static __int64 Zobrist[128]={
0xB3A383B2FCE17F73,0x8C46D1049A35048F,0xB41750F46824F8CF,0xCF32FDB9DF62D2DF,
0x7D826B719E360CCA,0x97EF35332E927DC9,0xC87A93CC79F2505B,0x8DD261543FB1314B,
0x31650E9BAEB448F7,0x9BCB5413BB005513,0x2C4D48D4261F9D64,0x4BF970A344EFF012,
0x739C875AD7CC94A8,0xCB32AEE2F89BB0BC,0x04D3CAAFEF4E00FC,0x4D69283B8FDFFF31,
0x475FDAB869DE769C,0x66AA2BC70B0687B3,0x7F97C647525B4ECB,0xC73770FCBFE527C2,
0xB448575DA377F098,0x358E7BD99C17FC43,0xE8BBF52CE87A40BA,0x5D256F94155B3C7A,
0x605A39665A4E88FE,0xA6369A45615839AB,0x61B414DD1B533E0D,0xA18DC5176E712D51,
0x2693633B269347DB,0xBCA57448ABE616C0,0x00966B0B8B14F66F,0x7FD350813D9E4072,
0x31E4FB522FF6E82F,0x77A4CA48A1C0BC46,0x9FE726FD46A01184,0xF94001541A51AE23,
0xA4CDBF07BCBF7D12,0xD47E59EAC1B38EBD,0x26CEEFD7F5B5321B,0x1C724B268BA0E0F6,
0x5553DA71A2FCCB55,0x1915611050B69D28,0x91FAEFE414F88D03,0x9F3ECA25ACDC9A30,
0xA5921526BBA49636,0x8C918A0551A9D2E3,0x84D1ACF2642A54FF,0x0320A8BB4C2139FA,
0x00C5240D77A420F7,0x468D5072A7252E35,0xAB44FD96A63F395B,0xAC1A560A23126B76,
0x04C4F046B7102431,0x3CB8EF7CFEAC3A43,0xB4166B87D36039A0,0xD2271D88C96E7584,
0xE01CA2C8025076D4,0x36FFE8D026BF0D97,0x2BA252E7DD5D0CB6,0xB5152F9201916E54,
0xEC8D456A4508AB82,0xD23434B86E1F0C11,0xFF210E9325605BEA,0xFAF8AAEAFF64942E,
0x0E0FC8842B7AE1DC,0x393F2B25ADB9ADAC,0xF0768179C4691280,0xA111375E489A0941,
0xDE603DE5418E0BBC,0xBCB535BD9C1F87E4,0xC2774CE6C54800CA,0x672EC147CF993488,
0x2D0D1884F3D4E645,0xF10E5AF10B11DD05,0x65AE03CF70B51369,0x1D9CE620E8040533,
0xDBF6416292D6E797,0x7B4AB20DAF5CED77,0xEDA9AB22CB735E93,0xBD89A214B5415BA4,
0xA056D14D78085F97,0x3412D04812414EA9,0x96BDD72766873D55,0xB3EACE97B34CD538,
0xB0533FC66D230D6E,0xC96F3ECF4D3284CB,0xA451B5B3A13DC4DA,0x46F101E2F9203CA8,
0xE4F2D6B9750C6880,0x86DF09D22F6D2190,0x5FA055967D58CB7C,0x7DDD5F95D58EDE80,
0x58BE3B5916FADE50,0x6C0878A36D92A613,0xFF0B7AD52536C45A,0x7376EA4265A70100,
0x0AB1DBF24BCF4302,0x39E5FEBC7B556939,0xBDDB500B43C9AE3A,0x7AF4E5FBC581C0B1,
0x8DCC12B22CEBB710,0x9E6075D0AF12C1E6,0xEC84449E4EFC5710,0xFF56DBDE7ADD907A,
0x4D23CD74857D4050,0x2686B0D44F65B534,0x41796831E3893320,0x855FCEB1B9939DB2,
0x6C578AAC65995775,0x1F2B781D2AE068F1,0x326892E5535A0860,0xB7F1306E227458D8,
0xCCAB7B0DD754A8F4,0x0C0DFE6859A69978,0x9E0EAA98857BAD51,0xE6F528C49BBB6170,
0x3E80987DD5DC4A9A,0xDD85DEEAC8E75443,0x8E755558484D1CCF,0xE0CCBCBDE3BF1661,
0x676D81D7A6B6A49C,0x8CA4B46030A8361E,0x5BBA689435951CD6,0x8E31673D7D8C0A5D,
0x64B2EBA8B4AD4EDE,0x45EC592213786D2F,0xF766657E48C5BA16,0x389EB2A097989BAF,};
__int64 key=0x0;
while(n!=0)
{
key^=Zobrist[n & 0x7f];
n>>=7;
}
return (int)(key & 0x7fffffff);
}
int RecordHash(int n)
{
int key=(GetZobristKey(n) & hashBoard);
while(hashTable[key].n!=n && hashTable[key].n>0)
{
key=(GetZobristKey(key) & hashBoard);
}
if(hashTable[key].n==0)
hashTable[key].n=n;
return ++(hashTable[key].count);
}
int Majority (int vote[], int n)
{
memset(hashTable,0,hashLength*sizeof(hnode));
for(int i=0;i<n;++i)
{
int count=RecordHash(vote[i]);
if(count>n/2)
{
int then=vote[i];
for(i++;i<n;++i)
{
if(vote[i]==then)
++count;
}
return count;
}
}
return 0;
}
2.
int Count (int f[], int g[], int m, int n)
{
int *pf=f,*pg=g,*fend=f+m,*gend=g+n;
int c=0;
while(pf!=fend && pg!=gend)
{
if(*pf<*pg)
{
pf++;
}
else if(*pf>*pg)
{
pg++;
}
else
{
pf++;
pg++;
c++;
}
}
return c;
}
19 楼
joekings [专家分：550] 发布于 2006-08-24 16:13:00
//赠送题：
int Count (int f[], int g[], int m, int n)
{
int i,j,temp;
int count=0;
temp=0;
for(i=0;i<m;i++)
{
j=temp;
for(;j<n;j++)
{
if(f[i]==g[j])
{
count++;
temp=j+1;
break;
}
if(f[i]<g[j])
{
if(j>0)
temp=j-1;
else
temp=j;
break;
}
continue;
}
if(j==n) break;
}
return count;
}
20 楼
ghbxx2004 [专家分：610] 发布于 2006-08-24 16:38:00
第一题的答案 在VC6.0下编译通过
##include "stdafx.h"
#include "iostream.h"
#include "stdio.h"
#include "time.h"
int Majority (int vote[], int n)//半数问题的主函数，返回一个整型值
{
int m;//记录出现次数
int *p,*q;
for(p=vote;p<vote+n;p++)//重头开始查找
{
m=0;//每次开始前清零，防止把上一次的结果带到下一次去
for(q=p;q<vote+n;q++)
{
if(*q==*p){m++;}//进行比较，符合条件就记录
}
if(m>=(n/2)){p=vote+n;}//找到了符合条件的数就退出
}
if(m>=(n/2)){return m;}
else{return 0;}
}
int main(int argc, char* argv[])
{
clock_t start,end;
int str[10]={1,2,3,3,3,3,2,3,4,5};
start=clock();
cout<<Majority (str,10)<<endl;
end=clock();
cout<<"time is "<<(double)(end-start)<<endl;//测试该函数执行所消耗的时间
return 0;
}
我来回复
您所在位置：