Programowanie

Algorytm Luhna

Algorytm Luhna

Algorytm Luhna – jeden z najczęściej wykorzystywanych algorytmów służących do sprawdzania poprawności wpisania danej liczby. Jest on używany m.in. do walidacji numerów kart kredytowych, ciągów liczbowych itd.. Nazwa algorytmu pochodzi od nazwiska niemieckiego naukowca Hansa Petera Luhna (1896-1964).

Na końcu liczby doklejana jest cyfra kontrolna określająca, czy poprzedzający ją ciąg cyfr jest wpisany poprawnie.

Spis treści

[edytuj] Dane podstawowe

Algorytm ten wygląda następująco:

  1. Dla każdej pozycji cyfry określone zostają wagi (mnożniki). Najczęściej jest to 2 dla pozycji nieparzystych, 1 dla parzystych.
  2. Każdą cyfrę liczby mnożymy przez odpowiadającą jej wagę.
  3. Jeśli w wyniku mnożenia otrzymamy liczbę dwucyfrową, dodajemy cyfry do siebie otrzymując liczbę jednocyfrową.
  4. Dodajemy wszystkie otrzymane liczby do siebie.
  5. Wykonujemy operację mod 10 na otrzymanej sumie (pozostawiamy jedynie cyfrę jedności).
  6. Następnie, jeśli otrzymana cyfra nie równa się 0, odejmujemy ją od 10. Otrzymujemy cyfrę kontrolną, która jest "doklejana" do liczby.

[edytuj] Przykład

[edytuj] Implementacja

Następująca funkcja C# przedstawia algorytm opisany wyżej, zwracając true jeśli dana tablica cyfr jest prawidłową cyfrą Luhna, a false jeśli nie.

bool CheckNumber(int[] digits)
{
int sum = 0;
bool alt = false;
for(int i = digits.Length - 1; i >= 0; i--)
{
if(alt)
{
digits[i] *= 2;
if(digits[i] > 9)
{
digits[i] -= 9; // equivalent to adding the value of digits
}
}
sum += digits[i];
alt = !alt;
}
return sum % 10 == 0;
}

Następnie widzimy program (w C#), który generuje liczbę zdająca egzamin algorytmu Luhna. Wypełnia tablicę liczbami losowymi, oblicza sumę tych liczb i wpisuje różnicę 10-sum (modulo 10) w ostatnim elemencie tablicy.

int[] CreateNumber(int length)
{
Random random = new Random();
int[] digits = new int[length];
// For loop keeps default value of zero for last slot in array
for(int i = 0; i < length - 1; i++)
{
digits[i] = random.Next(10);
}
int sum = 0;
bool alt = true;
for(int i = length - 2; i >= 0; i--)
{
if(alt)
{
int temp = digits[i];
temp *= 2;
if(temp > 9)
{
temp -= 9;
}
sum += temp;
}
else
{
sum += digits[i];
}
alt = !alt;
}
int modulo = sum % 10;
if(modulo > 0)
{
digits[length-1] = 10 - modulo;
}
// No else req'd - keep default value of zero for digits[length-1]
return digits;
}

[edytuj] Linki zewnętrzne