UVa 128 Software CRC:模计算及CRC循环冗余校验码

128 - Software CRCTime limit: 3.000 seconds

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=64

You work for a company which uses lots of personal computers. Your boss, Dr Penny Pincher, has wanted to link the computers together for some time but has been unwilling to spend any money on the Ethernet boards you have recommended. You, unwittingly, have pointed out that each of the PCs has come from the vendor with an asynchronous serial port at no extra cost. Dr Pincher, of course, recognizes her opportunity and assigns you the task of writing the software necessary to allow communication between PCs.

You've read a bit about communications and know that every transmission is subject to error and that the typical solution to this problem is to append some error checking information to the end of each message. This information allows the receiving program to detect when a transmission error has occurred (in most cases). So, off you go to the library, borrow the biggest book on communications you can find and spend your weekend (unpaid overtime) reading about error checking.

Finally you decide that CRC (cyclic redundancy check) is the best error checking for your situation and write a note to Dr Pincher detailing the proposed error checking mechanism noted below.

CRC Generation

The message to be transmitted is viewed as a long positive binary number. The first byte of the message is treated as the most significant byte of the binary number. The second byte is the next most significant, etc. This binary number will be called ``m'' (for message). Instead of transmitting ``m'' you will transmit a message, ``m2'', consisting of ``m'' followed by a two-byte CRC value.

The CRC value is chosen so that ``m2'' when divided by a certain 16-bit value ``g'' leaves a remainder of 0. This makes it easy for the receiving program to determine whether the message has been corrupted by transmission errors. It simply divides any message received by ``g''. If the remainder of the division is zero, it is assumed that no error has occurred.

You notice that most of the suggested values of ``g'' in the book are odd, but don't see any other similarities, so you select the value 34943 for ``g'' (the generator value).

Input and Output

You are to devise an algorithm for calculating the CRC value corresponding to any message that might be sent. To test this algorithm you will write a program which reads lines (each line being all characters up to, but not including the end of line character) as input, and for each line calculates the CRC value for the message contained in the line, and writes the numeric value of the CRC bytes (in hexadecimal notation) on an output line. Each input line will contain no more than 1024 ASCII characters. The input is terminated by a line that contains a # in column 1. Note that each CRC printed should be in the range 0 to 34942 (decimal).

Sample Input

this is a test

A
#

Sample Output

77 FD
00 00
0C 86

题目有个关键地方没说清楚,就是把每个字符化为ASCII码,所以m相当于一个有strlen(s)位的256进制数,m2相当于一个有strlen(s)+2位的256进制数,并且m2的十进制表示能被34942整除。

我们就是要求这两个256进制数,中间用空格隔开。

具体过程见代码。

完整代码:

/*0.105s*/

#include<cstdio>
#include<cstring>

int len;
unsigned int ans;
char s[1030], output[4];

int main(void)
{
    while (gets(s), s[0] != '#')
    {
        len = strlen(s);
        ans = 0;
        for (int i = 0; i < len; i++)
            ans = ((ans << 8) + s[i]) % 34943;
        ans = (ans << 16) % 34943;
        ans = (ans ? 34943 - ans : 0);
        sprintf(output, "%04x\n", ans);///16进制,长度不够4就补0 (不写0就补空格)
        for (int i = 0; i < 4; i++)
            if (output[i] >= 'a' && output[i] <= 'z')
                output[i] = output[i] - 'a' + 'A';
        printf("%c%c %c%c\n", output[0], output[1], output[2], output[3]);
    }
    return 0;
}

查看本栏目更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索error
, 16位的crc校验
, message
, value
, to
, 循环冗余校验
, The
that
智能相应hjsoftware、software、移动apphjsoftware、销售行为hjsoftware、crmhjsoftware,以便于您获取更多的相关知识。

时间: 2016-07-11