Реализация алгоритма Луна

Ответ 1

массив [0,1,2,3,4,-4,-3,-2,-1,0] используется в качестве поискового массива для нахождения разницы между числом в 0-9 и суммой цифр в 2 раза больше его значения. Например, для числа 8 разность между 8 и (2 * 8) = 16 → 1 + 6 = 7 равна 7-8 = -1.

Вот графическое представление, где {n} обозначает сумму цифры n

[{0*2}-0, {1*2}-1, {2*2}-2, {3*2}-3, {4*2}-4, {5*2}-5, {6*2}-6, {7*2}-7....]
   |       |        |         |        |        |       |         |  
[  0  ,    1    ,   2    ,    3  ,     4   ,   -4  ,   -3   ,    -2  ....] 

Алгоритм, который вы указали, просто суммируется по всей цифре и для каждой четной четной цифры, просматривает разницу с помощью массива и применяет ее к общей сумме.

Ответ 2

К сожалению, ни один из приведенных выше кодов не работал у меня. Но я нашел на GibHub рабочее решение

// takes the form field value and returns true on valid number
function valid_credit_card(value) {
// accept only digits, dashes or spaces
    if (/[^0-9-\s]+/.test(value)) return false;

// The Luhn Algorithm. It so pretty.
    var nCheck = 0, nDigit = 0, bEven = false;
    value = value.replace(/\D/g, "");

    for (var n = value.length - 1; n >= 0; n--) {
        var cDigit = value.charAt(n),
            nDigit = parseInt(cDigit, 10);

        if (bEven) {
            if ((nDigit *= 2) > 9) nDigit -= 9;
        }

        nCheck += nDigit;
        bEven = !bEven;
    }

    return (nCheck % 10) == 0;
}

Ответ 3

Компактный валидатор Luhn:

var luhn_validate = function(imei){
    return !/^\d+$/.test(imei) || (imei.split('').reduce(function(sum, d, n){ 
            return n===(imei.length-1)
                   ? 0 
                   : sum + parseInt((n%2)? d: [0,2,4,6,8,1,3,5,7,9][d]);
        }, 0)) % 10 == 0;
};

Прекрасно работает для номеров CC и IMEI. Fiddle: http://jsfiddle.net/8VqpN/

Ответ 4

Таблицы поиска или массивы могут упростить реализацию алгоритмов - сэкономить много строк кода - и при этом повысить производительность... если вычисление индекса поиска прост - или проще - и объем памяти массива является доступным.

С другой стороны, понимание того, каким образом может возникнуть конкретный массив поиска или структура данных, может быть довольно сложным, потому что реализация соответствующего алгоритма может выглядеть - на первый взгляд - совершенно отличной от спецификации или описания оригинального алгоритма.

Указание на использование таблиц поиска - это числовые алгоритмы с простой арифметикой, простые сравнения и одинаково структурированные шаблоны повторения - и, конечно же, - вполне конечных наборов значений.

Многие ответы в этом потоке идут для разных таблиц поиска и с тем, что для разных алгоритмов реализует тот же алгоритм Луна. В большинстве реализаций используется массив поиска, чтобы избежать громоздкого вычисления из значения для удвоенных цифр:

var   luhnArr   =   [0,   2,   4,   6,   8,   1,   3,   5,   7,   9];
//
//                   ^    ^    ^    ^    ^    ^    ^    ^    ^    ^
//                   |    |    |    |    |    |    |    |    |    |
//
// - d-igit=index:   0    1    2    3    4    5    6    7    8    9
// - 1st 
//    calculation: 2*0  2*2  2*2  2*3  2*4  2*5  2*6  2*7  2*8  2*9 
// - intermeduate
//          value: = 0  = 2  = 4  = 6  = 8  =10  =12  =14  =16  =18
// - 2nd
//    calculation:                          1+0  1+2  1+4  1+6  1+8
//
// - final value:    0    2    4    6    8   =1   =3   =5   =7   =9
//       
var luhnFinalValue = luhnArray[d]; // d is numeric value of digit to double

Аналогичная реализация для получения luhnFinalValue выглядит следующим образом:

var luhnIntermediateValue = d * 2; // d is numeric value of digit to double
var luhnFinalValue = (luhnIntermediateValue < 10)
        ? luhnIntermediateValue           // (d    ) * 2;
        : luhnIntermediateValue - 10 + 1; // (d - 5) * 2 + 1;

Который - с комментариями в приведенных выше истинных и ложных терминах - конечно упрощается:

var luhnFinalValue = (d < 5) ? d : (d - 5) * 2 + 1;

Теперь я не уверен, что я вообще "сохранил" что-либо...;-) особенно благодаря построенной или короткой форме if-then-else. Без него код может выглядеть так: с "упорядоченными" блоками и встроен в следующий более высокий уровень контекста алгоритма, и поэтому luhnValue:

var luhnValue; // card number is valid when luhn values for each digit modulo 10 is 0

if (even) { // even as n-th digit from the the end of the string of digits
    luhnValue = d;
} else { // doubled digits
    if (d < 5) {
        luhnValue = d * 2;
    } else {
        lunnValue = (d - 5) * 2 + 1;
    }
}

Или:

var luhnValue = (even) ? d : (d < 5) ? d * 2 : (d - 5) * 2 + 1;

Btw, с современными, оптимизирующими интерпретаторами и (как раз вовремя) компиляторами, разница только в исходном коде и имеет значение только для читаемости.

Придя за этим объяснением - и "оправданием" - использованием таблиц поиска и сравнением с прямым кодированием, таблица поиска теперь немного перегрузила меня. Алгоритм без теперь довольно легко закончить - и он выглядит довольно компактным:

function luhnValid(cardNo) { // cardNo as a string w/ digits only
    var sum = 0, even = false;
    cardNo.split("").reverse().forEach(function(dstr){ d = parseInt(dstr);
        sum += ((even = !even) ? d : (d < 5) ? d * 2 : (d - 5) * 2 + 1);
      });
    return (sum % 10 == 0);
  }

Что мне кажется после того, как я объяснил это упражнение, заключается в том, что изначально самая заманчивая реализация, использующая метод reduce() из @kalypto, просто потеряла полностью свой блеск для меня... не только потому, что она ошибочна на нескольких уровнях, но тем более, что это показывает, что колокола и свистки не всегда могут "звонить в колокол победы". Но спасибо, @kalypto, это заставило меня фактически использовать - и понять - уменьшить():

function luhnValid2(cardNo) { // cardNo as a string w/ digits only
    var d = 0, e = false; // e = even = n-th digit counted from the end
    return ( cardNo.split("").reverse().reduce(
                 function(s,dstr){ d = parseInt(dstr); // reduce arg-0 - callback fnc
                     return (s + ((e = !e) ? d : [0,2,4,6,8,1,3,5,7,9][d]));
                   } // /end of callback fnc
                ,0 // reduce arg-1 - prev value for first iteration (sum)
                ) % 10 == 0
           );
  }

Чтобы быть правдой в этом потоке, нужно указать несколько дополнительных параметров таблицы поиска:

• как просто настроить параметры для удвоенных цифр - как опубликовано @yngum
• как только все с таблицами поиска - как опубликовано @Simon_Weaver - где также значения для удвоенных цифр берутся из таблицы поиска.
• как только все с помощью только одной таблицы поиска - как вдохновлено использованием смещения, как это сделано в широко обсуждаемой функции luhnValid().

Код для последнего - с использованием сокращения - может выглядеть так:

function luhnValid3(cardNo) { // cardNo as a string w/ digits only
    var d = 0, e = false; // e = even = n-th digit counted from the end
    return ( cardNo.split("").reverse().reduce(
          function(s,dstr){ d = parseInt(dstr);
              return (s + [0,1,2,3,4,5,6,7,8,9,0,2,4,6,8,1,3,5,7,9][d+((e=!e)?0:10)]);
            }
         ,0
         ) % 10 == 0
      );
  }

И для закрытия lunValid4() - очень компактный - и используя только "старомодный" (совместимый) JavaScript - с одной единственной таблицей поиска:

function luhnValid4(cardNo) { // cardNo as a string w/ digits only
  var s = 0, e = false, p = cardNo.length; while (p > 0) { p--;
    s += "01234567890246813579".charAt(cardNo.charAt(p)*1 + ((e=!e)?0:10)) * 1; }
  return (s % 10 == 0);
 }

Corollar: строки можно рассматривать как таблицы поиска символов...; -)

Прекрасным примером приложения с красивым поисковым столом является подсчет установленных битов в битовых списках - биты, установленные в длинной 8-разрядной байтовой строке aa (очень) длиной в (интерпретированном) языке высокого уровня (где любые битовые операции довольно дорого). Таблица поиска содержит 256 записей. Каждая запись содержит количество бит, установленное в 8-битном целое без знака, равное индексу записи. Итерируя по строке и принимая значение unsigned 8-bit byte равное значение для доступа к количеству бит для этого байта из таблицы поиска. Даже для низкоуровневого языка, такого как ассемблер/машинный код, поисковая таблица - это способ... особенно в среде, где микрокод (инструкция) может обрабатывать несколько байтов до 256 или более в одном (один CISC).

Некоторые примечания:

• numberString * 1 и parseInt (numberStr) делают примерно то же самое.
• есть некоторые лишние углубления, скобки и т.д.... поддержка моего мозга в получении семантики быстрее... но некоторые, которые я хотел бы оставить, на самом деле необходимы... когда это относится к арифметическим операциям с выражениями short-form, value-if-then-else в качестве терминов.
• какое-то форматирование может показаться вам новым; например, я использую запятую продолжения с продолжение в той же строке, что и продолжение, и я "закрываю" вещи - наполовину вкладку - отступом до элемента "открытия".
• Все форматирование сделано для человека, а не для компьютера... "это все равно.

algorithm datastructure luhn lookuptable creditcard validation bitlist

Ответ 5

Очень быстрая и элегантная реализация алгоритма Луна:

const isLuhnValid = function luhn(array) {
      return function (number) {
        let len = number ? number.length : 0,
          bit = 1,
          sum = 0;

        while (len--) {
          sum += !(bit ^= 1) ? parseInt(number[len], 10) : array[number[len]];
        }

        return sum % 10 === 0 && sum > 0;
      };
    }([0, 2, 4, 6, 8, 1, 3, 5, 7, 9]);

console.log(isLuhnValid("4112344112344113".split(""))); // true
console.log(isLuhnValid("4112344112344114".split(""))); // false

Ответ 6

Если вы хотите рассчитать контрольную сумму, этот код с этой страницы является очень кратким и в моем случайном тесты, похоже, работают.

ПРИМЕЧАНИЕ: алгоритмы проверки на этой странице НЕ все работают.

// Javascript
String.prototype.luhnGet = function()
{
    var luhnArr = [[0,1,2,3,4,5,6,7,8,9],[0,2,4,6,8,1,3,5,7,9]], sum = 0;
    this.replace(/\D+/g,"").replace(/[\d]/g, function(c, p, o){
        sum += luhnArr[ (o.length-p)&1 ][ parseInt(c,10) ]
    });
    return this + ((10 - sum%10)%10);
};

alert("54511187504546384725".luhnGet());​

Здесь мои выводы для С#

Ответ 7

Код выглядит следующим образом:

var LuhnCheck = (function()
{
    var luhnArr = [0, 2, 4, 6, 8, 1, 3, 5, 7, 9];
    return function(str)
    {
        var counter = 0;
        var incNum;
        var odd = false;
        var temp = String(str).replace(/[^\d]/g, "");
        if ( temp.length == 0)
            return false;
        for (var i = temp.length-1; i >= 0; --i)
        {
            incNum = parseInt(temp.charAt(i), 10);
            counter += (odd = !odd)? incNum : luhnArr[incNum];
        }
        return (counter%10 == 0);
    }
})();

Переменная counter представляет собой сумму всей цифры в нечетных положениях, плюс двойную цифру в четных положениях, когда double превышает 10, мы добавляем два числа, которые делают это (например: 6 * 2 → 12 → 1 + 2 = 3)

Массив, о котором вы спрашиваете, является результатом всех возможных удвоений

var luhnArr = [0, 2, 4, 6, 8, 1, 3, 5, 7, 9];

• 0 * 2 = 0 → 0
• 1 * 2 = 2 → 2
• 2 * 2 = 4 → 4
• 3 * 2 = 6 → 6
• 4 * 2 = 8 → 8
• 5 * 2 = 10 → 1 + 0 → 1
• 6 * 2 = 12 → 1 + 2 → 3
• 7 * 2 = 14 → 1 + 4 → 5
• 8 * 2 = 16 → 1 + 6 → 7
• 9 * 2 = 18 → 1 + 8 → 9

Итак, например

luhnArr[3] --> 6 (6 is in 3rd position of the array, and also 3 * 2 = 6)
luhnArr[7] --> 5 (5 is in 7th position of the array, and also 7 * 2 = 14 -> 5 )

Ответ 8

function luhnCheck(value) {
  return 0 === (value.replace(/\D/g, '').split('').reverse().map(function(d, i) {
    return +['0123456789','0246813579'][i % 2][+d];
  }).reduce(function(p, n) {
    return p + n;
  }) % 10);
}

Ответ 9

Другая альтернатива:

function luhn(digits) {
    return /^\d+$/.test(digits) && !(digits.split("").reverse().map(function(checkDigit, i) { 
        checkDigit = parseInt(checkDigit, 10);
        return i % 2 == 0
            ? checkDigit
            : (checkDigit *= 2) > 9 ? checkDigit - 9 : checkDigit;
    }).reduce(function(previousValue, currentValue) {
        return previousValue + currentValue;
    }) % 10);
}

Ответ 10

Альтернатива;) Простой и лучший

  <script>
      // takes the form field value and returns true on valid number
    function valid_credit_card(value) {
      // accept only digits, dashes or spaces
        if (/[^0-9-\s]+/.test(value)) return false;

        // The Luhn Algorithm. It so pretty.
        var nCheck = 0, nDigit = 0, bEven = false;
        value = value.replace(/\D/g, "");

        for (var n = value.length - 1; n >= 0; n--) {
            var cDigit = value.charAt(n),
                  nDigit = parseInt(cDigit, 10);

            if (bEven) {
                if ((nDigit *= 2) > 9) nDigit -= 9;
            }

            nCheck += nDigit;
            bEven = !bEven;
        }

        return (nCheck % 10) == 0;
    }

    console.log(valid_credit_card("5610591081018250"),"valid_credit_card Validation");
  </script>

Лучшее решение здесь

• http://plnkr.co/edit/34aR8NUpaKRCYpgnfUbK?p=preview

со всеми тестовыми примерами, переданными в соответствии с

• http://www.paypalobjects.com/en_US/vhelp/paypalmanager_help/credit_card_numbers.htm

и кредит идет на

• https://gist.github.com/DiegoSalazar/4075533

Ответ 11

const LuhnCheckCard = (number) => {
  if (/[^0-9-\s]+/.test(number) || number.length === 0)
    return false;

  return ((number.split("").map(Number).reduce((prev, digit, i) => {
    (!(( i & 1 ) ^ number.length)) && (digit *= 2);    
    (digit > 9) && (digit -= 9);    
    return prev + digit;
  }, 0) % 10) === 0);
}

console.log(LuhnCheckCard("4532015112830366")); // true
console.log(LuhnCheckCard("gdsgdsgdsg")); // false

Ответ 12

Я разработал следующее решение после того, как отправил на тест гораздо худшее.

function valid(number){
    var splitNumber = number.toString().split("");
    var totalEvenValue = 0;
    var totalOddValue = 0;
    for(var i = 0; i < splitNumber.length; i++){
        if(i % 2 === 0){
            if(splitNumber[i] * 2 >= 10){
                totalEvenValue += splitNumber[i] * 2 - 9;
            } else {
                totalEvenValue += splitNumber[i] * 2;
            }
        }else {
            totalOddValue += parseInt(splitNumber[i]);
        }
    }
    return ((totalEvenValue + totalOddValue) %10 === 0)
}
console.log(valid(41111111111111111));