2014
01-22

# UVa-128-Software CRC(软件CRC)

Time limit: 3.000 seconds

## Problem问题

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 GenerationCRC的生成

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).

this is a test

A
#

77 FD
00 00
0C 86

## Analysis分析

p = a0n0 + a1n1 + … + aknk

rk = aknk mod q
rk-1 = (rkn + ak-1nk-1) mod q

r0 = (r1n + a0n0) mod q

(a0n0 + a1n1 + … + aknk + c) mod q = 0

(a0n0 + a1n1 + … + aknk) mod q = r

c = q – (nr mod q)

5B 04 AF 00

## Solution解答

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <string>
using namespace std;
int main(void) {
typedef unsigned short word;
char Bits[1032]; //存储输入的字符串
cin.sync_with_stdio(false); //输入的数据量很大，关闭同步以加速
cout << setbase(16) << setiosflags(ios::uppercase) << setfill('0');
//循环处理输入的每一行字符串
for (string Line; getline(cin, Line) && Line[0] != '#'; cout << endl) {
word nGen = 34943, nLen = Line.length(), *pBit = (word*)Bits;
//将字符串转存到静态数组中。x86的CPU字节序为little-endian，
reverse_copy(Line.begin(), Line.end(), Bits); //反转为正字节序
*(word*)(&Bits[nLen]) = 0; //将结尾后面的一些位都清零
nLen = nLen / 2 + (nLen % 2 != 0); //计算作为int数组的长度
long nRem = 0;//nRem表示余数
//循环除所有的位，累加进位的余数，生成CRC码
for (int i = nLen - 1; i >= 0; --i) {
nRem = ((nRem << 16) + pBit[i]) % nGen;
}
if (nRem != 0) { //如果余数不为0，则需构造CRC码，算法见文档
nRem = nGen - (nRem << 16) % nGen;
} //下面按要求的格式输出CRC码
unsigned char* pByte = (unsigned char*)&nRem;
cout << setw(2) << (int)pByte[1] << ' ' << setw(2) << (int)pByte[0];
}
return 0;
}

1. 给你一组数据吧：29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。

2. 您没有考虑 树的根节点是负数的情况， 若树的根节点是个很大的负数，那么就要考虑过不过另外一边子树了

3. 这道题目的核心一句话是：取还是不取。
如果当前取，则index+1作为参数。如果当前不取，则任用index作为参数。

4. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}