Язык Си: проверка номера кредитной карты по алгоритму Луна

Опубликовано 27 марта, 2022 автором

В курсе cs50 (Гарвард) есть задача по программированию на Си по выявлению правильности номера кредитной карты через алгоритм Луна (credit.c). Разберем эту задачку и покажем два варианта еще решения.

Итак. На любой кредитке напечатан номер, который также хранится в базе данных банка, выдавшего карту. Номера кредиток генерируются таким образом, что у них есть некоторая «контрольная сумма» — математическое соотношение между по крайней мере одним числом и другими. Эта контрольная сумма позволяет быстро провести первоначальную проверку и обнаружить опечатки на стороне клиента без необходимости делать запрос к серверу.

Тут-то нам и помогает Алгоритм Луна (создан Гансом Питером Луном из IBM), который позволяет проверить валидность карты таким образом:

  • Начиная с конца (с предпоследней цифры), умножьте каждую вторую цифру на 2, а затем сложите цифры этих частей вместе;
  • Прибавьте сумму к сумме цифр, которые не умножались на 2;
  • Если последняя цифра суммы равна 0 (т.е. сумма по модулю 10 равна 0) — карта валидна.

Возьмем номер карты VISA и выделим каждую вторую цифру, начиная с  предпоследней цифры:
4003600000000014

Мы получим цифры:
4 0 6 0 0 0 0 1

Напишем эти цифры наоборот, для удобства:
1 0 0 0 0 6 0 4

Умножим каждую из этих цифр на 2:
1*2 + 0*2 + 0*2 + 0*2 + 0*2 + 6*2 + 0*2 + 4*2

Получаем:
2 + 0 + 0 + 0 + 0 + 12 + 0 + 8

Сложим цифры этих частей (т. е. не сами части) вместе:
2 + 0 + 0 + 0 + 0 + 1 + 2 + 0 + 8 = 13

Теперь добавим эту сумму (13) к сумме цифр, которые не умножались на 2 (начиная с конца):
13 + 4 + 0 + 0 + 0 + 0 + 0 + 3 + 0 = 20

Ура! Последняя цифра полученного числа равна 0 — карта валидна. Теперь давайте напишем программу, которая дает возможность пользователю ввести номер карточки и узнать — валидна ли она; а также к какому типу карт она принадлежит.

Чтобы понять тип карты: American Express использует 15-значные номера, MasterCard использует 16-значные номера, а Visa использует 13- и 16-значные номера. Все номера American Express начинаются с 34 или 37; большинство номеров MasterCard начинаются с 51, 52, 53, 54 или 55 (у них также есть некоторые другие потенциальные начальные номера); все номера Visa начинаются с 4.

Эта задачка может быть довольно сложной для новичков, поэтому если у вас что-то не вышло, дам несколько советов для начала; ну а решения буду опубликованы ниже. Аккуратно, спойлеры 🙂

  1. во-первых, подумайте, как вы будете сохранять номер кредитки. Он довольно большой. Класть его сразу в массив или строку мы не будем, а положим его в длинную-длинную переменную (спойлер: long long int; чтобы увидеть — выдели).
  2. далее.. если непонятно с какой стороны подходить к задаче: скопируйте (или распечатайте) пример с карточкой 4003600000000014. Держите его все время перед глазами и просто выполняйте то, что там написано 🙂
  3. для начала для наглядности начните писать программу с помощью обычных переменных, а уже потом спойлер: переведите все на массивы.
  4. Взять тестовые номера кредиток для тестирования программы можно у палки.

Решение Игроглаза. Я работаю непосредственно в своей IDE, поэтому не использую неродную библиотеку cs50. Это сказывается на том, что ввод приходится фильтровать ручками. У Штукенции в решении эта библиотека используется. Для начала мое первое решение, которое прошло у меня все тесты, но было забраковано тестировщиком cs50:

#include <stdio.h>
#include <limits.h>

/*
4003600000000014         x16
. . . . . . . .
 400360000000001         x15
  . . . . . . .
   4003600000000         x13
    . . . . . .
*/

int main(void)
{
    long long int cc = 0; // cc number; could be 13, 15, 16 numbers
    int first_multiply = 0;
    int second_summ = 0;
    int final_summ = 0;

    printf("Enter your CC number:\n");

    do
    {
        if (!scanf("%lld", &cc) ||   // scanf returns 1 if valid
           (cc < (long long)100000000000 && !(cc > LLONG_MAX))) // min/max CC number
            printf("INVALID\n");
        while (getchar() != '\n') ; // clear buffer
    }
    while (cc < (long long)100000000000 && !(cc > LLONG_MAX));  // min/max CC number

    // now get separate numbers (2nd starting from end)
    // make array which contain 9 elements (we will use only 8)
    int n[9]; for (int i = 0; i < 10; i++) n[i] = 0; // fill array with 0;

    n[1] = (cc % 100)               / 10;
    n[2] = (cc % 10000)             / 1000;
    n[3] = (cc % 1000000)           / 100000;
    n[4] = (cc % 100000000)         / 10000000;
    n[5] = (cc % 10000000000)       / 1000000000;
    n[6] = (cc % 1000000000000)     / 100000000000;
    n[7] = (cc % 100000000000000)   / 10000000000000;
    n[8] = (cc % 10000000000000000) / 1000000000000000;

    // multiplied x2 (`d` - doubled)
    int d[9]; for (int i = 0; i < 10; i++) d[i] = 0; // fill array with 0;

    d[1] = (n[1]*2);
    d[2] = (n[2]*2);
    d[3] = (n[3]*2);
    d[4] = (n[4]*2);
    d[5] = (n[5]*2);
    d[6] = (n[6]*2);
    d[7] = (n[7]*2);
    d[8] = (n[8]*2);

    // Extract number from 0 to 9 from doubled numbers with module (`m`).
    // Sometimes we will have 1 digit, sometimes 2 (then one will be 1).
    int m[9]; for (int i = 0; i < 10; i++) m[i] = 0; // fill array with 0;

    for (int i = 1; i < 9; i++) // must lurk only at 8 (legit array)
    {
        if (d[i] > 10)
            m[i] = (d[i] % 10) + 1; // as we need summ, we can add 1 right on
        else if (d[i] == 10)
            m[i] = 1;
        else
            m[i] = d[i];
    }

    // first half done:
    first_multiply = m[1]+m[2]+m[3]+m[4]+m[5]+m[6]+m[7]+m[8];

    // now take leftover digits from initial CC number
    int x[9]; for (int i = 0; i < 10; i++) x[i] = 0; // fill array with 0;

    x[1] = (cc % 10);
    x[2] = (cc % 1000)             / 100;
    x[3] = (cc % 100000)           / 10000;
    x[4] = (cc % 10000000)         / 1000000;
    x[5] = (cc % 1000000000)       / 100000000;
    x[6] = (cc % 100000000000)     / 10000000000;
    x[7] = (cc % 10000000000000)   / 1000000000000;
    x[8] = (cc % 1000000000000000) / 100000000000000;

    // done! now calculate:
    second_summ    = x[1]+x[2]+x[3]+x[4]+x[5]+x[6]+x[7]+x[8];
    final_summ     = first_multiply + second_summ;

    if (final_summ % 10 == 0)
    {
        if (cc < (long long)10000000000000)    // 13 digits
        {
            printf("VISA\n");
        }

        else if (cc < (long long)1000000000000000)  // 15 digits
        {
            printf("AMEX\n");
        }

        else if (cc < (long long)10000000000000000) // 16 digits
        {
            if (n[8] == 4) // visa cc always starts with 4
                printf("VISA\n");
            else
                printf("MCARD\n");
        }
    }
    else
        printf("Credit card INVALID\n");

    getchar();
    getchar();

}

А вот мое второе решение, которое все тесты на cs50 прошло успешно:

#include <stdio.h>
#include <limits.h>

/*
4003600000000014         x16
. . . . . . . .
 400360000000001         x15
  . . . . . . .
   4003600000000         x13
    . . . . . .
*/

int main(void)
{
    long long int cc = 0; // cc number; could be 13, 15, 16 numbers
    int first_multiply = 0;
    int second_summ = 0;
    int final_summ = 0;

    printf("Enter your CC number:\n");

    do
    {
        scanf("%lld", &cc);
        while (getchar() != '\n') ; // clear buffer
    }
    while (cc < (long long)100000000);

    if (cc < (long long)1000000000000 || cc >= (long long)10000000000000000) // min/max CC number: error reporting
    {
        printf("INVALID\n");
        return 0;
    }

    // now get separate numbers (2nd starting from end)
    // make array which contain 9 elements (we will use only 8)
    int n[9];
    for (int i = 0; i < 10; i++)
    {
        n[i] = 0; // fill array with 0;
    }

    n[1] = (cc % 100)               / 10;
    n[2] = (cc % 10000)             / 1000;
    n[3] = (cc % 1000000)           / 100000;
    n[4] = (cc % 100000000)         / 10000000;
    n[5] = (cc % 10000000000)       / 1000000000;
    n[6] = (cc % 1000000000000)     / 100000000000;
    n[7] = (cc % 100000000000000)   / 10000000000000;
    n[8] = (cc % 10000000000000000) / 1000000000000000;

    // multiplied x2 (`d` - doubled)
    int d[9];
    for (int i = 0; i < 10; i++)
    {
        d[i] = 0; // fill array with 0;
    }

    d[1] = (n[1] * 2);
    d[2] = (n[2] * 2);
    d[3] = (n[3] * 2);
    d[4] = (n[4] * 2);
    d[5] = (n[5] * 2);
    d[6] = (n[6] * 2);
    d[7] = (n[7] * 2);
    d[8] = (n[8] * 2);

    // Extract number from 0 to 9 from doubled numbers with module (`m`).
    // Sometimes we will have 1 digit, sometimes 2 (then one will be 1).
    int m[9];
    for (int i = 0; i < 10; i++)
    {
        m[i] = 0; // fill array with 0;
    }

    for (int i = 1; i < 9; i++) // must lurk only at 8 (legit array)
    {
        if (d[i] > 10)
        {
            m[i] = (d[i] % 10) + 1; // as we need summ, we can add 1 right on
        }
        else if (d[i] == 10)
        {
            m[i] = 1;
        }
        else
        {
            m[i] = d[i];
        }
    }

    // first half done:
    first_multiply = m[1] + m[2] + m[3] + m[4] + m[5] + m[6] + m[7] + m[8];

    // now take leftover digits from initial CC number
    int x[9];
    for (int i = 0; i < 10; i++)
    {
        x[i] = 0; // fill array with 0;
    }

    x[1] = (cc % 10);
    x[2] = (cc % 1000)             / 100;
    x[3] = (cc % 100000)           / 10000;
    x[4] = (cc % 10000000)         / 1000000;
    x[5] = (cc % 1000000000)       / 100000000;
    x[6] = (cc % 100000000000)     / 10000000000;
    x[7] = (cc % 10000000000000)   / 1000000000000;
    x[8] = (cc % 1000000000000000) / 100000000000000;

    // done! now calculate:
    second_summ    = x[1] + x[2] + x[3] + x[4] + x[5] + x[6] + x[7] + x[8];
    final_summ     = first_multiply + second_summ;

    if (final_summ % 10 == 0)
    {
        if (cc < (long long)10000000000000)    // 13 digits
        {
            printf("VISA\n");
        }

        else if (cc < (long long)1000000000000000 && // 15 digits
                 ((cc >= (long long)340000000000000 && cc < (long long)350000000000000) || // starts with 34
                  (cc >= (long long)370000000000000 && cc < (long long)380000000000000)))  // starts with 37
        {
            printf("AMEX\n");
        }

        else if (cc < (long long)10000000000000000) // 16 digits
        {
            if (n[8] == 4) // visa cc always starts with 4
            {
                printf("VISA\n");
            }
            else if (cc >= (long long)5100000000000000 && cc < (long long)5600000000000000) // MCARD starts with 51,52,53,54,55
            {
                printf("MASTERCARD\n");
            }
            else
            {
                printf("INVALID\n");
            }
        }
        else
        {
            printf("INVALID\n");
        }
    }
    else
    {
        printf("INVALID\n");
    }

    return 0;
}

 

Решение №3 (читерское от Штукенции). 

Привет, это Штукенция. Поняв, что задача сложная, я полностью потеряла веру в себя и прибегла к подсказкам из интернета. Но Игроглазу сказала, что все решение сделала сама, так как мы сами проходим курс без подсказок. 

Получилось вот что:

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    string cardtype="";
    long long int cardnum = get_long("Card number:");
    int i=0;
    long long int lenth = cardnum;
    long long int lenthcardname = cardnum;
    long long int lenthcardcheck = cardnum;

// Check lenth of input cardnumber (VALID or NOT):

    for (i=0; lenth>0; i++)
    {
        lenth=lenth/10;
    }
    printf("Lenth:%i\n",i);
    if (i<13 || i>16)
    {
        cardtype="INVALID\n";
    }
    else
    {
        cardtype="OK, LENTH\n";
    }
    printf("Lenth check:%s\n",cardtype);

// Check card type (AMEX, VISA, MASTERCARD):

    long long int firstnumcheck=lenthcardcheck;
    if (i==15)
    {
        printf("AMEX\n");
    }
    else if (i==13)
    {
        printf("VISA\n");
    }
    else if (i==16)
    {
        firstnumcheck=firstnumcheck/1000000000000000;
        if (firstnumcheck==4)
            printf("VISA\n");
        else
            printf("MASTERCARD\n");
    }

    printf("%lld\n",firstnumcheck);

// Check Luhn algoruthm (VALID or NOT):

    int numbers1;
    int numbers2;
    int firstdig;
    int seconddig;
    int sumnum1=0;
    int sumnum2=0;
    do
    {
        numbers1=cardnum%10;
        cardnum=cardnum/10;
        sumnum1+=numbers1;

        numbers2=cardnum%10;
        cardnum=cardnum/10;

        numbers2=numbers2*2;
        firstdig=numbers2/10;
        seconddig=numbers2%10;
        sumnum2+=firstdig+seconddig;
    }
    while(cardnum>0);

    int sumnum;
    sumnum=sumnum1+sumnum2;

    if (sumnum%10==0)
    {
        printf("GOOD! VALID CARD\n");
    }
    else
        printf("INVALID\n");
}

Потом пришлось во всем сознаться и переделывать с нуля. Более подробно об этой ситуации:

https://youtu.be/fM9Bnow_nTA

Решение Штукенции честное-кошачье:

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

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    string cardtype="";
    long long int cardnum = get_long("Card number:");
    int i=0;
    long long int lenth = cardnum;
    long long int lenthcardname = cardnum;
    long long int lenthcardcheck = cardnum;



// Check the Luhn Algorithm

    int num1 = cardnum%10;
    int num2 = ((cardnum%100)/10)*2;
    int num3 = (cardnum%1000)/100;
    int num4 = ((cardnum%10000)/1000)*2;
    int num5 = (cardnum%100000)/10000;
    int num6 = ((cardnum%1000000)/100000)*2;
    int num7 = (cardnum%10000000)/1000000;
    int num8 = ((cardnum%100000000)/10000000)*2;
    int num9 = (cardnum%1000000000)/100000000;
    int num10 = ((cardnum%10000000000)/1000000000)*2;
    int num11 = (cardnum%100000000000)/10000000000;
    int num12 = ((cardnum%1000000000000)/100000000000)*2;
    int num13 = (cardnum%10000000000000)/1000000000000;
    int num14 = ((cardnum%100000000000000)/10000000000000)*2;
    int num15 = (cardnum%1000000000000000)/100000000000000;
    int num16 = ((cardnum%10000000000000000)/1000000000000000)*2;

    int num2dig1 = num2%10;
    int num4dig1 = num4%10;
    int num6dig1 = num6%10;
    int num8dig1 = num8%10;
    int num10dig1 = num10%10;
    int num12dig1 = num12%10;
    int num14dig1 = num14%10;
    int num16dig1 = num16%10;

    int sumnumdig1 = num2dig1+num4dig1+num6dig1+num8dig1+num10dig1+num12dig1+num14dig1+num16dig1;

    int num2dig2 = (num2-num2dig1)/10;
    int num4dig2 = (num4-num4dig1)/10;
    int num6dig2 = (num6-num6dig1)/10;
    int num8dig2 = (num8-num8dig1)/10;
    int num10dig2 = (num10-num10dig1)/10;
    int num12dig2 = (num12-num12dig1)/10;
    int num14dig2 = (num14-num14dig1)/10;
    int num16dig2 = (num16-num16dig1)/10;

    int sumnumdig2 = num2dig2+num4dig2+num6dig2+num8dig2+num10dig2+num12dig2+num14dig2+num16dig2;

    int sumnum1=sumnumdig1+sumnumdig2;

    int sumnum2=num1+num3+num5+num7+num9+num11+num13+num15;

    int sumnum=sumnum1+sumnum2;

    printf("Sumnum= %d\n",sumnum);
    
// Check if card valid: lenth of cardnumber & AMEX, VISA, MASTERCARD:

    long long int firstnumcheck=lenthcardcheck;

    for (i=0; lenth>0; i++)
    {
        lenth=lenth/10;
    }
    printf("Lenth:%i\n",i);


    if (i<13 || i>16)
    {
        cardtype="INVALID\n";
    }
    else
    {
        cardtype="OK, LENTH\n";

        if (sumnum%10==0)
            {
                if (i==15)
                {
                    printf("AMEX\n");
                }
                else if (i==13)
                {
                printf("VISA\n");
                }
                else if (i==16)
                {
                firstnumcheck=firstnumcheck/1000000000000000;
                    if (firstnumcheck==4)
                        printf("VISA\n");
                    else
                        printf("MASTERCARD\n");
                }

                printf("%lld\n",firstnumcheck);

                printf("GOOD! VALID CARD\n");
            }
        else
            printf("INVALID\n");

    }
    printf("Lenth check:%s\n",cardtype);
}

И код этой программы после тестирования багов выглядит так:

#include <cs50.h>
#include <stdio.h>
#include <string.h>

//Check typy of creditcard and if it's even valid
int main(void)
{
    string cardtype = "INVALID\n";
    long long int cardnum = get_long("Card number:");
    int i = 0;
    long long int lenth = cardnum;
    long long int lenthcardname = cardnum;
    long long int lenthcardcheck = cardnum;

// Check the Luhn Algorithm

// First use module to identify each number of card
    int num1 = cardnum % 10;
    int num2 = ((cardnum % 100) / 10) * 2;
    int num3 = (cardnum % 1000) / 100;
    int num4 = ((cardnum % 10000) / 1000) * 2;
    int num5 = (cardnum % 100000) / 10000;
    int num6 = ((cardnum % 1000000) / 100000) * 2;
    int num7 = (cardnum % 10000000) / 1000000;
    int num8 = ((cardnum % 100000000) / 10000000) * 2;
    int num9 = (cardnum % 1000000000) / 100000000;
    int num10 = ((cardnum % 10000000000) / 1000000000) * 2;
    int num11 = (cardnum % 100000000000) / 10000000000;
    int num12 = ((cardnum % 1000000000000) / 100000000000) * 2;
    int num13 = (cardnum % 10000000000000) / 1000000000000;
    int num14 = ((cardnum % 100000000000000) / 10000000000000) * 2;
    int num15 = (cardnum % 1000000000000000) / 100000000000000;
    int num16 = ((cardnum % 10000000000000000) / 1000000000000000) * 2;
    int num2dig1 = num2 % 10;
    int num4dig1 = num4 % 10;
    int num6dig1 = num6 % 10;
    int num8dig1 = num8 % 10;
    int num10dig1 = num10 % 10;
    int num12dig1 = num12 % 10;
    int num14dig1 = num14 % 10;
    int num16dig1 = num16 % 10;

// Find first sum of digits
    int sumnumdig1 = num2dig1 + num4dig1 + num6dig1 + num8dig1 + num10dig1 + num12dig1 + num14dig1 + num16dig1;

// Find second sum of digits
    int num2dig2 = (num2 - num2dig1) / 10;
    int num4dig2 = (num4 - num4dig1) / 10;
    int num6dig2 = (num6 - num6dig1) / 10;
    int num8dig2 = (num8 - num8dig1) / 10;
    int num10dig2 = (num10 - num10dig1) / 10;
    int num12dig2 = (num12 - num12dig1) / 10;
    int num14dig2 = (num14 - num14dig1) / 10;
    int num16dig2 = (num16 - num16dig1) / 10;

    int sumnumdig2 = num2dig2 + num4dig2 + num6dig2 + num8dig2 + num10dig2 + num12dig2 + num14dig2 + num16dig2;

    int sumnum1 = sumnumdig1 + sumnumdig2;

    int sumnum2 = num1 + num3 + num5 + num7 + num9 + num11 + num13 + num15;

    int sumnum = sumnum1 + sumnum2; // Final sum of digits

// Check if card valid: lenth of cardnumber & AMEX, VISA, MASTERCARD:

    long long int firstnumcheck = lenthcardcheck;

    for (i = 0; lenth > 0; i++)
    {
        lenth = lenth / 10;
    }

    if (i < 13 || i > 16) // If cardlenth invalid
    {
        printf("INVALID\n");
    }
    else
    {
        cardtype = "OK, LENTH\n";

        if (sumnum % 10 == 0) // Check if the last digit of final sum = 0
        {
            int amex_check = firstnumcheck / 10000000000000;

            if (i == 15 && (amex_check == 34 || amex_check == 37)) // Check if it's AmericanExpress
            {
                printf("AMEX\n");
            }

            else if (i == 13) // Check if it's VISA by lenth
            {
                printf("VISA\n");
            }

            else if (i == 16) // Check if it's VISA or Mastercard by first numbers
            {
                int firstnumcheck_16 = firstnumcheck / 1000000000000000;
                int secondnumcheck = firstnumcheck / 100000000000000;

                if (firstnumcheck_16 == 4)
                {
                    printf("VISA\n");
                }

                else if (secondnumcheck == 51 || secondnumcheck == 52 || secondnumcheck == 53 || secondnumcheck == 54 || secondnumcheck == 55)
                {
                    printf("MASTERCARD\n");
                }

                else
                {
                    printf("INVALID\n");
                }

            }

            else
            {
                printf("INVALID\n");
            }

        }

        else
        {
            printf("INVALID\n");
        }

    }
}

 


Запись опубликована в рубрике С (Си). Добавьте в закладки постоянную ссылку.

Добавить комментарий

🇬🇧 Attention! Comments with URLs/email are not allowed.
🇷🇺 Комментарии со ссылками/email удаляются автоматически.