0

卢恩算法

用于验证信用卡号码

  1. 从最右边的数字（即校验位）开始，向左移动，每第二位的值加倍；如果这个加倍运算的乘积大于 9（例如，8 × 2 = 16），则将乘积的数字相加（例如，16: 1 + 6 = 7, 18: 1 + 8 = 9）或减法9 来自产品（例如，16：16 - 9 = 7、18：18 - 9 = 9）。
  2. 取所有数字的总和。
  3. 如果总模 10 等于 0（如果总和以 0 结尾），那么根据 Luhn 公式，该数是有效的；否则无效。

执行

#include<stdlib.h>
#include<stdio.h>
#include<stddef.h>

int luhnSum(int);

typedef struct{
  int quotient;
  int remainder;
}Tuple;

Tuple* split(int number){
  /* Split positive number into all but its last digit and its last digit */

  Tuple *tuple = malloc(sizeof(Tuple));
  tuple->quotient = number / 10;
  tuple->remainder = number % 10;
  return tuple;
}

int sumDigits(int number){
  /* Return the sum of digits of positive number n */

  Tuple *tuple = NULL;
  if(number < 10){
    return number;
  }else{
    tuple = split(number);
    return sumDigits(tuple->quotient) + tuple->remainder;
  }
}


int luhnSumDouble(int number){

  Tuple *tuple = split(number);
  int luhnDigit = sumDigits(2*(tuple->remainder));

  if(number < 10){
    return luhnDigit;
  }else{
   return luhnSum(tuple->quotient + luhnDigit);
  }
}

int luhnSum(int number){

  Tuple *tuple = NULL;
  if(number < 10){
    return number;
  }else{
    tuple = split(number);
    return luhnSumDouble(tuple->quotient) + tuple->remainder;
  }
}

int main(void){

}

如何分析相互递归代码的空间和时间复杂度？

4

0 回答 0