Luhn算法学习及其Ruby版实现代码示例

关于LUHN算法
LUHN算法，主要用来计算信用卡等证件号码的合法性。
1、从卡号最后一位数字开始,偶数位乘以2,如果乘以2的结果是两位数，将两个位上数字相加保存。
2、把所有数字相加,得到总和。
3、如果信用卡号码是合法的，总和可以被10整除。
Luhn 算法或是Luhn 公式，也被称作“模10算法”。它是一种简单的校验公式，一般会被用于身份证号码，IMEI号码，美国供应商识别号码，或是加拿大的社会保险号码的验证。该算法是由IBM的科学家Hans Peter Luhn所创造，于1954年1月6日提出该专利的申请，并于1960年8月23日被授予，在美国的专利号为2950048。
该算法一直都被大家所公用，并且时至今日应用也很广泛。它被指定在ISO/IEC7812-1。它的目的不是成为一种加密安全的哈希函数；它的目的是防止意外出现的错误，而不是恶意攻击。很多信用卡和众多的政府身份识别号码都使用该算法从一系列的随机数字中提取有效的数字。

优点和缺点
Luhn 算法会检测到任何单码的错误以及几乎所有的相邻数字换位的错误。但是它不会检测两个数字序列09转90的错误（反之亦然）。它会检测到十分之七的相同双位数错误（不会检测到22和55的互换，33和66的互换，44和77的互换）。其他更复杂的检查数字算法，如费尔赫夫算法，可以检测出更多的转录错误。模N的Luhn算法是Luhn算法的一个扩展，支持非数字字符串。因为该算法采取了从右向左的方式，而且零位会影响计算的结果。只有当零位造成了数位的移动或是用零来填充一串数字的开头时才不会影响计算结果的生成。因此不论在将1234用零填充为0001234之前或是之后，使用Luhn算法得到的结果都是一样的。
该算法在美国专利上是为了给手持或是机械设备计算校验码。所以它必须尽可能的简单。

Ruby版实现
Luhn算法的基本原理非常简单：（eg：49927398716）
第一步：把信用卡号倒序（61789372994）
第二步：取出倒序后的奇数位置上的号码， 相加等到总和s1（s1=6+7+9+7+9+4=42)
第三步：取出倒序后的偶数位置上的号码，每个号码乘以2. (eg:2,16,6,4,18)
第四步：把第三步得到的大于10的号码转化为个位+十位。（eg：2,7,6,4,9)
第五步：把处理好的偶数位号码相加，得到s2(s2=2+7+6+4+9=28)
第六步：判读(s1+s2)%10 == 0则有效，否则无效。（有效）
代码：

module LuhnValidator
 def validate(number)
  s1 = s2 = 0
  number.to_s.reverse.chars.each_slice(2) do |odd, even|
   s1 += odd.to_i 

   double = even.to_i * 2
   double -= 9 if double >= 10
   s2 += double
  end
  (s1 + s2) % 10 == 0 ? 'valid' : 'invalid'
 end
end
赞 (0)

相关推荐

  • Ruby实现的最长公共子序列算法

    最长公共子序列,LCS,动态规划实现. #encoding: utf-8 #author: xu jin, 4100213 #date: Nov 01, 2012 #Longest-Commom-Subsequence #to find a longest commom subsequence of two given character arrays by using LCS algorithm #example output: #The random character arrays are

  • Ruby实现的3种快速排序算法

    刚学Ruby,正巧算法老师鼓励用不熟悉的语言来写算法,我就用Ruby吧~~ 话说Ruby可真是超厉害,好多凭直觉的方法都可以用.....无限膜拜中.... 期间我遇到了invalid multibyte char (US-ASCII)的错误,解决办法是在开头加一个#encoding:utf-8 这个错误在stackoverflow上有人问到过,某人给出的回答是 Write # encoding: utf-8 on top of that file. That changes the defaul

  • Ruby实现的各种排序算法

    时间复杂度:Θ(n^2) Bubble sort 复制代码 代码如下: def bubble_sort(a)    (a.size-2).downto(0) do |i|      (0..i).each do |j|        a[j], a[j+1] = a[j+1], a[j] if a[j] > a[j+1]      end    end    return a  end Selection sort 复制代码 代码如下: def selection_sort(a)    b =

  • Ruby实现的矩阵连乘算法

    动态规划解决矩阵连乘问题,随机产生矩阵序列,输出形如((A1(A2A3))(A4A5))的结果. 代码: #encoding: utf-8 =begin author: xu jin, 4100213 date: Oct 28, 2012 MatrixChain to find an optimum order by using MatrixChain algorithm example output: The given array is:[30, 35, 15, 5, 10, 20, 25]

  • Ruby实现的最优二叉查找树算法

    算法导论上的伪码改写而成,加上导论的课后练习第一题的解的构造函数. 复制代码 代码如下: #encoding: utf-8 =begin author: xu jin date: Nov 11, 2012 Optimal Binary Search Tree to find by using EditDistance algorithm refer to <<introduction to algorithms>> example output: "k2 is the r

  • ruby实现的插入排序和冒泡排序算法

    1.插入排序 复制代码 代码如下: seq = [3,4,9,0,2,5,9,7,1] 1.upto(seq.length-1) do |i|  if seq[i] < seq[i-1]    tmp = seq[i]    j = i-1    while(j>=0 && tmp<seq[j]) do      seq[j+1] = seq[j]      j=j-1    end    seq[j+1]=tmp  endend seq.each {|num| puts

  • Ruby实现的合并排序算法

    算法课的作业,利用分治法,合并排序. #encoding: utf-8 #author: xu jin, 4100213 #date: Oct 27, 2012 #MergeSort #to sort an array by using MergeSort algorithm #example output: #The original array is:[4, 32, 84, 58, 49, 40, 75, 29, 82, 21, 70, 37, 70] #The sorted array i

  • Luhn算法学习及其Ruby版实现代码示例

    关于LUHN算法 LUHN算法,主要用来计算信用卡等证件号码的合法性. 1.从卡号最后一位数字开始,偶数位乘以2,如果乘以2的结果是两位数,将两个位上数字相加保存. 2.把所有数字相加,得到总和. 3.如果信用卡号码是合法的,总和可以被10整除. Luhn 算法或是Luhn 公式,也被称作"模10算法".它是一种简单的校验公式,一般会被用于身份证号码,IMEI号码,美国供应商识别号码,或是加拿大的社会保险号码的验证.该算法是由IBM的科学家Hans Peter Luhn所创造,于195

  • K均值聚类算法的Java版实现代码示例

    1.简介 K均值聚类算法是先随机选取K个对象作为初始的聚类中心.然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心.聚类中心以及分配给它们的对象就代表一个聚类.一旦全部对象都被分配了,每个聚类的聚类中心会根据聚类中现有的对象被重新计算.这个过程将不断重复直到满足某个终止条件.终止条件可以是没有(或最小数目)对象被重新分配给不同的聚类,没有(或最小数目)聚类中心再发生变化,误差平方和局部最小. 2.什么是聚类 聚类是一个将数据集中在某些方面相似的数据成员进行分类组织

  • python算法学习双曲嵌入论文代码实现数据集介绍

    python算法学习双曲嵌入论文代码实现数据集介绍

    目录 1. 目标 Python 代码依赖库 2. 数据集 数据展示 学习的文章: Poincaré Embeddings for Learning Hierarchical Representations 主要参考的代码: poincare_embeddings gensim – Topic Modelling in Python - poincare.py 由于有些代码难以运行,有些比较难读(封装程度非常高)甚至有些代码写得存在一些问题.因此我们重新按照论文的设置,利用Python重现了对应的

  • OpenCV学习方框滤波实现图像处理代码示例

    OpenCV学习方框滤波实现图像处理代码示例

    目录 一.方框滤波 二.C++代码 三.python代码 四.结果展示 1.原始图像 2.归一化 3.不归一化 4.平方和求均值 一.方框滤波    方框滤波是均值滤波的一种形式.在均值滤波中,滤波结果的像素值是任意一个点的邻域平均值,等于各邻域像素值之和的均值,而在方框滤波中,可以自由选择是否对均值滤波的结果进行归一化,即可以自由选择滤波结果是邻域像素值之和的平均值,还是邻域像素值之和. 二.C++代码 #include <iostream> #include <opencv2\ope

  • Ruby实现插入排序算法及进阶的二路插入排序代码示例

    基础 将一个记录插入到一个已经排序好的表中,以得到一个记录增一的有序表.并且最关键的一点就是它把比当前元素大的记录都往后移动,用以空出"自己"该插入的位置.当n-1趟插入完成后该记录就是有序序列. def insertSort(tarray) i=1 while(i < tarray.size) do if tarray[i] < tarray[i-1] j=i-1 x=tarray[i] #puts x.class #puts tarray[i].class tarray

  • 详解堆排序算法原理及Java版的代码实现

    详解堆排序算法原理及Java版的代码实现

    概述 堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(k1,k2,...,kn), 当且仅当满足: 时称之为堆.由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)或最大项(大顶堆). 若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点(有子女的结点)的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的. (a)大顶堆序列:(96, 83, 27, 38, 11, 09) (b)小顶堆序列:(12, 36,

  • 简单理解插入排序算法及Swift版的代码示例

    简单理解插入排序算法及Swift版的代码示例

    算法思想 插入排序的方式类似平时打扑克牌的时候排序自己手中的扑克牌.开始时,我们左手中没有牌,桌上有洗好的扑克牌,我们抓取一张扑克牌并放入左手的正确位置.为了找到一张扑克牌的正确位置,我们从右到左将它与手中的每张牌进行比较,左手上的牌总是排序好的,而这些牌原来都是桌上牌堆中顶部的牌,当我们抓完牌时,左手中的牌自然是有顺序的. 之所以叫插入排序,不是为别的,正是因为该算法的核心就是将无序的元素插入排好序的部分. 插入排序的核心思想即在于划分已排序和未排序,将每个待排序的元素逐个与已排序的元素比较,

  • KMP算法精解及其Python版的代码示例

    KMP算法是经典的字符串匹配算法,解决从字符串S,查找模式字符串M的问题.算法名称来源于发明者Knuth,Morris,Pratt. 假定从字符串S中查找M,S的长度ls,M的长度lm,且(ls > lm). 朴素的字符串查找方法 从字符串S的第一个字符开始与M进行比较,如果匹配失败.从下一字符开始,重新比较.指导第 (ls - lm) 个字符. 这种方法容易想到并且容易理解,效率不高. 问题在于每次匹配失败后,移动的步伐固定为 1,其实步子可以迈得再大一些. KMP的字符串查找方法 假定在模式

  • python算法学习双曲嵌入论文方法与代码解析说明

    python算法学习双曲嵌入论文方法与代码解析说明

    目录 1. 方法说明 损失函数 梯度下降 梯度求解 2. 代码训练过程 3. 结果表现 其他参考资料 本篇接上一篇:python算法学习双曲嵌入论文代码实现数据集介绍 1. 方法说明 首先学习相关的论文中的一些知识,并结合进行代码的编写.文中主要使用Poincaré embedding. 对应的python代码为: def dist1(vec1, vec2): # eqn1 diff_vec = vec1 - vec2 return 1 + 2 * norm(diff_vec) / ((1 -

  • Java语言Consistent Hash算法学习笔记（代码示例）

    本文研究的主要是ConsistentHashing算法代码. 一致性哈希(Consistent Hash) 协议简介 一致性哈希算法在1997年由麻省理工学院提出(参见0),设计目标是为了解决因特网中的热点(Hot pot)问题,初衷和CARP十分类似.一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用. 哈希算法 一致性哈希提出了在动态变化的Cache环境中,哈希算法应该满足的4个适应条件: 平衡性(Balance) 平衡性是指哈希的结果能够尽可能分

随机推荐