Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CRC - Oblicz CRC

Kod kontrolny CRC jest ciągiem bitów dodawanym do pliku lub wysyłanej informacji aby umożliwić późniejsze wykrycie przekłamania danych.

Obliczanie CRC opiera się na obliczaniu reszty z dzielenia wielomianu przez wielomian, przy czym współczynniki tych wielomianów są elementami ciała Z2 reszt modulo 2 (czyli 0 i 1, operacje arytmetyczne wykonywane modulo 2, więc np. x+x=(1+1)x=0x=0). Wielomiany takie możemy reprezentować jako ciągi binarne, w ten sposób, że wielomian w(x) stopnia k reprezentujemy za pomocą ciągu (k+1)-bitowego, w którym kolejne pozycje odpowiadają kolejnym współczynnikom wielomianu, przy czym pierwszy z lewej bit odpowiada współczynnikowi przy xk. W ten sposób możemy wzajemnie jednoznacznie wyznaczyć na podstawie wielomianu liczbę binarną,np.

x7+x5 +x1+1 <=> 101000112 <=> 16310

W najprostszej wersji obliczanie CRC wygląda następująco:

  1. Mamy ustalony z góry wielomian p(x) stopnia k.
  2. Wpierw na podstawie danych, dla których ma być obliczone CRC, jest tworzony wielomian w(x) w ten sposób, że dane traktowane są jako długa liczba binarna, do której dopisujemy k zer z prawej i na podstawie tego ciągu wyznaczamy w(x).
  3. Obliczana jest reszta r(x) z dzielenia w(x) przez p(x).
  4. Reszta r(x) jest kodem CRC, kórego reprezentacja binarna jest doklejana do danych.

Wejście

W pierwszym wierszu podana jest liczba testów, każdy kolejny wiersz zawiera jeden test.

Każdy test składa się z liczby zapisanej szesnastkowo (co najwyżej 8 cyfr), reprezentującej wielomian p(x) oraz, po spacji, łańcucha znaków (bez białych znaków, max. 10 000 znaków) dla którego ma być obliczone CRC.

Wyjście

Na wyjściu należy podać kody CRC w postaci liczb zapisanych szesnastkowo, po jednym w każdym wierszu.

Przykład

Wejście:
4
11021 Pan_kotek_byl_chory
12021 i_lezal_w_lozeczku
1BABA i_przyszedl_pan_doktor,
1AAAA "Jak_sie_masz,_Koteczku?"

Wyjście:
E53D
A98D
1E8A
573C

Bibliografia

  1. Kalkulator CRC
  2. Wikipedia

Dodane przez:Adam Nadolski
Data dodania:2007-02-26
Limit czasu wykonania programu:0.200s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ERL GOSU JS-RHINO NODEJS PERL6 VB.NET

ukryj komentarze
2018-06-04 23:05:40 Tomasz Nastula
Czy ma ktoś próbkę dodatkowych testów? Przykładowe i zmyślone działają, ale moje zgłoszenia nadal zwracają błędy.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.