2012年华为编程大赛算法实现

#第一题就餐问题
def check_lunch(num, time, input):
    for i in range(num):
        if ((i + 1) % time != 0 and input[i] != (i + 1) % time):
            input[i] = 0
        elif ((i + 1) % time == 0 and input[i] != time):
            input[i] = 0;
    return input
num = 11;
#第二题输入联想
def auto_complete(str, tmp):
    arr = str.split(‘ ‘)
    n = len(tmp)
    m = len(arr)
    count = [0, 0]
    maxIndex = 0
    output = []
    err =0
    for i in range(n):
        for j in range(m):
            if (tmp[i] == arr[j][i]): count[j] += 1
    #print(err)
    maxNum = max(count)
    for i in range(m):
        if(tmp[0] != arr[i][0]): err +=1
        if(err == 2):return ""
        if(count[i] == maxNum):
            output.append(arr[i]+" ")
    return output;
def findStr(pattern,str):
     lenStr = len(str)
     lenPat = len(pattern)
     i=0
     j=0
     start = -1
     step = 0
     while(i         if(str[i] != pattern[j]):
             i = i+1
             j = 0
             step =0
         else:
             i = i+1
             j = j+1
             step = step+1
             if(step == lenPat):
                 return i-step,i
     return -1,0
pats=[["if","then"],
          ["switch","case","end"],
          ["do","while"]]
def analysize2(str):#第三题语法分析
    lenStr = len(str)
    lenPat = len(pats)
    i =0;
    count = 0
    results = []
    while(i        for j in range(0,lenPat):
            result = findPat(pats[j],str)
            if(result[0]>0):
                results.append(result)
        if(results ==[]):break
        minItem=(0,lenStr,0)
        for item in results:
            if(item[1]                minItem = item
        if(minItem[0]==0 or minItem[2]>=lenStr):
            break
        count += minItem[0]
        start = minItem[2] +1
        str = str[start:]
        i += minItem[2] +1
        results.clear()
    return count
def findPat(pattern,str):
    str0 = str
    lenP = len(pattern)
    lenStr = len(str)
    k ,count= 0,0
    i=0;j=0
    start =0
    end = 0
    while(k        i1,j1=findStr(pattern[k],str)
        if(i1!=-1):
            #start.append(i1+j)
            start = i1 +j
            i=j+i1
            j=j+j1
            k=k+1
            str = str0[j:]
            m,n=findStr(pattern[k],str)
            if(m!=-1):
                k=k+1
                i,j = j+m,j+n
                str = str0[j:]
                if(k==lenP):
                    count =count+1;
                    end=j-1
                    #k = 0
        else:
            break
    return count,start,end;
str = "switch if sdfas then case then if adb switch case then"
print(check_lunch(11,3,[1,2,3,3,1,3,1,1,1,1,2,3]))
print(check_lunch(11,4,[1,2,3,4,2,3,3,4,1,2,3]))
print(auto_complete("chengdu chongqing","c"))
print(auto_complete("chengdu chongqing","che"))
print(auto_complete("chengdu chongqing","jing"))
print(analysize2("if then"))
print(analysize2("switch case aaa"))
print(analysize2("if (aaa) then do bbb while switch cas"))

1. 就餐抽查（30分） 

 问题描述：  

某公司由于人多，午餐分为多批次就餐，严格要求每批次就餐时间。并定期抽查就餐情况。请编写程序实现就餐抽查情况。 

要求实现函数：  

void check_lunch(int num, int time,int input[], int output[]) 

【输入】  int num，就餐总人数           int time，就餐分批数           char input[]，就餐情况 【输出】  char 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] 

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 

输出：end = Chengdu  

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

输出：end =     

 3. 语法分析（40分） 

 问题描述：  

编译器通过语法分析来检测程序的一些语法问题。要求实现一个简单的语法分析程序，判断输入的字符串是否有符合要求的语法组合。 

需要判断的语法组合有： if  then 

if  ( )  then switch case end switch ( ) case end 

switch ( ) case default end 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 

本文出自 “tech” 博客，请务必保留此出处http://freemanwest.blog.51cto.com/1137962/1657486