Алгоритм Дамма

Этот известный с 2004-го года алгоритм позволяет найти несложные ошибки во введённой последовательности цифр, такие как замену одной цифры на другую и перестановку двух соседних цифр (возможно, не только соседних).

Предварительно для "эталонного" числа должна быть по таблице цифр размерностью 10×10 рассчитана и сохранена единственная контрольная цифра. Если дописать контрольную цифру к числу справа и повторить расчёт контрольной суммы для нового числа, то должен получиться ноль.

Ниже показан небольшой класс, реализующий алгоритм Дамма, он проверялся в консоли Visual Studio 2019. Если конструктору класса передана строка, содержащая ещё что-то кроме десятичных цифр, свойство контрольной цифры check будет установлено в значение -1. Конечно, в класс можно добавить метод для расчёта контрольной цифры нового числа, тогда для проверки множества чисел хватит и одного экземпляра класса.

#include <iostream>
#include <string>
using namespace std;

class Damm {
 private:
  int check;
 public:
  const int table[10][10] = {
   {0, 3, 1, 7, 5, 9, 8, 6, 4, 2},
   {7, 0, 9, 2, 1, 5, 4, 8, 6, 3},
   {4, 2, 0, 6, 8, 7, 1, 3, 5, 9},
   {1, 7, 5, 0, 9, 8, 3, 4, 2, 6},
   {6, 1, 2, 3, 0, 4, 5, 9, 7, 8},
   {3, 6, 7, 4, 2, 0, 9, 5, 8, 1},
   {5, 8, 6, 9, 7, 2, 0, 1, 3, 4},
   {8, 9, 4, 5, 3, 6, 2, 0, 1, 7},
   {9, 4, 3, 8, 6, 1, 7, 2, 0, 5},
   {2, 5, 8, 1, 4, 3, 6, 7, 9, 0},
  };
  Damm (string number) {
   if (!isDigits(number)) { check = -1; }
   else {
    check = calculateCheckSum(number);
   }
  }
  int getCheck() { return check; }
  bool isDigits (const string &str) {
   return str.find_first_not_of("0123456789") == std::string::npos;
  }
  int calculateCheckSum(string s) {
   int d = 0;
   for (int i = 0; i < s.size(); i++) {
    d = table[d][(int)(s[i]-'0')];
   }
   return d;
  }
  bool checkNumber(string s) {
   if (check<0) return false;
   return calculateCheckSum(s+to_string(check))==0;
  }
};

int main() {
 Damm n(string("123453908"));
 int d = n.getCheck();
 if (d<0) cout << "Bad data string, need digits only" << endl;
 else {
  string test1("123453908");
  cout << "Input " << test1 << " is " << (n.checkNumber(test1) ? "correct" : "incorrect") << endl;
  string test2("123453809");
  cout << "Input " << test2 << " is " << (n.checkNumber(test2) ? "correct" : "incorrect") << endl;
 }
 return 0;
}

05.06.2020, 12:27 [1254 просмотра]