西瓜田 » 华为

第五届华为“创新杯”编程大赛初赛题目（第一场）

suika — Sat, 11 May 2013 05:03:29 +0000

分了两场，每场三道题
这次华为终于用online judge了 OTL…… 难度也是比去年的提高了不少（去年题还都停留在字符串操作上见：http://blog.thpiano.com/?p=543）
不过就是华为那边服务器运行结果慢如牛，比完了都不知道结果……
顺便所有题都没有输入输出范围，部分题意也有些含糊
先把题目和自己的烂代码贴一下吧

第二题：容量转换

自己的代码wa了，找不到wa在哪，求各位指点……
最大数字应该是2的60次方，double也应该存的下才对，难道要大数乘法 OTL

第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;
}

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

寻找最大的非重复数

suika — Sun, 15 Apr 2012 07:50:50 +0000

好像好久都没在编程栏目下投新稿了（

那就来篇水点的，顺便测试下代码高亮插件

报了华为编程大赛，找了去年的题，看到了这道：

如果一个数字十进制表达时，不存在连续两位相同，则称之为“不重复数”。
例如，105、1234和12121都是“不重复数”，而11、100和1225不是。
给定一个正整数A，返回大于A的最小“不重复数”。A小于100000

初见一看，从所给之数开始依次加一，判断新的数是否是重复数就行了，可谓是最笨而又保险的做法

很快写完后，恰好有友人过来一同讨论，是否有更优的算法呢？

先从这个每步+1着手，诸如122421这样的数，千位和万位重复，再从个位加真是太累了；于是改成从高位向低位遍历，遇到重复的邻近位就把低位+1，至少效率会比+1好多了；

对122421采用这种做法，会+1000变成123421，看上去的确是不重复了，但却丢失了最小性（最小的应该是123010）

因此，在修改重复位之后，还需要把低位重置，重置成0、1相邻的序列，就能弥补最小性了

例如122121，先+1000变为123121，再从123后面填入序列，得到123010；

例如120014，先+100变为120114，再从1201后面填入序列，得到120101

在这种做法下，循环数量可谓是大大减少了，很多情况下更是一步到位；但是依然没有摆脱“自增修改->判断是否为重复数”的循环试探法

要得到一步到位的稳定法，还需考虑进位的情况：

例如1219922，在遍历到9并+100后，变为1220022，会对已遍历过的高位引入新的重复；此时再将遍历位回退2位重新遍历，即能解决进位带来的不稳定情况

总结一下，最终一步到位的算法步骤为：

1.将原数+1得到目标数字

2.对目标数字从高位向低位遍历，若未发现邻近重复数字，则转入步骤4；否则将2个重复数字中的低位数字+1，并记录重复处之后的低位位数

3.遍历位置回退2，重复步骤2

4.若记录了重复处之后的低位位数，则将这些低位用0、1相间的序列进行填充；返回修改后的目标数字

顺便附上输入数据为整形时的代码（c++字符串的代码有点长就不贴了）：

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

unsigned int GetNotRepeatNum(unsigned int lValue){
int temp, aim = lValue + 1;
int divide = pow(10.0f, int(log10(double(aim))) - 1);
while (divide >= 1){
temp = (aim / divide) % 10;
if (temp == (aim / (divide * 10)) % 10){
aim = (aim / divide + 1) * divide;
if (temp == 9){
divide *= 100;
}
}else{
divide /= 10;
}
}
return aim;
}

最后发现自己实在是太罗嗦了，其实本篇就是一道可以用一句话来概括的水题，“高位到低位扫描，遇到相邻位相同，低位+1，低位后面的全置为0；重复上述直至十位与个位不同”，当然也可以用三个字，“构造法”

最近一段时间也是老夫聊发少年狂，刷了些oj，弥补以前的遗憾；不过也只能从实效性下手，无暇追求排名与AC数了。新手上道，挫折无限，还需多多修炼

西瓜田 » 华为

第五届华为“创新杯”编程大赛初赛题目（第一场）

第一题：磁盘数据恢复（点此展开）

第一题自己的AC代码

第二题：容量转换

第二题自己的代码

第三题：判断给定的数字是否满足给定的条件

第三题自己的代码

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

寻找最大的非重复数