24h購物| | PChome| 登入
2011-08-17 09:20:08| 人氣329| 回應0 | 上一篇 | 下一篇

c102. Software CRC

推薦 0 收藏 0 轉貼0 訂閱站台

c102. Software CRC

內容 :

你在一家有很多個人電腦的公司上班。你的老闆,連一分都省博士,想要把這些個人電腦連線,但是他又不想要花錢買網路卡。由於你不小心告訴老闆每台電 腦出廠時就有一個非同步串列埠在上面,老闆當然把腦筋動到這不用花錢的解決方案上。於是可憐的你被指派來完成這工作軟體的需求,以使這些電腦之間可以連 線。

你已經讀了許多關於通訊的書並且知道在傳送及接收訊息時,確保訊息的正確性是一個重點。典型的作法是在訊息的最後加上額外的錯誤檢查碼。這個資訊允 許接收程式檢查出傳送的資訊是否有錯誤(在大多數的例子)。於是,你跑到圖書館借回了一本關於通訊厚厚的書,利用週末(當然沒有加班費)研究錯誤檢查的部 分。

最後,你決定CRC(cyclic redundancy check)是最適合的錯誤檢查方式。以下描述這個機制:

CRC Generation

待傳遞的訊息被視為一列長長二元數。訊息的第一個位元組(byte)被當作這二元數最重要的位元組,第二個位元組被當作第二重要的位元組,依此類推。這個二元數被稱為"m"。當傳送時會在"m"之後加上2個位元組的CRC檢查碼,然後整個二元數稱為"m2"。

這個CRC的檢查碼被產生使得"m2"可以整除某個16位元的值 "g"。所以當接收端收到一訊息,只要把他除以 "g",如果餘數為0即代表此訊息正確。

你也注意到,大部分建議採用的g值都是奇數,所以你決定用 34943 當作 g 的值。現在你迫切的任務就是對待傳送的訊息,寫一個程式算出這個CRC的值。

例如:若要傳送的訊息為:AB(二進位的表示式為:01000001 01000010),你必須算出的CRC值應為60 1B(01100000 00011011的十六進位表示式),使得 01000001 01000010 01100000 00011011可以整除34943(10進位)。

輸入說明 :

每組測試資料一列,含有一個待傳送的訊息(不會超過1024個ASCII字元的長度),列結束字元(End of line)不被視為待傳送訊息的一部份。若遇到只含 # 的一列,代表輸入結束(此列無須輸出)。請參考Sample Input。

輸出說明 :

對每組測試資料輸出一列,CRC的值(以十六進位表示)。請注意:CRC的值一定介於0到34942(十進位)之間。輸出格式請參考Sample Output。

範例輸入 :

this is a testAABNothing gonna change my love for you.#

範例輸出 :

77 FD00 000C 8660 1B57 98

提示 :

* Luck 貓翻譯

出處 :

ACM 128



作法 : 大數mod小數
256 進制數 去 mod 34943,

#include<stdio.h>
main() {
    char s[1030], *A;
    while(gets(s)) {
        if(s[0] == '#')    break;
        int CRC = 0;
        for(A = s; *A; A++)
            CRC = ((CRC*256)+(*A))%34943;
        CRC = ((34943 - ((CRC*256)%34943*256))%34943 + 34943)%34943;
        printf("%02X %02X\n", CRC/256, CRC%256);
    }
    return 0;
}

台長: Morris
人氣(329) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:d750. 11321 - Sort! Sort!! and Sort!!!
此分類上一篇:c110. Packets

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文