我来说说“顶嵌杯”全国嵌入式系统C语言编程大赛的试题

  在POJ上看见顶嵌杯的试题，虽然结束了不过我还是做了几题，分析一下贴上代码，还有2道我没有做，做完一并贴上。

Description

假设你工作在一个32位的机器上，你需要将某一个外设寄存器的第X位设置成0(最低位为第0位，最高位为第31位)，将第Y位开始的连续三位设置成110（从高位到低位的顺序），而其他位保持不变。对给定的寄存器值R，及X，Y，编程计算更改后的寄存器值R。

Input

仅一行，包括R,X,Y，以逗号","分隔，R为16进制表示的32位整数，X,Y在0-31之间且Y>=3，(Y-X)的绝对值>=3，保证两次置位不会重合

Output

更改后的寄存器值R（16进制输出）

Sample Input

12345678,0,3

Sample Output

1234567c

Source

这个题目最对位的解法当然是用位计算，我先贴上位运算的代码在来看看不是位运算的，位运算的我就不分析了，看了都能懂。

#include<stdio.h>
#include<stdlib.h>

int main(){

    long R;
    int X,Y;
    scanf("%x,%d,%d",&R,&X,&Y);

    R = ((~(1<<X)) & R);
    R = (~(1<<(Y-2))) & R;
    R = (3<<(Y-1)) | R;

    printf("%x\n",R);
    return EXIT_SUCCESS;
}

我的非位运算的算法思路其实是这样的，现在回头看过去是非一般的冗余。先以long的格式读入一个16进制的数字，注意不一定是8位的，所以在后续的时候需要用一个len来获取这个数字的长度。然后我们一位一位的获取然后根据相应的值来映射一个字符串得到这个16进制数字的字符串表示，然后处理该改变的位，再做和之前相反的操作，即再得到字符串相应的十六进制数字，注意前导零不输出的。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){

    long R;
    int X,Y,flag = 0;
    char buf[8];
    char p[32];
    char *Rp = (char *)malloc(sizeof(char)*9);
    char *sixteen_to_10[16] = {"0000","0001","0010","0011",
                              "0100","0101","0110","0111",
                              "1000","1001","1010","1011",
                              "1100","1101","1110","1111",};
    scanf("%ld,%d,%d",&R,&X,&Y);
    sprintf(Rp,"%ld",R);
    int len = 0;
    while(R){
        len++;
        R /= 10;
    }
    for(int i=0;i <len;i++)
        sscanf(Rp+i,"%c",&buf[i]);

    memset(p,'\0',32);
    for(int i=0;i <len;i++){
        switch(buf[i]){
            case '0':strcat(p,"0000");break;
            case '1':strcat(p,"0001");break;
            case '2':strcat(p,"0010");break;
            case '3':strcat(p,"0011");break;
            case '4':strcat(p,"0100");break;
            case '5':strcat(p,"0101");break;
            case '6':strcat(p,"0110");break;
            case '7':strcat(p,"0111");break;
            case '8':strcat(p,"1000");break;
            case '9':strcat(p,"1001");break;
            case 'a':strcat(p,"1010");break;
            case 'b':strcat(p,"1011");break;
            case 'c':strcat(p,"1100");break;
            case 'd':strcat(p,"1101");break;
            case 'e':strcat(p,"1110");break;
            case 'f':strcat(p,"1111");break;
        }
    }
    p[4*len-1-X] = '0';
    strncpy(p+4*len-1-Y,"110",3);

    char *pp = p;
    while(pp != p+4*len){
        for(int i=0;i <16;i++)
            if(strncmp(pp,sixteen_to_10[i],4) == 0){
                switch(i){
                    case 0:if(flag) printf("%d",i);break;
                    case 1:printf("%d",i);flag = 1;break;
                    case 2:printf("%d",i);flag = 1;break;
                    case 3:printf("%d",i);flag = 1;break;
                    case 4:printf("%d",i);flag = 1;break;
                    case 5:printf("%d",i);flag = 1;break;
                    case 6:printf("%d",i);flag = 1;break;
                    case 7:printf("%d",i);flag = 1;break;
                    case 8:printf("%d",i);flag = 1;break;
                    case 9:printf("%d",i);flag = 1;break;
                    case 10:printf("a");flag = 1;break;
                    case 11:printf("b");flag = 1;break;
                    case 12:printf("c");flag = 1;break;
                    case 13:printf("d");flag = 1;break;
                    case 14:printf("e");flag = 1;break;
                    case 15:printf("f");flag = 1;break;
                    default:printf("wrong\n");
                }
            }
        pp += 4;
    }
    printf("\n");

    return EXIT_SUCCESS;
}

Description

据说最早的密码来自于罗马的凯撒大帝。消息加密的办法是：对消息原文中的每个字母，分别用该字母之后的第5个字母替换（例如：消息原文中的每个字母A都分别替换成字母F）。而你要获得消息原文，也就是要将这个过程反过来。 

密码字母：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z M 
原文字母：V W X Y Z A B C D E F G H I J K L M N O P Q R S T U 

注意：只有字母会发生替换，其他非字母的字符不变，并且消息原文的所有字母都是大写的。

Input

最多不超过100个数据集组成，每个数据集之间不会有空行，每个数据集由3部分组成: 

1. 起始行：START
2. 密码消息：由1到200个字符组成一行，表示凯撒发出的一条消息.
3. 结束行：END

在最后一个数据集之后，是另一行：ENDOFINPUT

Output

每个数据集对应一行，是凯撒的原始消息。

Sample Input

START
NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX
END
START
N BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJ
END
START
IFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJ
END
ENDOFINPUT

Sample Output

IN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES
I WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROME
DANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE

Source

这个题是没有什么技术含量，不分析

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
int main()
{
    char buf[200];
    char *p = buf;
    memset(buf,'\0',200);
    while(fgets(buf,200*sizeof(char),stdin) != NULL){
        if(strncmp(buf,"ENDOFINPUT",10) == 0) break;
        memset(buf,'\0',200);
        fgets(buf,200*sizeof(char),stdin);
        p = buf;
        while(*p != '\0'){
            if(isalpha(*p)){
                switch(*p){
                    case 'A':*p = 'V';break;
                    case 'B':*p = 'W';break;
                    case 'C':*p = 'X';break;
                    case 'D':*p = 'Y';break;
                    case 'E':*p = 'Z';break;
                    default:*p = *p-5;break;
                }
            }
            printf("%c",*p++);
        }
        gets(buf);
        memset(buf,'\0',200);
    }
    return 0;
}


Description

有N个小孩围成一圈，给他们从1开始依次编号，现指定从第W个开始报数，报到第S个时，该小孩出列，然后从下一个小孩开始报数，仍是报到S个出列，如此重复下去，直到所有的小孩都出列（总人数不足S个时将循环报数），求小孩出列的顺序。

Input

第一行输入小孩的人数N（N<=64） 
接下来每行输入一个小孩的名字(人名不超过15个字符) 
最后一行输入W,S (W < N)，用逗号","间隔

Output

按人名输出小孩按顺序出列的顺序，每行输出一个人名

Sample Input

5
Xiaoming
Xiaohua
Xiaowang
Zhangsan
Lisi
2,3

Sample Output

Zhangsan
Xiaohua
Xiaoming
Xiaowang
Lisi

Source

这个是典型的约瑟夫环问题，解决这个问题的时候要么用链表要么是循环数组，在这里还是选择数组，因为题意的关系而且处理也快。我大概说一下如何解决，刚开始的时候把数组都设置其值为1，然后开始数数，数到的就设置为0，一直循环，到数组末就从数组头开始。代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

bool notempty(int n,int child[]){
    for(int i=1;i<n+1;i++)
        if(child[i])
            return true;
    return false;
}
int main()
{
    int n,w,s,begin;
    scanf("%d",&n);
    int child[n+1];
    char name[n+1][15];

    for(int i=1;i<n+1;i++){
        scanf("%s",&name[i]);
        child[i] = 1;
    }
    scanf("%d,%d",&w,&s);

    begin = w;
    while(notempty(n,child)){

        int i=0,j=begin;
        while(true){
            if(child[j]) i++;
            if(i == s){
                child[j] = 0;
                printf("%s\n",name[j]);
                if(j==n) begin = 1;
                else begin = j+1;
                break;
            }
            if(j==n)
                j = 1;
            else
                j++;
        }
    }
    return 0;
}


Description

世界各地有多种格式来表示日期和时间。对于日期的常用格式，在中国常采用格式的是“年年年年/月月/日日”或写为英语缩略表示的”yyyy/mm/dd”，此次编程大赛的启动日期“2009/11/07”就是符合这种格式的一个日期，而北美所用的日期格式则为“月月/日日/年年年年”或”mm/dd/yyyy”，如将“2009/11/07”改成这种格式，对应的则是”11/07/2009”。对于时间的格式，则常有12小时制和24小时制的表示方法，24小时制用0-24来表示一天中的24小时，而12小时制只采用1-12表示小时，再加上am/pm来表示上午或下午，比如”17:30:00”是采用24小时制来表示时间，而对应的12小时制的表示方法是”05:30:00pm”。注意12:00:00pm表示中午12点，而12:00:00am表示凌晨12点。 

对于给定的采用”yyyy/mm/dd”加24小时制（用短横线”-”连接）来表示日期和时间的字符串，请编程实现将其转换成”mm/dd/yyyy”加12小时制格式的字符串。

Input

第一行为一个整数T（T<=10），代表总共需要转换的时间日期字符串的数目。 
接下来的总共T行，每行都是一个需要转换的时间日期字符串。

Output

分行输出转换之后的结果

Sample Input

2
2009/11/07-12:12:12
1970/01/01-00:01:01

Sample Output

11/07/2009-12:12:12pm
01/01/1970-12:01:01am

Hint

注意中午和凌晨时间的特殊表示

Source

  这个主要是注意一些边界条件，上面的实例能过基本问题就不大

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(){

    int n,year,month,day,hour,min,sec;
    char buf[20];

    scanf("%d",&n);

    while(n-- && scanf("%s",buf) == 1){
            char ap[2];
            char m[2],d[2],h[2],mi[2],s[2];
            sscanf(buf,"%d/%d/%d-%d:%d:%d",&year,&month,&day,
                                      &hour,&min,&sec);

            if(hour>=12){
                strcpy(ap,"pm");
                if(hour >= 13)hour -= 12;
            }else{
                if(hour == 0)
                    hour += 12;
                strcpy(ap,"am");
            }
            strcpy(m,month<10?"0":"");
            strcpy(d,day<10?"0":"");
            strcpy(h,hour<10?"0":"");
            strcpy(mi,min<10?"0":"");
            strcpy(s,sec<10?"0":"");
            printf("%s%d/%s%d/%d-%s%d:%s%d:%s%d%s\n",m,month,d,day,year,
                                         h,hour,mi,min,s,sec,ap);
    }
    return EXIT_SUCCESS;
}


 Description

给定两个整数M，N，生成一个M*N的矩阵，矩阵中元素取值为A至Z的26个字母中的一个，A在左上角，其余各数按顺时针方向旋转前进，依次递增放置，当超过26时又从A开始填充。例如，当M=5，N=8时，矩阵中的内容如下：

   A   B   C   D   E   F   G   H

   V   W   X   Y   Z   A   B   I

   U   J   K   L   M   N   C   J

   T   I   H   G   F   E   D   K

   S   R   Q   P   O   N   M   L

Input

M为行数，N为列数，其中M，N都为大于0的整数。

Output

分行输出相应的结果

Sample Input

4 9

Sample Output

   A   B   C   D   E   F   G   H   I
   V   W   X   Y   Z   A   B   C   J
   U   J   I   H   G   F   E   D   K
   T   S   R   Q   P   O   N   M   L

Source

这个题很爽，我的构思时这样的，分四个操作，往右，往下，往左和往上四个连续的操作，用right，left，up和down来记录每次往各个方向所到达的极限位置。这些位置在每一次“兜圈”之后更新一次，而line和colum是记录行和列这些也是一个循环才更新一次，这里没有用VLA而是用了动态分配，显得有点啰嗦呵呵，有一个要注意的是，如果是奇数行的话，right和left操作会执行两次，这里我WA了3词还一直以为是格式错误，汗，所以在判断到已经到中间行的时候break就okay了，代码如下：

#include <stdio.h>
#include <stdlib.h>
#include<memory.h>

int isfull(char **array,int M,int N){
    for(int i=0;i<M;i++)
        for(int j=0;j<N;j++)
            if(array[i][j] == 'a')
                return 0;
    return 1;
}
int main()
{
    int M,N,left = 0,right = 0,up = 0,down = 0,line = 0,colum = 0,begin = 0;
    char ch = 'A';

    scanf("%d %d",&M,&N);

    char **array = (char **)malloc(sizeof(char *)*M);
    for(int i=0;i<M;i++)
        array[i] = (char *)malloc(sizeof(char)*N);

    for(int i=0;i<M;i++)
        for(int j=0;j<N;j++)
            array[i][j] = 'a';

    left = 0;
    right = N-1;
    up = 1;
    down = M-1;
    while(!isfull(array,M,N)){
        for(int i=begin;i<=right;i++){
            array[line][i] = ch;
            if(ch == 'Z') ch = 'A';
            else ch++;
        }
        begin = line + 1;
        for(int i=begin;i<=down;i++){
            array[i][right] = ch;
            if(ch == 'Z') ch = 'A';
            else ch++;
        }
        begin = right-1;
        for(int i=begin;i>=left;i--){
            if(line == M-1-line)break;
            array[M-1-line][i] = ch;
            if(ch == 'Z') ch = 'A';
            else ch++;
        }
        begin = M-line-2;
        for(int i=begin;i>=up;i--){
            array[i][colum] = ch;
            if(ch == 'Z') ch = 'A';
            else ch++;
        }

        line++;colum++;
        left++;right--;up++;down--;
        begin = colum;
    }
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++)
            printf(" %c",array[i][j]);
        printf("\n");
    }

    return 0;
}