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; } |
交上去，会拿到多少分呢？（比赛是机器阅卷，估计会以各测试用例的正确性来评分）
一条评论
[...] 难度也是比去年的提高了不少（去年题还都停留在字符串操作上 见：http://blog.thpiano.com/?p=543） 不过就是华为那边服务器运行结果慢如牛，比完了都不知道结果…… [...]