В курсе 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.
Эта задачка может быть довольно сложной для новичков, поэтому если у вас что-то не вышло, дам несколько советов для начала; ну а решения буду опубликованы ниже. Аккуратно, спойлеры 🙂
- во-первых, подумайте, как вы будете сохранять номер кредитки. Он довольно большой. Класть его сразу в массив или строку мы не будем, а положим его в длинную-длинную переменную (спойлер: long long int; чтобы увидеть — выдели).
- далее.. если непонятно с какой стороны подходить к задаче: скопируйте (или распечатайте) пример с карточкой 4003600000000014. Держите его все время перед глазами и просто выполняйте то, что там написано 🙂
- для начала для наглядности начните писать программу с помощью обычных переменных, а уже потом спойлер: переведите все на массивы.
- Взять тестовые номера кредиток для тестирования программы можно у палки.
Решение Игроглаза. Я работаю непосредственно в своей 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");
}
Потом пришлось во всем сознаться и переделывать с нуля. Более подробно об этой ситуации:
Решение Штукенции честное-кошачье:
После предыдущего фейла, взяв себя в руки, удалось решить задачу самостоятельно с использованием модуля.
#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");
}
}
}
