Алгарытм Луна

З пляцоўкі Вікіпедыя
Перайсці да: рух, знайсці

Алгарытм Лу́на (англ.: Luhn algorithm) — алгарытм вылічэння кантрольнага ліку нумара пластыкавых картак у адпаведнасці са стандартам ISO/IEC 7812. Не з'яўляецца крыптаграфічным сродкам, прызначэнне алгарытму ў першую чаргу - выяўленне памылак, выкліканых ненаўмысным скажэннем даных (напрыклад, пры ручным уводзе нумара карткі, пры прыёме даных аб нумары сацыяльнага страхавання праз тэлефон). Дазваляе толькі з некаторай ступенню пэўнасці судзіць аб адсутнасці памылак у блоку лікаў, але не дае магчымасці лакалізацыі і карэкцыі выяўленай недакладнасці.

Алгарытм распрацаваны супрацоўнікам фірмы IBM Гансам Пітэрам Лунам(руск.) бел., апісаны ў ЗША ў 1954 годзе, патэнт атрыманы ў 1960 годзе.

Найбольш распаўсюджаныя ўжыванні для падліку кантрольнга ліку:

  • Нумары ўсіх банкаўскіх картак
  • Нумары некаторых дысконтных картак
  • Коды сацыяльнага страхавання
  • IMEI - коды.
  • Разлік кантрольнага знака адзінага 8-значнага нумара чыгуначнага вагона на Расійскай чыгунцы.

У цяперашні час змест алгарытму з'яўляецца грамадскім здабыткам.

Перавагі і недахопы[правіць | правіць зыходнік]

У сілу прастаты рэалізацыі, алгарытм спажывае мінімум вылічальных магутнасцяў; у шэрагу выпадкаў пры наяўнасці навыка разлік можа быць выкананы ў уме. У той жа час, алгарытм Луна дазваляе толькі выявіць памылкі ў блоках даных, і нават не ўсе. Скажэнне адной лічбы выяўляецца. ВЫяўляюцца амаль усе парныя перастаноўкі лічбаў, якія ідуць запар (за выключэннем 09 ↔ 90). Не могуць быць выяўлены некаторыя скажэнні двух літар запар, а дакладна 22 ↔ 55, 33 ↔ 66 и 44 ↔ 77. Алгарытм не дае инфармацыі аб месцы і характары ўзніклай памылкі.

Алгарытм можа ўжывацца для паслядоўнасцяў лічбаў любой даўжыні, аднак пры гэтым варта мець на ўвазе, што на досыць доўгіх паслядоўнасцях лікаў магчыма з'яўленне адначасова некалькіх скажэнняў даных; некаторыя з такіх памылак могуць прывесці да памылковай высновы, што кантрольны лік, вылічаны алгарытмам Луна, пацвярджае нязменнаць даных.

Алгарытм праверки кантрольнай лічбы[правіць | правіць зыходнік]

Спрошчаны алгарытм[правіць | правіць зыходнік]

1. Пачынаючы з першай лічбы злева праз 1 (то бок 1, 3, 5, 7, 9, …) у выпадку, калі колькасць лічбаў у радку цотная (як у гэтым прыкладзе, дзе яна роўная 16), калі ж колькасць лічбаў няцотная, тады, пачынаючы з другой лічбы праз 1 (то бок 2, 4, 6, 8, ...), робицца праверка: кали 2·x > 9, то з множання аднімаецца 9, інакш множанне 2·x пакідаем без зменаў.

напрыклад:

4  5  6  1     2  6  1  2     1  2  3  4     5  4  6  4
8     12       4     2        2     6        10    12
8     3        4     2        2     6        1     3

2. Потым усе лікі складваюцца.

8+5+3+1 + 4+6+2+2 + 2+2+6+4 + 1+4+3+4 = 57

3. атрыманая сумма павінна быйь кратнай 10 (40, 50, 60, 70, …)

У прыкладзе: апошні лік — гэта кантрольная лічба. Для таго, каб радок быў правільны ў адпаведнасці с алгарытмам Луна, кантрольная лічба павінна быць роўнай 7.

4  5  6  1     2  6  1  2     1  2  3  4     5  4  6  7
8     12       4     2        2     6        10    12
8     3        4     2        2     6        1     3
8+5+3+1 + 4+6+2+2 + 2+2+6+4 + 1+4+3+7 = 60

Арыгінальн алгарытм, апісаны распрацоўшчыкам[правіць | правіць зыходнік]

1. Лічбы патрэбнай паслядоўнасці нумаруюцца спарава налева.

2. Лічбы, якія апынуліся на няцотных месцах, застаюцца без зменаў.

3. Лічбы, якія знаходзяцца на цотных месцах, памнажаюцца на 2.

4. Калі ў выніку такога множання атрымліваецца лік больш за 9, яно замяняецца сумай лічбаў атрыманага множання — адной личбай.

5. Усе атрыманыя ў выніку пераўтварэння лічбы складваюцца. Калі сума кратная 10, то зыходны радок правільны.

Алгарытм вылічэння кантрольнай лічбы[правіць | правіць зыходнік]

Num[1..N] — нумар картки, Num[N] — кантрольная личба

 sum = 0
 for i = 1 to N-1 do
   p = Num[N-i]    
   if (i mod 2 <> 0) then
     p = 2*p
     if (p > 9) then 
       p = p - 9
     end if
   end if
   sum = sum + p
 next i
 //даданне да да 10 
 sum = 10 - (sum mod 10)
 if (sum == 10) then 
   sum = 0
 end if
 Num[N] = sum

pascal Num[1..N] — нумар карткі, Num[N] — кантрольная лічба

function Luhn(Num: array of Integer; var sum: Integer): Boolean;
var
  i, p: integer;
begin    
  sum := 0;
  for i := High(Num) downto Low(Num) do
  begin
    p := Num[i];
    if i mod 2 = 0 then
      p := 2 * p;
    if p > 9 then
      p := p - 9;
    sum := sum + p;
  end;
  Result := sum mod 10 = 0;
  sum := 10 - (sum mod 10);
  if sum = 10 then
    sum := 0;
end;

Ruby

Выраз вяртае true калі лік (num) адпавядае алгарытму Луна і false у адваротным выпадку.

num.to_s.reverse.split(//).each_slice(2).flat_map{|a,b| [a.to_i,2*b.to_i]}.join.split(//).map(&:to_i).reduce(:+)%10==0

Аналагі[правіць | правіць зыходнік]

Алгарытм Верхуффа

Літаратура[правіць | правіць зыходнік]

Спасылкі[правіць | правіць зыходнік]

Wiki letter w.svg На гэты артыкул не спасылаюцца іншыя артыкулы Вікіпедыі,
калі ласка, карыстайцеся падказкай і пастаўце спасылкі ў адпаведнасці з прынятымі рэкамендацыямі.