第4届华为编程大赛初赛试题

suika — Sun, 22 Apr 2012 08:49:56 +0000

RT，就是今天上午刚举办的比赛，周同学在赛后留了一份题目的拷贝，正好借来做记录
c/c++和java的题目应该是一样的
整体来说还是字符操作为主的基础题，不过做得真是太郁闷，最后一题的规则数组竟然开小了（低维的长度应该是7，误开成6了），满盘皆输
决赛基本无望= = 还需多多修炼啊

题后顺便附上自己土土的c/c++代码

1. 就餐抽查（30分）
• 问题描述： 
某公司由于人多，午餐分为多批次就餐，严格要求每批次就餐时间。并定期抽查就餐情况。
请编写程序实现就餐抽查情况。
• 要求实现函数： 
void check_lunch(int num, int time,int input[], int output[])
【输入】  int num，就餐总人数
         int time，就餐分批数
         int input[]，就餐情况
【输出】  int output[]， 违规就餐情况
【返回】  无
注：对就餐分3批的情况，12人就餐，正确的就餐情况应如下分布：
[1,2,3,1,2,3,1,2,3,1,2,3]，不符合该分布的即是违规，输出时对相应位置0。
• 示例 
1）输入：num = 12，time = 3，input =[1,2,3,3,1,3,1,1,1,1,2,3]
输出：output = [1,2,3,0,0,3,1,0,0,1,2,3]

2）输入：num = 11，time = 4，intput = [1,2,3,4,2,3,3,4,1,2,3]
输出：output = [1,2,3,4,0,0,3,4,1,2,3]

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void check_lunch(int num, int time,int input[], int output[])
{
if (time < 1){
memset(output, 0, num * sizeof(int));
return;
}
for (int i = 0; i < num; ++i){
if (input[i] != (i % time) + 1){
output[i] = 0;
}else{
output[i] = input[i];
}
}
}

-------------------------------------------------------------------------------------------

2. 输入联想（30分）
•问题描述： 
输入联想功能是非常实用的一个功能，请编程实现类似功能。
•要求实现函数： 
void auto_complete(char *str, char *tmp,char *output)
【输入】  char *str，候选字符串
          char *tmp，输入字符串
【输出】  int *output，联想匹配的字符串
【返回】  无
注：候选字符串以空格隔开，输入字符串仅从字符串开始处匹配。
将匹配的子字符串输出，同样以空格隔开。
如无匹配成功的子字符串，则输出空字符串。
•示例 
1）输入：str = chengdu chongqing，tmp = c
输出：output = chengdu chongqing

2）输入：str = chengdu chongqing，tmp = che
输出：output = chengdu

3）输入：str = beijing nanjing，tmp = jing
输出：output =

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void auto_complete(char *str, char *tmp, char *output)
{
char* str_copy = strdup(str);
char* token = strtok(str_copy, " ");
int tipLength = strlen(tmp);
output[0] = '\0';
while (token){
if (strncmp(token, tmp, tipLength) == 0){
strcat(output, token);
strcat(output, " ");
}
token = strtok(NULL, " ");
}
if (strlen(output) > 0){
output[strlen(output) - 1] = '\0'; // remove the last space
}
free(str_copy);
}

-------------------------------------------------------------------------------------------

3. 语法分析（40分）
•问题描述： 
编译器通过语法分析来检测程序的一些语法问题。
要求实现一个简单的语法分析程序，判断输入的字符串是否有符合要求的语法组合。
需要判断的语法组合有：
if  then
if  ( )  then
switch case end
switch ( ) case end
switch ( ) case default end
do while

if  then ( ) switch case end default do while

•要求实现函数： 
void analysis(char *str,int *num)
【输入】  char *str，待分析字符串      
【输出】  int num，匹配的组合个数
【返回】  无
注：输入字符串中关键字以空格隔开，"if"、"("、")"、"case"等均表示关键字。
从左向右，找到匹配的组合即可。
组合一定是相互分离，不会嵌套，不会有交叉情况出现。
•示例 
1）输入：str = if then，
输出：num = 1

2）输入：str = switch case aaa ，
输出：num = 0

3）输入：str = if ( aaa ) then do bbb while switch cas ，
输出：num = 2

和第二题感觉有点重复，还好规则不会嵌套，所以写得很土也可以过（

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

void analysis(char *str,int *num)
{
char* words[] = {"if", "then", "(", ")", "switch", "case", "end", "default", "do", "while"};
int wordsNum = 10;
int rules[6][7] = { {2, 0, 1},
{4, 0, 2, 3, 1},
{3, 4, 5, 6},
{5, 4, 2, 3, 5, 6},
{6, 4, 2, 3, 5, 7, 6},
{2, 8, 9} };
//"rules[x][0] = v" means there are v keywords in rule x
int rulesNum = 6;
int rev[255];
int revNum = 0;
(*num) = 0;
char* str_copy = strdup(str);
char* token = strtok(str_copy, " ");
while (token){
for (int i = 0; i < wordsNum; ++i){
if (strcmp(token, words[i]) == 0){//check if the current word is a keyword
rev[revNum++] = i;
for (int j = 0; j < rulesNum; ++j){//check every rules
if (revNum < rules[j][0]){
continue;
}
bool found = true;
for (int k = 0; k < rules[j][0]; ++k){
if (rules[j][k + 1] != rev[revNum - rules[j][0] + k]){
found = false;
break;
}
}
if (found){//it fits a rule
revNum = 0;
++(*num);
break;
}
}
break;
}
}
token = strtok(NULL, " ");
}
free(str_copy);
}

最后很好奇，如果第二题写：

1
2
3
4

void auto_complete(char *str, char *tmp, char *output)
{
strcpy(output, str);
}

第三题写：

1
2
3
4

void analysis(char *str,int *num)
{
*num = 0;
}

交上去，会拿到多少分呢？（比赛是机器阅卷，估计会以各测试用例的正确性来评分）

西瓜田 » 比赛

第4届华为编程大赛初赛试题