Системы счисления, сложение, вычитание.

 

Хотите готовиться со мной к ЕГЭ?
Пишите: ydkras@mail.ru
Немного обо мне.

 

В задачах ЕГЭ по информатике иногда нужно выполнять арифметические действия над очень длинными числами в различных системах счисления. В частности, это требуется в задаче 14.

Вот типичная задача из ЕГЭ прошлых лет (задание 14 № 36027 с сайта "Решу ЕГЭ"):

Значение арифметического выражения

7 · 512¹²⁰ − 6 · 64¹⁰⁰ + 8²¹⁰ - 255

записали в системе счисления с основанием 8. Сколько цифр 0 содержится в этой записи?

В общем-то не так сложно решить эту задачу на бумаге. Однако в языке Питон есть две приятные особенности, которые позволяют решать подобные задачи программно. Это, во-первых, возможность работы с очень большими целыми числами, а во-вторых,  операция возведения в степень (обозначается двумя звездочками - **).

Вспомним, как можно получать цифры некоторого целого числа в системе счисления с основанием b. Чтобы получить последнюю цифру числа, надо найти остаток от деления этого числа на b. А если разделить нацело число на b, то результатом будет исходное число без последней цифры. (Полагаю, читателю известно, что в Питоне операция нахождения остатка от деления обозначается знаком процента, а операция целочисленного деления - двумя слэшами.)

Вот универсальная программа для решения задач, подобных приведенной выше:

n = 7*512**120 - 6*64**100 + 8**210 - 255
base=8

d=[0]*base
while n>0:
    d[n%base] += 1
    n //= base
for i in range(base): print(i, d[i]) 

Подробно прокомментируем данную программу.

В первой строке вычисляется значение выражения из условия задачи и результат присваивается переменной n.

Во второй строке задается основание системы счисления.

В третьей строке создается масссив d из нулей. Размер массива - это основание системы счисления. В этом массиве будет храниться количество цифр записи числа в требуемой системе счисления.

Далее организуется цикл, который выполняется, пока число n не станет равным нулю (т.е. пока мы не получим все цифры, которые входят в его запись). Число n%base - это последняя цифра числа n в требуемой системе счисления. Соответствующий элемент массива d увеличивается на единицу, а само число делится нацело на основание системы счисления - в результате получается число без последней цифры. (Операторы += и //= работают следующим образом: берется значение переменной, которая записана слева от оператора,  выполняется операция сложения или целочисленного деления на значение выражения в правой части оператора, а результат присваивается переменной в левой части.)

Когда цикл закончится, то элемент массива d[0] будет содержать количество нулей, d[1] - количество единиц и т.д. В последней строке производится печать этого массива. (К слову, если в условном операторе или операторе цикла присутствует лишь один оператор, то его можно писать не в отдельной строке, а после двоеточия.)

Программа выдает следующий результат:

0 151
1 2
2 0
3 0
4 1
5 0
6 0
7 207

Это означает, что в данном числе, записанном в восьмеричной системе счисления, содержится 151 ноль, две единицы, одна четверка и 207 семерок, а двоек, троек, пятерок и шестерок нет. Следовательно, ответ к задаче - 151.

Переменной n нужно присвоить выражение, которое вычисляет нужное число, а переменной base - основание системы счисления. Программа напечатает, сколько раз в записи этого числа встречается та или иная цифра. Чтобы решить практически любую задачу из соответствующего раздела сайта "Решу ЕГЭ", достаточно изменить в этой программе две первые строки: написать новое выражение для числа и изменить основание системы счисления.

Впрочем, данную конкретную задачу можно решить намного проще: буквально в одну строчку.

Вот эта волшебная строчка:  

print(oct(7*512**120 - 6*64**100 + 8**210 - 255)[2:].count('0'))

Функция oct преобразует целое число в строку, являющуюся восьмеричной записью этого числа. Вырезка [2:] удаляет из строки два первых символа (подробности см. в конце этой статьи), а операция count подсчитывает количество нулей в получившейся строке.

В последнем году задачи на тему сложения и вычитания в различных системах счисления стали более разнообразными. Так, на сайте К.Полякова приводится следующая задача:

(№ 4417) (П. Волгин) Значение выражения (64²⁵ + 4¹⁰) – (16²⁰ + 32³) записали в системе счисления с основанием 4. В каком разряде четверичной записи числа при просмотре справа налево впервые встречается цифра 2? 

Для решения данной задачи приведенную выше программу необходимо переработать. Можно, например, получить и напечатать само число в системе счисления с основанием 4:

 

n = (64**25 + 4**10) - (16**20 + 32**3)
base=4

num = ''
while n>0:
    num = str(n%base) + num
    n //= base
print(num)

 

Результат выполнения следующий:

333333333333333333333333333333333330000000000000000000000000000003320000000

Как видим, первый раз двойка появляется на восьмом месте справа. (Ответ к данной задаче - 7. Очевидно, автор считает, что нумерация разрядов справа налево начинается с нуля. Хорошо было бы явно указать это в условии задачи.)

Данная программа будет работать только для систем счисления с основанием, не превышающим 10. Если нужно большее основание (например, 16), то программу придется доработать, чтобы она корректно выводила шестнадцатеричные  цифры A, B и т.д.

Можно также проверять по очереди все цифры числа (алгоритм получает их именно справа налево) и, как только встретится двойка, напечатать номер разряда. После этого можно прервать цикл.

Вот программа, работающая по такому методу:

n = (64**25 + 4**10) - (16**20 + 32**3)
base=4

k=0
while n>0:
    if n%base == 2:
        print(k)
        break
    k += 1
    n //= base 

В программе учтено, что нумерация разрядов (она содержится в переменной k) начинается с нуля. Поэтому программа печатает правильный ответ, т.е.7.

Есть и другие вариации данной задачи: например, подсчитать сумму цифр некоего большого числа, записанного в системе счисления с некоторым основанием. Решение этой и подобных задач оставляем читателю в качестве упражнения.

Дополнение: полезные функции Питона

В Питоне есть несколько полезных функций, относящихся к переводу чисел в различные системы счисления.

bin - переводит целое число в символьную строку, которая представляет запись данного числа в двоичной системе. В начале строки содержатся символы "0b", за ними следует собственно двоичное число.

oct - работает аналогично bin, переводит целое число в восьмеричную систему счисления,  В начале строки содержатся символы "0o".

hex - перевод целого числа в шестнадцатеричную систему счисления, в начале строки содержатся символы "0x".

str - переводит целое число в символьную строку - запись этого числа в десятичной системе. Никаких дополнительных символов в начале строки нет.

int - переводит символьную строку в целое число. Ей пользуются для преобразования строк, прочитанных из файла, в числа. Однако эта функция может осуществлять перевод чисел, записанных в системе счисления с произвольным основанием, не превышающим 36. Для этого при вызове функции надо указать второй параметр: основание системы счисления, в которой представлено число. Для цифр со значением, большим, чем 9, используются латинские буквы A-Z (можно использовать как строчные, так и заглавные буквы). Так, для перевода строки "8A" (шестнадцатеричное число) в целое значение нужно написать вызов функции int("8A",16).

Если символы "0b" и т.п. в начале строки нам не нужны, их можно удалить, взяв подстроку без первых двух символов (вырезку). Для этого надо за строковым выражением написать операцию получения подстроки: [2:]

Приведем небольшой пример использования этих функций.

n = int( "235", 8 )
print( n )
print( bin(n) )
print( oct(n) )
print( hex(n) )
print( str(n) )
print( bin(n)[2:] )

Результат работы программы следующий:

157
0b10011101
0o235
0x9d
157
10011101

(c) Ю.Д.Красильников, 2021-2022 г.