algorytm.org

Algorytm Luhn'a (mod 10)

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Luhn'a (mod 10)
Ocena użytkowników:***** / 14
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 03 kwietnia 2007 00:13

Algorytm Luhn'a zwany inaczej algorytmem mod 10 jest przykładem prostej sumy kontrolnej używanej powszechnie w różnych numerach identyfikacyjnych takich jak na przykład numery kart kredytowych, numer IMEI. Metodę tą stworzył naukowiec IBM Hans Peter Luhn w celu wykrywania przypadkowych błędów w zabezpieczonych numerach. Numery takie mają następującą strukturę XXXXXXXC, gdzie XXXXXXX to numer identyfikacyjny (o dowolnej liczbie cyfr), a C to cyfra kontrolna. Algorytm sprawdzania poprawności liczby zabezpieczonej tą metodą przebiega następująco:
  • zaczynając od cyfry z prawej strony (czyli cyfry kontrolnej) poruszając się w lewą stronę podwajamy co drugą cyfrę (czyli drugą od prawej, czwartą od prawej, itd..). Jeżeli podwojona cyfra jest większa lub równa 10, wówczas dodajemy do siebie jej cyfry. Czyli jeżeli na parzystej pozycji od strony prawej stoi 1 to zamieniamy ją na 2, jeżeli stoi 6 to zamieniamy ją na 3, bo 6*2=12 i teraz dodajemy cyfry 1+2=3. W praktyce poprostu korzystamy z gotowej tablicy:
    CyfraCyfra podwojonaSuma cyfr liczby podwojonej
    000+0=0
    120+2=2
    240+4=4
    360+6=6
    480+8=8
    5101+0=1
    6121+2=3
    7141+4=5
    8161+6=7
    9181+8=9
  • dodajemy do siebie wszystkie cyfry
  • jeżeli wynik jest podzielny przez 10, to numer jest prawidłowy
Algorytm ten wykrywa każdy błąd pojedynczej cyfry, jak również większość zamian - jeżeli ktoś przepisując kod wpisał 12 zamiast 21. Nie wykrywa natomiast błędu zamiany cyfr 09 z 90 (i na odwrót).

Przykład:

Sprawdzimy czy numer IMEI: 353275011731396 jest prawidłowy.
Najpierw użyjemy tabeli powyżej do zamiany cyfr na pozycjach parzystych - licząc od prawej strony.
Czyli otrzymamy: 313471021532396.
Teraz dodajemy do siebie wszystkie cyfry, opórcz cyfry kontorlnej.
3 + 1 + 3 + 4 + 7 + 1 + 0 + 2 + 1 + 5 + 3 + 2 + 3 + 9 + 6 = 50.
Wynik jest podzielny przez 10, zatem podany numer IMEI jest prawidłowy.

Zadaniem cyfry kontrolnej jest dopełnienie tak całej sumy by całość była podzielna przez 10. Jak zatem obliczyć ją dla podanego numeru identyfikacyjnego? Zaczynamy podobnie jak przy sprawdzaniu:
  • zaczynając od cyfry z prawej strony (czyli cyfry kontrolnej) poruszając się w lewą stronę podwajamy co drugą cyfrę (czyli drugą od prawej, czwartą od prawej, itd..). Jeżeli podwojona cyfra jest większa lub równa 10, wówczas dodajemy do siebie jej cyfry. Czyli jeżeli na parzystej pozycji od strony prawej stoi 1 to zamieniamy ją na 2, jeżeli stoi 6 to zamieniamy ją na 3, bo 6*2=12 i teraz dodajemy cyfry 1+2=3. W praktyce poprostu korzystamy z przedstawionej już tablicy.
  • dodajemy do siebie wszystkie cyfry, z wyjątkiem cyfry kontrolnej
  • wynik dzielimy modulo 10 i odejmujemy od 10
  • wynik znów dzielimy modulo 10 (to zabezpieczenie gdyby w poprzednim kroku wyszło nam 10)
  • otrzymany wynik jest równy prawidłowej cyfrze kontrolnej

Przykład:

Obliczymy cyfrę kontrolną dla innego numeru IMEI: 35328501174149c.
Najpierw użyjemy tabeli powyżej do zamiany cyfr na pozycjach parzystych - licząc od prawej strony.
Czyli otrzymamy: 31348102154249c.
Teraz dodajemy do siebie wszystkie cyfry, opórcz cyfry kontorlnej.
3 + 1 + 3 + 4 + 8 + 1 + 0 + 2 + 1 + 5 + 4 + 2 + 4 + 9 = 47.
Wynik dzielimy modulo 10.
47 mod 10 = 7
Wynik odejmujemy od 10.
10 - 7 = 3
I znów dzielimy modulo 10.
3 mod 10 = 3
Zatem cyfra kontrolna c powinna wynosić 3. Zatem prawidłowy numer IMEI to: 353285011741493.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 3
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 2
Tomasz LubińskiJava
.java
.java
***** / 3
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 15 sierpnia 2012 07:11
Dodaj komentarz