Спирина, М.С. Дискретная математика

С = А + В = 410, Y,Ci г= 4 + 1 = 0 = 5; / D =A - B = 214, X ^ , = 2 + l + 4 = 7. i Найдем контрольные коды суммы и разности чисел С и D: r 'c -5 mod 15 = 5; r'D- 7 mod 15 = 7. Сравним результаты: ( /^+ rg )m od l5 = 8 , г'м в = 5, (г^ - mod 15 = = 4, = 7. Видим, что ответы, полученные различными способами, не совпали. Но результат контроля должен быть определен одно­ значно. ? В чем причина плохого результата? Оказывается, цифровой метод контроля не всегда дает точный результат. Это связано с тем, что нарушаются свойства сравнений из-за переносов единиц из одного разряда на другой при выпол­ нении арифметических действий над числами. Во-вторых, сумма цифр зависит от системы счисления, и поэтому необходимо кор­ ректировать контрольный код. Так , пусть заданы числа А и В и их контрольны е коды г'л = ^ a , (m o d р), г'в = X Д (mod р). Найдем контрольные коды гс = i i = гА+в, где С = А + В. Зная цифры о, и Ь, и количество переносов в каждом разряде, можно найти сумму цифр с,. В результате каждого переноса q еди­ ниц (например, q = 100 при заеме из второго разряда в третий операции сложения столбиком) уходит в следующий разряд и од­ новременно добавляется одна единица из младшего разряда. По­ этому сумма цифр уменьшается на q - 1 при каждом переносе. Тогда ( £ С,У = Х<% + X А - Чя ~ 0 . где ^ — количество перено­ сов в больший разряд, возникших в процессе сложения Х а<+ХА - Подставим это выражение вместо суммы цифр. Имеем /£ = (гА+гв - - l(q - l))(modp). Для разности аналогичная формула имеет вид гв = (г'А- г'в + + S(q - l))(modp), где S — количество заемов. Очевидно, что г£ и Го являются требуемыми скорректированными кодами для гА+в и гА_„ соответственно. Если появляется отрицательный остаток, то к сравнению надо добавить модуль р столько раз, сколько потре­ буется для получения первого положительного остатка. Задача 42. В предыдущем примере контрольные коды не совпа­ ли. Проверим их по формулам для случая подсчета контрольного кода с помощью суммирования цифр по модулю. Решение. Имеем г'л = 6 , г'в = 2. Расчет ведем по формуле г'А+в = = ( гА+гв - l ( q - l)(mod/?). Так как Х ^ + = 23, то имеем q - 10, 331