Luhn算法检验和验证

一、Luhn公式介绍

Luhn公式是一种广泛使用的系统,用于对标识号进行验证。它根据原始标识号,把每隔一个数字的值扩大一倍。然后把各个单独数字的值加在一起(如果扩大一倍后的值为2个数字,就把这两个数字分别相加)。如果相加之后可以被10整除,那么这个标识号就是合法的。

编写一个程序,接受一个任意长度的标识号,并根据Luhn公式确定这个标识号是否合法。这个程序在读取下一个字符之前必须处理之前所读取的那个字符。

过程有些复杂,在此上传一张图片以供各位理解:

 记住:最终标识号的检验和应该能够被10整除,或者说应该以0结尾。

二、问题分步求解

  1. 知道哪些数字需要扩大一倍。
  2. 对扩大一倍后大于等于10的数字,根据他们的单独数字进行处理。
  3. 知道已经到达了标识号的尾部。
  4. 分别读取每个数字。

(注:我们不需要按照特定的顺序处理这些问题。)

首先,我们处理扩大一倍后大于或等于10的数:

如果我们从单独的数字0~9开始并把它们扩大一倍,最大值将是18。因此,一共只有两种可能性:如果扩大一倍后的值为单个数字,就不需要再做处理;如果扩大一倍后的值大于或等于10,它的范围肯定在10~18之间,因此第一个数字总是为1.我们通过一个代码来验证一下:

 1     int digit;
 2     printf("Enter a single digit number,0-9:");
 3     scanf("%d",&digit);
 4     int doubledDigit = digit * 2;  //程序读取数字,并把它的值扩大一倍 
 5     int sum;
 6     if(doubledDigit >= 10)
 7         sum = 1 + doubledDigit % 10;  //求和计算 
 8     else
 9         sum = doubledDigit;
10     printf("Sum of digits in doubled number:%d\n",sum);  //输出求和结果 

验证结果如下:

我们可以把这段代码转化为一个短小的函数,这样就可以简化未来的代码了。(是不是很有远见呢?)

 1 int doubleDigitValue(int digit)
 2 {
 3     int doubledDigit = digit * 2;  //程序读取数字,并把它的值扩大一倍 
 4     int sum;
 5     if(doubledDigit >= 10)
 6         sum = 1 + doubledDigit % 10;  //求和计算 
 7     else
 8         sum = doubledDigit;
 9     return sum;
10 }

现在,我们读取标识号的单独数字:

如果我们以数值类型(例如int)的形式读取标识号,将会读取一个长长的数,需要处理很多事情。另外,可以读取的最大整数也是有限制的。但在该问题中,标识号可以是任意长度的。因此,我们必须逐字符读取。这意味着我们要知道怎样读取一个表示数字的字符并把它转换为整数类型,以便对它进行数学运算。来看以下代码:

1     char digit;
2     printf("Enter a one-digit number:");
3     scanf("%c",&digit);
4     int sum = digit;
5     printf("Is the sum of digits:%d?\n",sum); 

运行结果为:

字符7是以字符码值55存储的,因此当我们把这个字符作为整数时,得到的结果就是55.

因此,我们需要一种机制把字符7转换为整数7。

我们可以创建一张表,其中包含原值和目标值,还有两值之间的误差。

字符

字符码

目标整数值

0

48

0

48

1

49

1

48

2

50

2

48

3

51

3

48

4

52

4

48

5

53

5

48

6

54

6

48

7

55

7

48

8

56

8

48

9

57

9

48

字符码和目标整数值之差始终是48,因此我们需要做的就是使字符码减去这个值。而48正好是0的字符码,所以我们可以采用一种更通用、更容易理解的解决方案:就是减去字符0的字符码而不是减去像48这样预先确定的值:

1     char digit;
2     printf("Enter a one-digit number:");
3     scanf("%c",&digit);
4     int sum = digit - '0';
5     printf("Is the sum of digits:%d?\n",sum); 

运行结果为:

现在,我们转到问题的下一部分,判断哪些数字需要扩大一倍:

我们可以先试着把长度限制为6,则我们只需要读取6个数字,对它们进行求和,然后判断它们的和是否被10所整除,代码如下:

 1     char digit;
 2     int checksum = 0;
 3     printf("Enter a six-digit number:");
 4     for(int position = 1;position <= 6;position++){
 5         scanf("%c",&digit);
 6         checksum += digit - '0';
 7     }
 8     printf("Checksum is:%d\n",checksum);
 9     if(checksum%10 == 0)
10         printf("Valid:Checknum is divisible by 10\n"); 
11     else
12         printf("Invalid:Checknum is not divisible by 10\n");

运行结果为:

现在,我们需要为实际的Luhn检验公式增加逻辑,把从左边开始位置为奇数的数字扩大一倍。我们可以使用求摸操作符(%)确定奇数和偶数的位置,因为偶数的定义是它能够被2所整除。因此如果表达式位置%2的结果是1,这个位置就是奇数,应该把它扩大一倍。顺便插一句,在扩大一倍后,如果结果大于或等于10,还需要对这个结果的各个数字进行求和。代码如下(只需把for循环那改一下):

1     for(int position = 1;position <= 6;position++){
2         scanf("%c",&digit);
3         if(position%2 == 0) checksum += digit - '0';
4         else checksum += doubleDigitValue(digit - '0');
5     }

运行结果为:

到目前为止,我们在这个问题上已经取得很大的进展,但还需要完成一些步骤才能为任意长度的标识号编写代码。为了最终解决这个问题,我们需要采用分治法。

先考虑怎样处理长度为任意偶数的标识号。

我们所面临的第一个问题是怎样确定已经到达了标识号的末尾。如果用户输入了一个多位的标识号又按下了Enter键表示结束,并且我们是逐个字符读取输入的,那么在最后一个数字之后所读取的字符是什么呢?我们不妨用代码来试验一下:

1     printf("Enter a number:");
2     char digit;
3     while(1){
4         scanf("%c",&digit);
5         printf("%d\n",int(digit));
6     }

运行结果为:

输入1234,结果是49 50 51 52 10(结果基于ASCII码)。从运行结果中可以看出,10就是我们所寻找的结果,所以我们可以在前面的代码中用一个while循环代替for循环:

 1     //处理任意偶数长度的标识号 
 2     char digit;
 3     int checksum = 0;
 4     int position = 1;
 5     printf("Enter a number with an even number of digits:");
 6     scanf("%c",&digit);  //读取第一个值 
 7     while(digit != 10){  //用来检查字符码的值是否为行末符 
 8         if(position%2 == 0)  //偶数位判断 
 9          checksum += digit - '0';
10         else checksum += 2 * (digit - '0');
11         scanf("%c",&digit);  //读取每个后续的值 
12         position++;
13     }
14     printf("Checksum is:%d\n",checksum);
15     if(checksum%10 == 0)
16         printf("Valid:Checksum is divisible by 10\n");
17     else
18         printf("Invalid:Checksum is not divisible by 10\n");

运行结果为:

现在已经解决了“怎样确定已经到达了标识号的末尾”的问题。

要穷尽每种可能性,标识号的长度必须是奇数或者偶数。如果我们预先知道长度,就可以知道应该把奇数位的数字或者偶数位的数字扩大一倍。但是,在读取完这个标识号之前,我们并不知道这个信息。在思考这个问题前,我们先来类比另外一个问题:

编写一个程序,从用户那里读取10个整数。在输入了所有的整数之后,要求显示这些数中正数或负数的数量。

编写思路:需要一个对正数进行计数的变量,并用另一个变量对负数进行计数。当用户在程序的最后指定了具体的请求时,只需显示适当的变量作为响应即可。代码如下:

 1     int number;
 2     int positiveCount = 0;
 3     int negativeCount = 0;
 4     for(int i = 1;i <= 10;i++){
 5         scanf("%d",&number);
 6         if(number > 0) positiveCount++;  //计数正值 
 7         if(number < 0) negativeCount++;  //计数负值 
 8     } 
 9     char response;  //选择回答 
10     printf("Do you want the (p)ositive or (n)egative count?");
11     getchar(); //吞掉回车 
12     scanf("%c",&response);
13     if(response == 'p')
14      printf("Positive Count is %d\n",positiveCount);
15     if(response == 'n')
16      printf("Negative Count is %d\n",negativeCount);

运行结果为:

这个类比的问题显示了我们在解决Luhn检验和问题时所需要用到的方法:同时以两种方式追踪当前的检验和,分别是在标识符为奇数长度和偶数长度的情况下。当我们读取完这个编号并确定了它的真正长度时,再选择表示正确的检验和的变量。

现在,我们可以把所有的代码都集中在一起,来解决这个问题了。

三、完整代码

 1     char digit;
 2     int oddLengthChecksum = 0;
 3     int evenLengthChecksum = 0;
 4     int position = 1;
 5     printf("Enter a number:");
 6     scanf("%c",&digit);
 7     while(digit != 10){
 8         if(position%2 == 0){
 9             oddLengthChecksum += doubleDigitValue(digit - '0');
10             evenLengthChecksum += digit - '0';
11         }
12         else{
13             oddLengthChecksum += digit - '0';
14             evenLengthChecksum += doubleDigitValue(digit - '0');
15         }
16         scanf("%c",&digit);
17         position++;
18     }
19     int checksum;
20     if((position - 1)%2 == 0) checksum = evenLengthChecksum;
21     else checksum = oddLengthChecksum;
22     printf("Checksum is:%d\n",checksum);
23     if(checksum%10 == 0)
24         printf("Valid:Checknum is divisible by 10\n"); 
25     else
26         printf("Invalid:Checknum is not divisible by 10\n");

运行结果为:

感受

这篇博文写了一晚上,视力开始模糊了,而且还有一些头痛的症状,可能是昨天下午出去玩吹凉风了。不过今天还是很开心的,看着一个完整的算法被我们切成一小块一小块的细致分析和代码检验,沉浸于其中,一点点的接近真相,我感到兴奋和快乐!刚开始我还对函数调用和程序中的回车问题有所疑惑,不过在一位朋友的指点下我还是顺利通过了。最重要的是,我对这个算法也有了更深一步的了解与认识。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏和蔼的张星的图像处理专栏

162. 矩阵归零先找为零的位置,再分别置零

给定一个m×n矩阵,如果一个元素是0,则将其所在行和列全部元素变成0。 需要在原矩阵上完成操作。

1491
来自专栏数据结构与算法

P1044 栈

题目背景 栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。 栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一...

3056
来自专栏QQ音乐技术团队的专栏

Android Native 开发之 NewString 与 NewStringUtf 解析

本文将从一个 Native Crash 分析入手,带大家了解我们平时开发中,那些容易忽略但又很值得学习的底层源码知识。

1.4K9
来自专栏飞雪无情的博客

Go语言性能优化-两数之和算法性能研究

好多人都在刷leetcode,今天我也注册了一个玩玩,发现里面好多都是算法题,好吧,毕业十来年,学的那点可怜的数学知识,全都还给学校了。好了闲话少说,言归正传,...

1933
来自专栏数据结构与算法

2729:Blah数集

2729:Blah数集 查看 提交 统计 提问 总时间限制:3000ms内存限制:65536kB描述大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah,对...

3144
来自专栏用户2442861的专栏

典型的Top K算法_找出一个数组里面前K个最大数...或找出1亿个浮点数中最大的10000个...一个文本文件,找出前10个经常出现的词,但这次文件比较长,说是上亿行或十亿行,总之无法一次读入内存,

http://blog.163.com/xychenbaihu@yeah/blog/static/1322296552012821103039741/

5352
来自专栏LhWorld哥陪你聊算法

【机器学习】--Python机器学习库之Numpy

NumPy(Numerical Python的缩写)是一个开源的Python科学计算库。使用NumPy,就可以很自然地使用数组和矩阵。 NumPy包含很多实用的...

992
来自专栏Web行业观察

0.30000000000000004

0.30000000000000004问题是计算机科学领域的经典BUG, 由比尔盖茨那一代人标准化的浮点数表示法造福了一代人也祸害了一代人, 由...

4303
来自专栏小红豆的数据分析

小蛇学python(16)numpy高阶用法

如果只是从事简单的数据分析,其实numpy的用处并不是很大。简单了解一下numpy,学好pandas已经够用,尤其是对于结构化或表格化数据。但是精通面向数组的编...

1502
来自专栏逆向技术

逆向课程第四讲逆向中的优化方式,除法原理,以及除法优化上

           逆向课程第四讲逆向中的优化方式,除法原理,以及除法优化上 除法原理,涉及到了数学公式,而且在汇编中的体现形式也有10几种 这里首先讲解前4...

2448

扫码关注云+社区

领取腾讯云代金券