Арифметика в системах счисления
В любой позиционной системе числа складывают, вычитают и умножают столбиком, только перенос и заём равны основанию P. Неизвестную цифру в записи числа находят перебором всех цифр алфавита программой или по признаку делимости на через сумму цифр. Частное, которое просят в задании 14, программа считает сразу.
Действия в системе с основанием P
Правила столбика те же, что в десятичной системе. Вместо десятка в них стоит основание .
- Сложение: если сумма в разряде не меньше , запишите сумму минус и перенесите 1 в следующий разряд.
- Вычитание: если цифры не хватает, займите 1 из старшего разряда, он даёт единиц младшего.
- Умножение: умножьте на каждую цифру, сдвиньте и сложите частичные произведения по правилам сложения.
- Программа: переведите числа в десятичную систему через
int(s, p), вычислите и переведите результат обратно делением на . - Неизвестная цифра : переберите от 0 до и проверьте условие. Число и сумма его цифр дают одинаковый остаток при делении на .
Сложение столбиком
Запишите числа друг под другом, разряд под разрядом, и складывайте справа налево. Если сумма цифр разряда вместе с переносом меньше , запишите её. Если сумма не меньше , запишите сумму минус , а в следующий разряд перенесите 1. Сумма двух цифр с переносом не больше , поэтому перенос всегда равен 0 или 1.
Цифры больше 9 переводите в числа перед сложением и обратно после: в шестнадцатеричной системе , а сумма 18 даёт цифру и перенос 1. Перевод цифр и развёрнутая запись — в теме позиционные системы счисления.
Пример
Вычислите .
- 1.Разряд 0: . Это не меньше 8: пишем , перенос 1.
- 2.Разряд 1: . Пишем , перенос 1.
- 3.Разряд 2: . Пишем 4, перенос 1.
- 4.Разряд 3: . Это меньше 8, переноса нет.
- 5.Проверка в десятичной системе: .
Ответ:
Вычитание столбиком
Вычитайте справа налево. Если цифра уменьшаемого меньше цифры вычитаемого, займите 1 из соседнего старшего разряда: в младшем разряде она превращается в единиц. Цифра старшего разряда после займа уменьшается на 1. Если в старшем разряде стоит 0, заём идёт дальше влево, а каждый нуль на пути становится цифрой .
Пример
Вычислите .
- 1.Разряд 0: меньше 3. Занимаем из разряда 1: , .
- 2.Разряд 1: после займа осталось , это меньше 4. Занимаем: , .
- 3.Разряд 2: там 0, поэтому заём идёт из разряда 3. Нуль становится цифрой 4, и .
- 4.Разряд 3: после займа , .
- 5.Проверка: .
Ответ:
Умножение столбиком
Умножьте первое число на каждую цифру второго. Произведение двух цифр переводите в систему с основанием : младшая цифра остаётся в разряде, старшая уходит переносом. Каждое частичное произведение сдвиньте влево на номер разряда цифры и сложите все строки столбиком.
В двоичной системе умножать проще всего. Цифра 1 даёт копию первого числа, цифра 0 даёт строку нулей. Остаётся сложить сдвинутые копии.
Пример
Вычислите .
- 1.Цифра 1 в разряде 0 даёт строку .
- 2.Цифра 0 в разряде 1 даёт строку нулей.
- 3.Цифра 1 в разряде 2 даёт со сдвигом на два разряда: .
- 4.Складываем: .
- 5.Проверка: .
Ответ:
Арифметика программой
Программа не считает в P-ичной системе. Она переводит каждое число в десятичную систему функцией int(s, p), выполняет действие и переводит результат обратно: делит на с остатком, пока число больше 0. Цифры больше 9 берут из строки digits: digits[n % p] даёт символ цифры. Сам перевод разобран в теме позиционные системы счисления.
Пример
Вычислите и запишите ответ в шестнадцатеричной системе.
- 1.По столбику: , пишем 2, перенос 1. Затем , пишем 2, перенос 1. Старший разряд — 1.
- 2.Программа переводит слагаемые: .
- 3.Цикл делит 290 на 16 и собирает остатки справа налево. Программа печатает 122.
Ответ:
Неизвестная цифра: перебор программой
В задании 14 в записи чисел стоит неизвестная цифра из алфавита системы, то есть от 0 до . Если больше 10, функция int неудобна: цифру от 10 и больше пришлось бы в каждом шаге цикла превращать в букву. Поэтому запись числа задают списком цифр, а значение считают по схеме Горнера: n = n * p + d для каждой цифры d слева направо. Это та же развёрнутая запись, только без степеней.
Цикл перебирает от 0 до и проверяет делимость: n % m == 0. Для наименьшего цикл идёт вверх и останавливается на первом подходящем значении, для наибольшего — вниз, через range(p - 1, -1, -1). Частное берут через n // m. Делитель и ответ записаны в десятичной системе.
Пример
Значение выражения кратно 7. Найдите наименьшее и частное от деления значения выражения на 7.
- 1.Функция
valueсчитает число по списку цифр: — список[2, x, 5]. - 2.Цикл перебирает от 0 до 8. При : , , сумма .
- 3.При меньших сумма на 7 не делится, поэтому программа печатает 4 и 77.
Ответ: , частное 77
Делимость на P − 1: сумма цифр
, поэтому при делении на любая степень даёт остаток 1. Значит, число в системе с основанием даёт при делении на тот же остаток, что сумма его цифр. Это признак делимости на : число делится на , только если сумма его цифр делится на . Так же работает любой делитель числа : в системе с основанием 19 так проверяют делимость на 18, 9, 6, 3 и 2.
Если делитель в задании равен , сложите цифры всех слагаемых, найдите из условия делимости, а частное получите программой перебора. Если делитель не связан с , сразу пишите программу.
Пример задания
Открытый банк ФИПИ
Операнды арифметического выражения записаны в системе счисления с основанием 15.
В записи чисел переменной x обозначена неизвестная цифра из алфавита 15-ричной системы счисления. Определите наименьшее значение x, при котором значение данного арифметического выражения кратно 14. Для найденного значения x вычислите частное от деления значения арифметического выражения на 14 и укажите его в ответе в десятичной системе счисления. Основание системы счисления в ответе указывать не нужно.
Две неизвестные цифры: условие «при любом y»
Иногда в записи две неизвестные цифры и , а выражение должно делиться на при любом . По остаткам это решают так. Найдите остаток от деления каждой степени на и замените ими степени в развёрнутой записи. Слагаемые с должны в сумме давать кратное при любом , а остальная часть даёт условие на .
В программе условие «при любом » записывают функцией all: all(условие for y in range(p)) истинно, только если условие выполнено для каждого от 0 до . Частное считают при том , который дан в условии.
Пример задания
Открытый банк ФИПИ
Операнды арифметического выражения записаны в системе счисления с основанием 26.
В записи чисел переменными х и у обозначены две неизвестные цифры из алфавита 26-ричной системы счисления. Определите наибольшее значение х, при котором значение данного арифметического выражения кратно 8 при любом значении у. Для найденного значения х вычислите частное от деления значения арифметического выражения на 8 при у = 2 и укажите его в ответе в десятичной системе счисления. Основание системы счисления в ответе указывать не нужно.
Неизвестное вычитаемое и число нулей
Если из суммы степеней вычитают неизвестное небольшое число , запишите выражение по правилу вычитания небольшого числа. Возьмите степень , которая больше любого допустимого . Старшие разряды тогда не зависят от , а меняет только последние цифр: там стоит запись числа с нулями впереди до цифр.
Посчитайте нужные цифры в старших разрядах. Последние цифр подберите так, чтобы общее число совпало с условием. Наибольшему соответствует наименьшее . Проверка программой: цикл по и подсчёт цифр.
Пример задания
Открытый банк ФИПИ
Значение арифметического выражения 7350 + 7150 – x, где x – целое положительное число, не превышающее 2300, записали в семеричной системе счисления. Определите наибольшее значение x, при котором в семеричной записи числа, являющегося значением данного арифметического выражения, содержится ровно 200 нулей.
В ответе запишите число в десятичной системе счисления.
Проверьте себя
00