Strona główna » Algorytmy » Artykuły » Algorytm Luhna
 

Algorytm Luhna

https://mattomatti.com/a56

O algorytmie

Algorytm Luhna powstał, aby sprawdzać poprawność podanego numeru identyfikacyjnego np. karty kredytowej czy telefonu komórkowego. W tym celu algorytm wyznacza cyfrę kontrolną, którą dopisuje się na koniec liczby. W ten sposób jeśli źle się wpisze pojedynczą liczbę lub większą zmian istnieje możliwość wykrycia tego. Znane są przypadki kiedy algorytm nie wykrywa zamian.

Zasada działania

Każda cyfra w zależności od pozycji ma określony mnożnik. Przyjmuje się, że liczby na pozycjach parzystych ma wartość 1, a dla nieparzystych 2. W celu wyznaczenia liczby cyfry kontrolnej wyznacza się sumę jej składników tj. każdej cyfry pomnożonej przez swój mnożnik. Należy pamiętać, że taki sumowanie rozpoczynamy od prawej do lewej. Przyjęło się, że pierwsza rozpatrywana liczba (nie kontrolna!) jest zawsze parzysta. Jeśli którykolwiek składnik jest liczbą dwucyfrową to obie cyfry się sumuje. Z otrzymanej liczby pobieramy cyfrę jedności. Jeśli pobrana cyfra jest różna od zera to odejmujemy ją od 10.

Proces sprawdzania podanej liczby polega na obliczeniu sumy, która tym razem powinna wynieść 0. Należy pamiętać, że podczas procesu sprawdzania uwzględnia się cyfrę kontrolną, która podczas rozpatrywania od prawej do lewej będzie pierwsza. Jednak w tym przypadku pierwszą cyfrę przyjmuje się jako nieparzystą.

Przykłady

Wyliczanie cyfry kontrolnej

Przypuśćmy teraz, że pracujemy w korporacji i mamy zadanie przypisać każdemu urządzeniu unikalny kod ID. W tym przypadku będzie się on składał z 8 cyfr: 7 cyfr będzie kolejno oznaczać typ urządzenia (1 cyfra), piętro budynku (1 cyfra), numer pomieszczenia (2 cyfry) jak również unikalny numer w obrębie tego poziomu (3 cyfry). Ostatnia 8 cyfra to będzie cyfra kontrolna wyznaczona zgodnie z algorytmem Luhna. W ten sposób podczas zgłoszenia będziemy w stanie sprawdzić, że został podany prawdziwy numer identyfikacyjny.

Przyjmijmy przykładowo, że mamy numer 1234567*. Naszym zadaniem jest wyznaczenie cyfry kontrolnej zaznaczonej (*).

Należy pamiętać, że cyfry dodajemy od prawej do lewej!

Cyfra1234567*
Mnożnik1212121-
Wartość1438537-

Wartość dla cyfry 6 jest większa od 9, więc jej wartość to 1 + 2 = 3. Następnie należy wyznaczyć sumę składników. W tym przypadku wyniesie ona 31. Pobieramy z niej cyfrę jedności 1. Jest ona różna od 0, więc wykonujemy operację odejmowania 10 - 1 = 9. Wyliczona cyfr kontrolna to 9. Ostatecznie 8 cyfrowy kod identyfikacyjny wygląda następująco: 12345679.

Sprawdzanie kodu

Sprawdźmy teraz czy nie doszło do pomyłki w trakcie obliczeń kodu 12345679.

Cyfra12345679
Mnożnik12121212
Wartość14385379

Suma składników w tym przypadku wynosi 40. Cyfra jedności to 0, więc podany numer identyfikacyjny jest poprawny.

Spróbujmy teraz zmienić pojedynczą cyfrę 12345689:

Cyfra12345689
Mnożnik12121212
Wartość14385389

Suma składników w tym przypadku wynosi 41. Cyfra jedności to 1, więc podany numer identyfikacyjny jest niepoprawny.

Implementacja

Przyjmujemy, że numer będziemy przechowywać jako tablicę znaków. W ten sposób unikniemy problemu z "obcinaniem" początkowych zer liczby.

Wyliczanie cyfry kontrolnej

  1. void setControlNumber(char* data){
  2.   int suma = 0;
  3.   int dl = strlen(data);
  4.   bool nieparz = false;
  5.   for(int i = dl - 1; i >= 0; i--){
  6.     int temp = data[i] - '0';
  7.     if(parz){
  8.       temp *= 2;
  9.       temp = temp / 10 + temp % 10;
  10.     }
  11.     suma += temp;
  12.     parz = !parz;
  13.   }
  14.   data[dl] = (10 - (suma % 10)) % 10 + '0';
  15.   data[dl + 1] = '\0';
  16. }

(1.) Funkcja setControlNumber() przyjmuje tablice znaków data. Bardzo ważne, aby było zarezerwowane jedno dodatkowe miejsce na cyfrę kontrolną. (2.) Ustalamy sumę na 0. (3.) Pobieramy długość liczby. (4.) Ustalamy, że pierwsza liczba jest parzysta. (5.) Następnie dla każdej cyfry w liczbie: (6.) pobieramy jej wartość, (7.) i sprawdzamy czy nie trzeba pomnożyć przez 2. Jeśli tak to (8.) mnożymy razy dwa i (9.) sumujemy obie cyfry. (11.) Dopisujemy wyliczoną wartość składnika do suma i (12.) przemieniamy wartość parzystości. (14.) Zamiast znaku końca danych umieszczamy cyfrę kontrolną i (15.) na koniec umieszczamy znak \0.

Sprawdzanie kodu

  1. bool isValid(char* data){
  2.   int suma = 0;
  3.   bool nieparz = true;
  4.   for(int i = strlen(data) - 1; i >= 0; i--){
  5.     int temp = data[i] - '0';
  6.     if(parz){
  7.       temp *= 2;
  8.       temp = temp / 10 + temp % 10;
  9.     }
  10.     suma += temp;
  11.     parz = !parz;
  12.   }
  13.   return suma % 10 == 0;
  14. }

(2. - 12.) W ten sam sposób wyliczamy sumę składników (włącznie z cyfrą kontrolną). (13.) Jako wynik zwracamy porównanie cyfry jedności do 0.

Testowanie funkcji

Kod można przetestować przy pomocy poniższej funkcji main():

  1. int main () {
  2.   char* data = new char[128];
  3.   cin >> data;
  4.   setControlNumber(data);
  5.   cout << data << endl;
  6.   cout << (isValid(data) ? "TAK" : "NIE") << endl;
  7.   system("pause");
  8.   return 0;
  9. }

Zadania

Zadanie 1

Przypuśćmy, że nie chcemy, aby cyfra kontrolna była na końcu. Teraz będzie zależało to od użytkownika gdzie wstawi gwiazdkę. Zakładamy, że gwiazdka jest wstawiona na pozycji o mnożniku jeden i nie trzeba tego sprawdzać. Ponadto cyfr kontrolna zostaje wciśnięta, dlatego parzystości cyfr są takie jakby cyfra kontrolna była na końcu.

Przykładowo dla podania wartości 1234*567 zostanie wypisane na ekran:

  1. 12349567