卢恩算法逻辑

Question

我目前正在学习 Codecademy 的 Full Stack Engineer 课程，直到现在我都非常适应它，发现新事物，自己解决问题，但这是我进步的一个严重障碍，因为我只是似乎无法确定此逻辑的问题。我并不是要质疑 Luhn 的算法，但说真的，我需要对此进行一些澄清...

所以我的问题是，算法返回我的所有数组都是有效的，我的代码如下（codecademy 提供的数组）：

// All valid credit card numbers
const valid1 = [4, 5, 3, 9, 6, 7, 7, 9, 0, 8, 0, 1, 6, 8, 0, 8];
const valid2 = [5, 5, 3, 5, 7, 6, 6, 7, 6, 8, 7, 5, 1, 4, 3, 9];
const valid3 = [3, 7, 1, 6, 1, 2, 0, 1, 9, 9, 8, 5, 2, 3, 6];
const valid4 = [6, 0, 1, 1, 1, 4, 4, 3, 4, 0, 6, 8, 2, 9, 0, 5];
const valid5 = [4, 5, 3, 9, 4, 0, 4, 9, 6, 7, 8, 6, 9, 6, 6, 6];

// All invalid credit card numbers
const invalid1 = [4, 5, 3, 2, 7, 7, 8, 7, 7, 1, 0, 9, 1, 7, 9, 5];
const invalid2 = [5, 7, 9, 5, 5, 9, 3, 3, 9, 2, 1, 3, 4, 6, 4, 3];
const invalid3 = [3, 7, 5, 7, 9, 6, 0, 8, 4, 4, 5, 9, 9, 1, 4];
const invalid4 = [6, 0, 1, 1, 1, 2, 7, 9, 6, 1, 7, 7, 7, 9, 3, 5];
const invalid5 = [5, 3, 8, 2, 0, 1, 9, 7, 7, 2, 8, 8, 3, 8, 5, 4];

// Can be either valid or invalid
const mystery1 = [3, 4, 4, 8, 0, 1, 9, 6, 8, 3, 0, 5, 4, 1, 4];
const mystery2 = [5, 4, 6, 6, 1, 0, 0, 8, 6, 1, 6, 2, 0, 2, 3, 9];
const mystery3 = [6, 0, 1, 1, 3, 7, 7, 0, 2, 0, 9, 6, 2, 6, 5, 6, 2, 0, 3];
const mystery4 = [4, 9, 2, 9, 8, 7, 7, 1, 6, 9, 2, 1, 7, 0, 9, 3];
const mystery5 = [4, 9, 1, 3, 5, 4, 0, 4, 6, 3, 0, 7, 2, 5, 2, 3];

// An array of all the arrays above
const batch = [valid1, valid2, valid3, valid4, valid5, invalid1, invalid2, invalid3, invalid4, invalid5, mystery1, mystery2, mystery3, mystery4, mystery5];

我实现算法的函数：

const validateCred = arr => {

    let checkSum = 0;
    let ifEvenDouble = 0;
    arr.push(checkSum);

    //Iterate through array, double what is needed

    for(let i = arr.length - 2; i >= 0; i--){
      console.log(ifEvenDouble);

      //If ifEvenDouble is even, we are at the 'other' cell

        if((ifEvenDouble % 2) === 0){
          let doubled = arr[i] * 2;

          //If doubled digit is greater than 9, store sum of individual digits
          //Convert the doubled number to a string then extract each member and convert back to number for calculation, add to checkSum and skip to next iteration, otherwise, add arr[i]

          let newDigit = 0;
          if(doubled > 9){
            newDigit = Number(doubled.toString()[0]) + Number(doubled.toString()[1]);
            //Add doubled & split digit to total and continue the loop
            checkSum += newDigit;
            ifEvenDouble++;
            continue;
          }
          //Add doubled digit less than 9 to total and continue the loop
          checkSum += doubled;
          ifEvenDouble++;
          continue;
        }

        //Add current array member to total
        checkSum += arr[i];
        ifEvenDouble++;

    }//End for loop

    console.log(checkSum);
    const checkDigit = (checkSum * 9) % 10;
    const totalSum = checkDigit + checkSum;

    if(totalSum % 10 === 0){
      console.log('Valid');
      return true;
    } else {
      console.log('Invalid');
      return false;
    }
};

validateCred(invalid1); // -> Output: Valid

根据我的理解，我的总和是总是将是 10 的倍数，如果我从 10 中减去我的个位数，将它添加到我的校验和是总是会给我 10 的倍数。我错了吗？

编辑：我一直在尝试调试它，但我做的越多，我就越远离核心算法。

Edit(2)：感谢下面的人，我认为我的问题是生成我自己的校验位而不是使用已经提供的校验位？我的困惑是，通过阅读关于此的维基百科页面，它说：

'计算校验位示例：假设一个帐号“7992739871”的示例将添加一个校验位，使其格式为 7992739871x'

然后他们开始用 x 以外的数字进行所有计算，我认为这是现在主要的混淆。

Answer 1

你的算法太复杂了。 Wikipedia描述的很简洁，只需执行3个步骤

From the rightmost digit (excluding the check digit) and moving left, double the value of every second digit. The check digit is neither doubled nor included in this calculation; the first digit doubled is the digit located immediately left of the check digit. If the result of this doubling operation is greater than 9 (e.g., 8 × 2 = 16), then add the digits of the result (e.g., 16: 1 + 6 = 7, 18: 1 + 8 = 9) or, equivalently, subtract 9 from the result (e.g., 16: 16 − 9 = 7, 18: 18 − 9 = 9).

Take the sum of all the digits (including the check digit).

If the total modulo 10 is equal to 0 (if the total ends in zero) then the number is valid according to the Luhn formula; otherwise it is not valid.

我还认为你误解了校验位是什么。您似乎将它作为 0 附加到数组，并试图在最后计算它。它已经存在于号码中 - 这是最后一位。

const validateCred = arr => {

   let doubleIt = true;
   let sum = 0;
   // From the rightmost digit excluding check digit...
   for(let i = arr.length - 2; i >= 0; i--){
        
        if(doubleIt){
          let doubled = arr[i] * 2;
         
          if(doubled > 9){
            doubled -= 9
          }
          sum += doubled
        }
        else {
          sum += arr[i]
        }
        doubleIt = !doubleIt;

    }

    // Add the check digit to the sum
    sum += arr[arr.length-1];

    // If sum is divisible by 10 it is valid
    if(sum % 10 === 0){
      console.log('Valid');
      return true;
    } else {
      console.log('Invalid');
      return false;
    }
};

const invalid1 = [4, 5, 3, 2, 7, 7, 8, 7, 7, 1, 0, 9, 1, 7, 9, 5];
const valid1 = [4, 5, 3, 9, 6, 7, 7, 9, 0, 8, 0, 1, 6, 8, 0, 8];
validateCred(invalid1);
validateCred(valid1);

你出错的地方主要是在校验位的使用上。您似乎正在计算它，而它已经存在，只是数组中的最后一个元素。下面的片段更接近您的原始片段，只是没有计算校验位。

const validateCred = arr => {

    let ifEvenDouble = 0;
   let checkSum=0
    //Iterate through array, double what is needed

    for(let i = arr.length - 2; i >= 0; i--){

      //If ifEvenDouble is even, we are at the 'other' cell

        if((ifEvenDouble % 2) === 0){
          let doubled = arr[i] * 2;

          //If doubled digit is greater than 9, store sum of individual digits
          //Convert the doubled number to a string then extract each member and convert back to number for calculation, add to checkSum and skip to next iteration, otherwise, add arr[i]

          let newDigit = 0;
          if(doubled > 9){
            newDigit = Number(doubled.toString()[0]) + Number(doubled.toString()[1]);
            //Add doubled & split digit to total and continue the loop
            checkSum += newDigit;
            ifEvenDouble++;
            continue;
          }
          //Add doubled digit less than 9 to total and continue the loop
          checkSum += doubled;
          ifEvenDouble++;
          continue;
        }

        //Add current array member to total
        checkSum += arr[i];
        ifEvenDouble++;

    }//End for loop

    const checkDigit = arr[arr.length-1]
    const totalSum = checkDigit + checkSum;

    if(totalSum % 10 === 0){
      console.log('Valid');
      return true;
    } else {
      console.log('Invalid');
      return false;
    }
};


const invalid1 = [4, 5, 3, 2, 7, 7, 8, 7, 7, 1, 0, 9, 1, 7, 9, 5];
const valid1 = [4, 5, 3, 9, 6, 7, 7, 9, 0, 8, 0, 1, 6, 8, 0, 8];
validateCred(invalid1);
validateCred(valid1);

Answer 2

我知道问题更多的是关于哪里出了问题，而不是关于更好的解决方案； Jamiec 的回答已经很好地涵盖了这一点。

然而，有了一堆数组方法，我们应该能够写出一个更简单的答案。

// utility functions
const sum = (ns) => ns .reduce ((a, b) => a + b, 0)
const last = (xs) => xs [xs .length - 1]

// helper function
const doubleDig = (d) => 2 * d > 9 ? 2 * d - 9 : 2 * d

// main function
const luhn = (ds) =>
  (sum ([... ds] .map (Number) .reverse () .slice(1) .map (
    (d, i) => i % 2 == 0 ? doubleDig (d) : d
  )) + Number (last (ds)))  % 10 == 0

// sample data
const batch = [
  /* Valid   */ [4, 5, 3, 9, 6, 7, 7, 9, 0, 8, 0, 1, 6, 8, 0, 8], [5, 5, 3, 5, 7, 6, 6, 7, 6, 8, 7, 5, 1, 4, 3, 9], [3, 7, 1, 6, 1, 2, 0, 1, 9, 9, 8, 5, 2, 3, 6], [6, 0, 1, 1, 1, 4, 4, 3, 4, 0, 6, 8, 2, 9, 0, 5], [4, 5, 3, 9, 4, 0, 4, 9, 6, 7, 8, 6, 9, 6, 6, 6],
  /* Invalid */ [4, 5, 3, 2, 7, 7, 8, 7, 7, 1, 0, 9, 1, 7, 9, 5], [5, 7, 9, 5, 5, 9, 3, 3, 9, 2, 1, 3, 4, 6, 4, 3], [3, 7, 5, 7, 9, 6, 0, 8, 4, 4, 5, 9, 9, 1, 4], [6, 0, 1, 1, 1, 2, 7, 9, 6, 1, 7, 7, 7, 9, 3, 5], [5, 3, 8, 2, 0, 1, 9, 7, 7, 2, 8, 8, 3, 8, 5, 4],
  /* Mystery */ [3, 4, 4, 8, 0, 1, 9, 6, 8, 3, 0, 5, 4, 1, 4], [5, 4, 6, 6, 1, 0, 0, 8, 6, 1, 6, 2, 0, 2, 3, 9], [6, 0, 1, 1, 3, 7, 7, 0, 2, 0, 9, 6, 2, 6, 5, 6, 2, 0, 3], [4, 9, 2, 9, 8, 7, 7, 1, 6, 9, 2, 1, 7, 0, 9, 3], [4, 9, 1, 3, 5, 4, 0, 4, 6, 3, 0, 7, 2, 5, 2, 3],
]

// demo
console.log (batch .map (luhn))

console .log (
  luhn ('4539677908016808'),
  luhn ('4532778771091795')
)

.as-console-wrapper {max-height: 100% !important; top: 0}

此函数适用于提供的单位数字数组，但也适用于数字字符串，因此 luhn ('4539677908016808') 等同于 luhn ([4, 5, 3, 9, 6, 7, 7, 9, 0, 8, 0, 1, 6, 8, 0, 8]).

首先，我们确保我们正在处理一个数字数组，[... ds] .map (Number)。然后我们 .reverse 数组，以便更容易跟踪偶数和奇数位置，而无需摆弄数组长度。我们 .slice 关闭现在第一个元素，我们稍后只需要它作为校验位。现在我们映射结果，将偶数位加倍并根据需要舍弃 9（使用辅助函数 doubleDig），但保持奇数位不变。我们使用助手 sum 对结果求和，并使用助手 last 找到最后一位数字，将其转换为数字并将其添加到总数中。我们以 10 为底的模数结束，并报告该值是否为 0。

那些辅助函数很有用，我几乎总是喜欢使用它们，但每个函数只在我们的主函数中的一个地方被调用，这使得我们可以很容易地内联它们，如果我们想的话，我们可以写这样做的独立版本：

const luhn = (ds) =>
  ([...ds] .map (Number) .reverse () .slice(1) .map (
    (d, i) => i % 2 == 0 ? (2 * d > 9 ? 2 * d - 9 : 2 * d) : d
  ) .reduce ((a, b) => a + b, 0) + Number (ds [ds .length - 1])) % 10 == 0

我不认为这是一个改进。虽然原始版本很密集，但也不难理解。这个，尤其是我们将 doubleDig 的条件表达式（三元）内联到另一个三元中的地方，看起来非常难看。也许更宽敞的布局会有所帮助。¹ 但是 sum (...) 绝对比 (...) .reduce ((a , b) => a + b, 0) 更干净，而 last 比它的替代方案更干净。总的来说，这是没有吸引力的。但最好将其视为上述辅助函数分解的替代方法。

¹ 是的，更宽敞的布局改善了这一点很多!

const luhn = (ds) =>
  ([...ds]
    .slice (0, -1)
    .reverse () 
    .map (Number) 
    .map ((d, i) => i % 2 == 0 ? (2 * d > 9 ? 2 * d - 9 : 2 * d) : d) 
    .reduce ((a, b) => a + b, 0) 
    + Number (ds [ds .length - 1])) 
    % 10 
    == 0

但更妙的是，如果我们更改执行数字加倍例程的奇偶校验位，则不必单独处理校验位。这让我们变得更好

const luhn = ([...ds]) => (ds
  .reverse () 
  .map (Number) 
  .map ((d, i) => i % 2 == 1 ? (2 * d > 9 ? 2 * d - 9 : 2 * d) : d) 
  .reduce ((a, b) => a + b, 0) 
) % 10 == 0

... 在这一点上，辅助函数最多是很好的。这看起来不错。

卢恩算法逻辑

Luhn Algorithm Logic

javascript

arrays

algorithm

credit-card

luhn