首页 > 代码库 > 2014第六届华为编程大赛初赛第四轮
2014第六届华为编程大赛初赛第四轮
/***********************************************************************
第一题 求n个整数的最大公约数
输入
第一行： n个整数
第二行：各个整数 以空格隔开
输出；公约数
例子：
input: 4
10 15 20 25
output: 5
**********************************************************************/
#include <stdio.h>
//转转相除法
int gcd(int x, int y)
{ //非递归形式
int rst=-1;
while(y)
{
rst=y;
y=x%y;
x=rst;
}
return rst;
//递归形式
// return (y == 0) ? x : gcd(y, x % y);
}
//求最小公倍数 lowest common multiple ( LCM )
//先得到两个数的最大公约数，然后用两个数的乘积除以该公约数
//比如 lcm(10,15) =10*15/gcd(10,15)=150/5=30;
int lcm(int x,int y)
{
int rst=gcd(x,y);
return (x*y)/rst;
}
//获取n个整数的最大公约数
int Getgcd(int a[],int len)
{
int rst=gcd(a[0],a[1]);
for(int j=2;j<len;j++)
rst=gcd(a[j],rst);
return rst;
}
//获取n个整数的最小公倍数
int GetLcm(int a[],int len)
{
int rst=lcm(a[0],a[1]);
for(int j=2;j<len;j++)
rst=lcm(a[j],rst);
return rst;
}
int main()
{
int num;
scanf("%d",&num);
int *a=new int[num];
if(NULL==a)
return -1;
int i=0;
char ch;
while(scanf("%d%c",&a[i++],&ch)!=EOF)
{
if(ch==‘\n‘)
break;
}
int rst;
if(num==1)
rst=a[0];
else
{
printf("%d\n",Getgcd(a,num)); //最大公约数
// printf("最小公倍数：%d\n",GetLcm(a,num));
}
delete [] a;
a=NULL;
return 0;
}第二题 实现一个开放的书名检索库 | |||
描述: | 实现一个开放的书名检索库，库中存储了若干个书名 用户可以： 重要格式说明 书名： 第一个单词前和最后一个单词后没有空格 搜索条件： 输出说明: 1. 如果没有查找到书名，那么输出一对双引号： "" 2. 如果存在多行输出（查找到多本书名），那么输出结果按字典序排序 举例 输入: AddBooks "extensions gnu" End 输出： "writing gnu emacs extensions" 输入: AddBooks "approach" End 输出： "aspect oriented analysis and design the theme approach" "net test automation recipes a problem solution approach" 规格 0<=书名个数范围<=200
|
| |
运行时间限制: | 无限制 | ||
内存限制: | 无限制 | ||
输入: | AddBooks [书名列表:每行一个书名，书名在双引号中] SearchBooks [关键字:多个关键字用空格分隔，关键字在双引号中] End
| ||
输出: | 1. 查找到的书名，查找到多个书名，以多行显示，书名在双引号内 2. 如果没有查找到书名，那么输出： "" 3. 如果存在多行输出（查找到多本书名），那么输出结果按字典序排序 如下： "aspect oriented analysis and design the theme approach" "net test automation recipes a problem solution approach"
如果一个字符相等，那么顺序比较后面的字符，直到找到一个字符不相等为止 | ||
样例输入: | AddBooks "high performance mysqlsecond edition" "writing gnu emacs extensions" "web client programming with perlautomating tasks" "net test automation recipes a problem solution approach" "photoreading" "pro wfwindows workflow in net" "aspect oriented analysis and design the theme approach" SearchBooks "extensions gnu" End | ||
样例输出: | "writing gnu emacs extensions" | ||
答案提示: |
| ||
#include <stdio.h>
#include <string.h>
int stringcmp(const void *elem1, const void *elem2 )
{
return strcmp((char*)elem1,(char*)elem2);
}
int main()
{
char BookName[200][510];
char searchkey[3][50];
char strtmp[510];
gets(strtmp);
if(strcmp(strtmp,"AddBooks")!=0)
return -1;
int index=0;
while(gets(strtmp)!=NULL)
{
if(strcmp(strtmp,"SearchBooks")==0)
break;
else
strcpy(BookName[index++],strtmp);
}
int len1=index;
index=0;
int len2=0;
while(gets(strtmp)!=NULL)
{
if(strcmp(strtmp,"End")==0)
break;
else {
char *p=strtok(strtmp+1," \"");
while(p){
strcpy(searchkey[index++],p);
p=strtok(NULL,"\"");
len2++;
}
}
}
char pos[200][510];
memset(pos,-1,sizeof(pos));
bool flag[3];
memset(flag,0,3);
int k;
index=0;
for(int i=0;i<len1;i++)
{
bool sum=true;
memset(flag,0,3);
k=0;
for(int j=0;j<len2;j++)
{
if(strstr(BookName[i],searchkey[j]))
flag[k++]=true;
else
break;
}
for(k=0;k<len2;k++)
sum &=flag[k];
if(sum)
strcpy(pos[index++],BookName[i]);
}
int len3=index;
if(0==len3)
puts("\"");
else
{
qsort(pos,len3,510,stringcmp);
for(k=0;k<len3;k++)
puts(pos[k]);
}
return 0;
}
大华为的服务器 太卡... 第二题没测试。