Задание 14
тема 3 из 3

Арифметика в системах счисления

В любой позиционной системе числа складывают, вычитают и умножают столбиком, только перенос и заём равны основанию P. Неизвестную цифру в записи числа находят перебором всех цифр алфавита программой или по признаку делимости на P−1P - 1 через сумму цифр. Частное, которое просят в задании 14, программа считает сразу.

Часто в задании14На карте навыков

Действия в системе с основанием P

Правила столбика те же, что в десятичной системе. Вместо десятка в них стоит основание PP.

  • Сложение: если сумма в разряде не меньше PP, запишите сумму минус PP и перенесите 1 в следующий разряд.
  • Вычитание: если цифры не хватает, займите 1 из старшего разряда, он даёт PP единиц младшего.
  • Умножение: умножьте на каждую цифру, сдвиньте и сложите частичные произведения по правилам сложения.
  • Программа: переведите числа в десятичную систему через int(s, p), вычислите и переведите результат обратно делением на PP.
  • Неизвестная цифра xx: переберите xx от 0 до P−1P - 1 и проверьте условие. Число и сумма его цифр дают одинаковый остаток при делении на P−1P - 1.

Сложение столбиком

Запишите числа друг под другом, разряд под разрядом, и складывайте справа налево. Если сумма цифр разряда вместе с переносом меньше PP, запишите её. Если сумма не меньше PP, запишите сумму минус PP, а в следующий разряд перенесите 1. Сумма двух цифр с переносом не больше 2P−12P - 1, поэтому перенос всегда равен 0 или 1.

Цифры больше 9 переводите в числа перед сложением и обратно после: в шестнадцатеричной системе F=15\mathrm{F} = 15, а сумма 18 даёт цифру 18−16=218 - 16 = 2 и перенос 1. Перевод цифр и развёрнутая запись — в теме позиционные системы счисления.

Пример

Вычислите 27658+145382765_8 + 1453_8.

  1. 1.Разряд 0: 5+3=85 + 3 = 8. Это не меньше 8: пишем 8−8=08 - 8 = 0, перенос 1.
  2. 2.Разряд 1: 6+5+1=126 + 5 + 1 = 12. Пишем 12−8=412 - 8 = 4, перенос 1.
  3. 3.Разряд 2: 7+4+1=127 + 4 + 1 = 12. Пишем 4, перенос 1.
  4. 4.Разряд 3: 2+1+1=42 + 1 + 1 = 4. Это меньше 8, переноса нет.
  5. 5.Проверка в десятичной системе: 1525+811=2336=4⋅512+4⋅64+4⋅81525 + 811 = 2336 = 4 \cdot 512 + 4 \cdot 64 + 4 \cdot 8.

Ответ: 444084440_8

Вычитание столбиком

Вычитайте справа налево. Если цифра уменьшаемого меньше цифры вычитаемого, займите 1 из соседнего старшего разряда: в младшем разряде она превращается в PP единиц. Цифра старшего разряда после займа уменьшается на 1. Если в старшем разряде стоит 0, заём идёт дальше влево, а каждый нуль на пути становится цифрой P−1P - 1.

Пример

Вычислите 30215−124353021_5 - 1243_5.

  1. 1.Разряд 0: 11 меньше 3. Занимаем из разряда 1: 1+5=61 + 5 = 6, 6−3=36 - 3 = 3.
  2. 2.Разряд 1: после займа осталось 2−1=12 - 1 = 1, это меньше 4. Занимаем: 1+5=61 + 5 = 6, 6−4=26 - 4 = 2.
  3. 3.Разряд 2: там 0, поэтому заём идёт из разряда 3. Нуль становится цифрой 4, и 4−2=24 - 2 = 2.
  4. 4.Разряд 3: после займа 3−1=23 - 1 = 2, 2−1=12 - 1 = 1.
  5. 5.Проверка: 386−198=188=1⋅125+2⋅25+2⋅5+3386 - 198 = 188 = 1 \cdot 125 + 2 \cdot 25 + 2 \cdot 5 + 3.

Ответ: 122351223_5

Умножение столбиком

Умножьте первое число на каждую цифру второго. Произведение двух цифр переводите в систему с основанием PP: младшая цифра остаётся в разряде, старшая уходит переносом. Каждое частичное произведение сдвиньте влево на номер разряда цифры и сложите все строки столбиком.

В двоичной системе умножать проще всего. Цифра 1 даёт копию первого числа, цифра 0 даёт строку нулей. Остаётся сложить сдвинутые копии.

Пример

Вычислите 10112⋅10121011_2 \cdot 101_2.

  1. 1.Цифра 1 в разряде 0 даёт строку 10111011.
  2. 2.Цифра 0 в разряде 1 даёт строку нулей.
  3. 3.Цифра 1 в разряде 2 даёт 10111011 со сдвигом на два разряда: 101100101100.
  4. 4.Складываем: 10112+1011002=11011121011_2 + 101100_2 = 110111_2.
  5. 5.Проверка: 11⋅5=55=32+16+4+2+111 \cdot 5 = 55 = 32 + 16 + 4 + 2 + 1.

Ответ: 1101112110111_2

Арифметика программой

Программа не считает в P-ичной системе. Она переводит каждое число в десятичную систему функцией int(s, p), выполняет действие и переводит результат обратно: делит на PP с остатком, пока число больше 0. Цифры больше 9 берут из строки digits: digits[n % p] даёт символ цифры. Сам перевод разобран в теме позиционные системы счисления.

Пример

Вычислите A316+7F16\mathrm{A3}_{16} + \mathrm{7F}_{16} и запишите ответ в шестнадцатеричной системе.

  1. 1.По столбику: 3+15=183 + 15 = 18, пишем 2, перенос 1. Затем 10+7+1=1810 + 7 + 1 = 18, пишем 2, перенос 1. Старший разряд — 1.
  2. 2.Программа переводит слагаемые: 163+127=290163 + 127 = 290.
  3. 3.Цикл делит 290 на 16 и собирает остатки справа налево. Программа печатает 122.

Ответ: 12216122_{16}

Неизвестная цифра: перебор программой

В задании 14 в записи чисел стоит неизвестная цифра xx из алфавита системы, то есть xx от 0 до P−1P - 1. Если PP больше 10, функция int неудобна: цифру xx от 10 и больше пришлось бы в каждом шаге цикла превращать в букву. Поэтому запись числа задают списком цифр, а значение считают по схеме Горнера: n = n * p + d для каждой цифры d слева направо. Это та же развёрнутая запись, только без степеней.

Цикл перебирает xx от 0 до P−1P - 1 и проверяет делимость: n % m == 0. Для наименьшего xx цикл идёт вверх и останавливается на первом подходящем значении, для наибольшего — вниз, через range(p - 1, -1, -1). Частное берут через n // m. Делитель и ответ записаны в десятичной системе.

Пример

Значение выражения 2x59+x1392x5_9 + x13_9 кратно 7. Найдите наименьшее xx и частное от деления значения выражения на 7.

  1. 1.Функция value считает число по списку цифр: 2x592x5_9 — список [2, x, 5].
  2. 2.Цикл перебирает xx от 0 до 8. При x=4x = 4: 2459=203245_9 = 203, 4139=336413_9 = 336, сумма 539=7⋅77539 = 7 \cdot 77.
  3. 3.При меньших xx сумма на 7 не делится, поэтому программа печатает 4 и 77.

Ответ: x=4x = 4, частное 77

Делимость на P − 1: сумма цифр

P=(P−1)+1P = (P - 1) + 1, поэтому при делении на P−1P - 1 любая степень PkP^k даёт остаток 1. Значит, число в системе с основанием PP даёт при делении на P−1P - 1 тот же остаток, что сумма его цифр. Это признак делимости на P−1P - 1: число делится на P−1P - 1, только если сумма его цифр делится на P−1P - 1. Так же работает любой делитель числа P−1P - 1: в системе с основанием 19 так проверяют делимость на 18, 9, 6, 3 и 2.

Если делитель в задании равен P−1P - 1, сложите цифры всех слагаемых, найдите xx из условия делимости, а частное получите программой перебора. Если делитель не связан с P−1P - 1, сразу пишите программу.

Пример задания

Открытый банк ФИПИ

Операнды арифметического выражения записаны в системе счисления с основанием 15.
 123x515+1x23315123 x 5_{15} + 1 x 233_{15}
В записи чисел переменной x обозначена неизвестная цифра из алфавита 15-ричной системы счисления. Определите наименьшее значение x, при котором значение данного арифметического выражения кратно 14. Для найденного значения x вычислите частное от деления значения арифметического выражения на 14 и укажите его в ответе в десятичной системе счисления. Основание системы счисления в ответе указывать не нужно. 

Две неизвестные цифры: условие «при любом y»

Иногда в записи две неизвестные цифры xx и yy, а выражение должно делиться на mm при любом yy. По остаткам это решают так. Найдите остаток от деления каждой степени PkP^k на mm и замените ими степени в развёрнутой записи. Слагаемые с yy должны в сумме давать кратное mm при любом yy, а остальная часть даёт условие на xx.

В программе условие «при любом yy» записывают функцией all: all(условие for y in range(p)) истинно, только если условие выполнено для каждого yy от 0 до P−1P - 1. Частное считают при том yy, который дан в условии.

Пример задания

Открытый банк ФИПИ

Операнды арифметического выражения записаны в системе счисления с основанием 26.
13ух526+24у132613 ух 5_{26} + 24 у 13_{26}
В записи чисел переменными х и у обозначены две неизвестные цифры из алфавита 26-ричной системы счисления. Определите наибольшее значение х, при котором значение данного арифметического выражения кратно 8 при любом значении у. Для найденного значения х вычислите частное от деления значения арифметического выражения на 8 при у = 2 и укажите его в ответе в десятичной системе счисления. Основание системы счисления в ответе указывать не нужно.

Неизвестное вычитаемое и число нулей

Если из суммы степеней вычитают неизвестное небольшое число xx, запишите выражение по правилу вычитания небольшого числа. Возьмите степень PmP^m, которая больше любого допустимого xx. Старшие разряды тогда не зависят от xx, а xx меняет только последние mm цифр: там стоит запись числа Pm−xP^m - x с нулями впереди до mm цифр.

Посчитайте нужные цифры в старших разрядах. Последние mm цифр подберите так, чтобы общее число совпало с условием. Наибольшему xx соответствует наименьшее Pm−xP^m - x. Проверка программой: цикл по xx и подсчёт цифр.

Пример задания

Открытый банк ФИПИ

Значение арифметического выражения 7350 + 7150 – x, где x – целое положительное число, не превышающее 2300, записали в семеричной системе счисления. Определите наибольшее значение x, при котором в семеричной записи числа, являющегося значением данного арифметического выражения, содержится ровно 200 нулей.
В ответе запишите число в десятичной системе счисления.

Проверьте себя

00

Потренируйте навык

Все задания на этот навык

Решать