Алгоритм Дамма
Этот известный с 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 [1252 просмотра]