Решение
Самый простой способ поиска серийного номера – перебор с вычислением контрольной суммы и сравнением с сохраненной в журнале посещений при известных других параметрах (дата, фамилия). Серийный номер карты лежит в диапазоне от 0 до 9999.
Суть алгоритма перебора: в цикле перебирается серийный номер. Для каждого значения вычисляется контрольная сумма по всем записям из журнала. Если контрольная сумма совпала со значением из журнала, значение серийного номера выводится на экран.
Пример такой программы на языке программирования Python приведён в листинге.
Листинг. Перебор серийных номеров карты
# алфавит
alpha = 'АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ'
# размер алфавита
N = len(alpha) # 32
# параметр модуля и общее число сотрудников
V = 10000
# журнал
# (используются только записи ЛОЖКИНА)
# СТРУКТУРА:
# ДЕНЬ, МЕСЯЦ, ФАМИЛИЯ, CRC
log = [
(3, 7, 'ЛОЖКИН', 2173),
(4, 7, 'ЛОЖКИН', 1836),
(7, 7, 'ЛОЖКИН', 3969),
(8, 7, 'ЛОЖКИН', 5336),
(11, 7, 'ЛОЖКИН', 8373),
(12, 7, 'ЛОЖКИН', 7668)
]
# ВЫЧИСЛЕНИЕ CRC
# Параметры:
# DAY - дата (день)
# MONTH - дата (месяц)
# NAME - фамилия
# SERIAL - серийный номер карты прохода
# RETURN - вычисленное значение CRC
def getCRC(day, month, name, serial):
# массив T для последовательности t0...tp
t = [0 for index in name]
# вычисление последовательности t0..tp
t[0] = 1
for i in range(1, len(t)):
t[i] = (t[i - 1] * day + month) % N
# массив индексов букв-символов фамилии
L = [alpha.index(letter) for letter in name]
crc = 0
for index in range(0,len(t)):
crc = crc + t[index]*L[index]
# умножение на серийный номер и взятие модуля
crc = (crc * serial) % V
return crc
# ПЕРЕБОР серийного номера карты прохода
# Параметры:
# DAY - дата (день)
# MONTH - дата (месяц)
# NAME - фамилия
# CRC - контрольная сумма из записи в журнале
# RETURN - массиы подобранных значений серийных номеров
def bruteSerial(day, month, name, crc):
result = []
for serial in range(V):
check_crc = getCRC(day, month, name, serial)
if check_crc == crc:
result.append(serial)
return result
# ВЫВОД НА ЭКРАН
def listSerials():
# цикл по записям из журнала
for day, month, name, crc in log:
serials = bruteSerial(day, month, name, crc)
print(f'{day:02}.{month:02}, {name}, CRC {crc:04}; Possible serials = {serials}')
if __name__ == '__main__':
listSerials()
В результате выполнения программы получится следующий результат:
03.07, ЛОЖКИН, CRC 2173; Possible serials = [1327]
04.07, ЛОЖКИН, CRC 1836; Possible serials = [1327, 3827, 6327, 8827]
07.07, ЛОЖКИН, CRC 3969; Possible serials = [1327]
08.07, ЛОЖКИН, CRC 5336; Possible serials = [77, 1327, 2577, 3827, 5077, 6327, 7577, 8827]
11.07, ЛОЖКИН, CRC 8373; Possible serials = [1327]
12.07, ЛОЖКИН, CRC 7668; Possible serials = [1327, 3827, 6327, 8827]
Проанализировав вычисленные серийные номера, можно сделать вывод, что только один серийный номер вычисляет корректные контрольные суммы для всех записей в журнале – 1327. Это и есть серийный номер карты ЛОЖКИНА.
Если проанализировать журнал прохода, можно заметить, что ВИЛКИН и ЛОЖКИН ходят на работу в режиме 2 дня через 2 дня. Поэтому для прохода на предприятие лучше выбрать те дни, в которые ЛОЖКИН должен посетить работу: то есть, 17-18 июня, 21-22 июня и так далее.