Задача 13 ЕГЭ по информатике: IP-адреса и маски.
Задача 13 ЕГЭ по информатике: IP-адреса и маски.
Хотите готовиться со мной к ЕГЭ?
Пишите: ydkras@mail.ru
Немного обо мне
Теория (очень кратко)
Интернет - это "сеть сетей". Он состоит из сетей, объединенных между собой. При этом каждая сеть, входящая в Интернет, имеет свой адрес.
Каждое устройство, подключенное к Интернету, входит в какую-либо сеть и имеет так называемый IP-адрес. IP-адрес - это строка из 32 бит. Левая часть этой строки - это адрес сети. Адрес сети одинаков для всех устройств данной сети. Правая часть IP-адреса - это номер узла сети.
Количество бит в адресе сети различно для разных сетей. Сколько именно бит отведено для адреса сети, а сколько - для номера узла, можно узнать по так называемой маске. Маска - это строка из 32 бит, в начале которой расположены единицы, а в конце - нули. Зона с единицами - это адрес сети, а зона с нулями - номер узла.
Для удобства чтения IP-адрес и маску разбивают на 4 группы по 8 бит, каждую такую группу переводят в число в десятичной системе. Получившиеся числа записывают через точку, и получается что-то вроде 192.168.1.5.
Два номера узла имеют специальное значение и не могут быть назначены конкретным устройствам. Номер из всех нулей - это адрес сети. Номер из всех единиц - так называемый широковещательный (при отправке информации на этот номер её получают ксе устройства в данной сети). Если в задаче идёт речь про IP-адреса, то эти два номера допустимы. Если же вопрос касается адрсов конкретных устройств, то эти номера нужно исключить из рассмотрения.
Задача из ЕГЭ 2024 г.
В дальнейшем будем использовать задачу, предлагавшуюся на ЕГЭ в 2024 г. (основная волна 08.06.2024, Дальний Восток).
В терминологии сетей ТСР/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и его маске. Сеть задана IP-адресом 112.160.0.0 и сетевой маской 255.240.0.0.
Сколько в этой сети IP-адресов, для которых количество единиц в двоичной записи IP-адреса не кратно 5?
Решение в Excel/Libreoffice
Вначала переведем адрес сети и маску в двоичное представление. Для этого занесем в ячейки A1:A4 байты адреса сети, а в ячейки B1:B4 - байты маски.
В ячейку C1 запишем формулу
=ДЕС.В.ДВ(A1:8)
(Функция ДЕС.В.ДВ осуществляет перевод целого числа в двоичную систему, её второй параметр - это количество цифр в двоичном числе.)
Скопируем эту формулу во все ячейки диапазона C1:D4 и получим двоичное представление адреса сети и маски:
| A | B | C | D | |
| 1 | 112 | 160 | 0 | 0 |
| 2 | 255 | 240 | 0 | 0 |
| 3 | 01110000 | 10100000 | 00000000 | 00000000 |
| 4 | 11111111 | 11110000 | 00000000 | 00000000 |
Из количества единиц и нулей в маске (ячейки D1:D4) понятно, что адрес сети занимает первые 12 бит, а номер узла - последние 20.
Мы видим, что в битах адреса сети 5 единичных бит, а поле номера узла в сети содержит 20 бит. Чтобы общее число единиц в IP-адресе не было кратно пяти, номер узла должен содержать не кратное пяти число единиц, т.е. число единиц не должно быть равно 0, 5, 10, 15 и 20.
А сколько существует двоичных чисел из 20 цифр (ведущие нули допускаются), которые содержат, например, ровно 3 единицы? Ответ - это число сочетаний из 20 по 3, C203. (В самом деле, нам надо выбрать из 20 позиций три для трех единиц.)
Следовательно, ответ можно получить, подсчитав сумму чисел C20k, где к - набор чисел 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19 (пропущены числа, кратные 5).
Число сочетаний можно вычислять по формуле
Cnk = n!/(k!*(n-k)!)
Для вычисления факториала в Excel/LibreOffice существует функция ФАКТР(n). Но проще воспользоваться функцией для вычисления числа сочетаний. В Excel она называется ЧИСЛКОМБ(n;k), а в LibreOffice Calc - ЧКОМБ(n;k).
Запишем в ячейки A10:A30 целые числа от 0 до 20 (возможные количества единиц в поле номера узла). В ячейку B10 запишем формулу
=ЕСЛИ(ОСТАТ(A10;5)<>0;ЧКОМБ(20;A10);0)
(для LibreOffice Calc)
или
=ЕСЛИ(ОСТАТ(A10;5)<>0;ЧИСЛКОМБ(20;A10);0)
Функция ЕСЛИ нужна для того, чтобы вывести нули для кратных 5 количеств единиц.
Скопируем эту формулу в ячейки B11:B30
Должно получиться следующее:
| 0 | 0 |
| 1 | 20 |
| 2 | 190 |
| 3 | 1140 |
| 4 | 4845 |
| 5 | 0 |
| 6 | 38760 |
| 7 | 77520 |
| 8 | 125970 |
| 9 | 167960 |
| 10 | 0 |
| 11 | 167960 |
| 12 | 125970 |
| 13 | 77520 |
| 14 | 38760 |
| 15 | 0 |
| 16 | 4845 |
| 17 | 1140 |
| 18 | 190 |
| 19 | 20 |
| 20 | 0 |
Осталось подсчитать сумму чисел в правом столбце с помощью функции =СУММ(B10:B30) и получить ответ 832810.
Можно было выписать в левом столбце не все числа от 0 до 20, а только не кратные 5. В этом случае можно было бы в правом столбце использовать более простую формулу =ЧКОМБ(20;A10) или =ЧИСЛКОМБ(20;A10).
Решение на питоне
Решение через числа сочетаний
Модуль математических функций math содержит функцию comb(n,k) - число сочетаний из n по к.
Если мы знаем, что поле адреса сети имеет длину 12 и содержит 5 единиц, а поле номера узла имеет длину 20, то сумму чисел сочетаний для количеств единиц, не кратных 5, можно подсчитать следующей программой:
import math
print(sum([math.comb(20,k) for k in range(21) if k%5!=0]))
Разумеется, необходимо сперва перевести байты адреса и маски в двоичную форму, чтобы узнать количество единиц в адресе сети и длину поля номера узла.
Решение с помощью модуля ipaddress
Сперва опишем необходимые средства для решения нашей задачи. Главные из них - это функции модуля ipaddress.
Эти функции работают с двумя типами данных, которые будут нам полезны. Один - это IP-адрес, другой - сеть (совокупность IP-адресов, которые принадлежат сети, заданной её адресом и маской).
Объект "IP-адрес" создается функцией ipaddress.ip_address. Её параметр - текстовая строка. Пример: ipaddress.ip_address('192.168.1.15')
Объект "сеть" создается функцией ipaddress.ip_network. Её параметр - строка, которая содержит адрес сети и маску, разделенные символом '/'. Пример: ipaddress.ip_network('192.168.1.0/255.255.255.0').
Следует заметить, что если адрес сети будет содержать единицы в поле номера узла (т.е. фактически является не адресом сети, а одним из её IP-адресов), то функция ipaddress.ip_network выдаст ошибку. Чтобы избежать этого, можно указать в функции второй параметр, равный нулю. Пример: ipaddress.ip_network('192.168.1.7/255.255.255.0',0).
Функция ipaddress.ip_network выдаёт полный список адресов, включая адрес сети и широковещательный. Если нам нужны только реальные адреса узлов, следует применить метод hosts(). Пример: ipaddress.ip_network('192.168.1.0/255.255.255.0').hosts().
IP-адреса сети можно получать, например, в цикле for.
Чтобы получить двоичную запись IP-адреса, нужно сперва преобразовать его в целое число с помощью функции int (она работает и с IP-адресами), а это целое число - в двоичное с помощью функции bin. Возможно, что двоичная запись будет содержать менее 32 цифр. Для подсчёта единиц это не имеет значения, но если требуется считать нули, то это приведет к ошибке. Чтобы избежать таких ситуаций, можно воспользоваться методом zfill(32) - он добавляет к строке нули слева до указанной длины.
Теперь приведем полную программу для решения приведенной выше задачи.
import ipaddress
network=ipaddress.ip_network('112.160.0.0/255.240.0.0')
k=0
for ip in network:
if bin(int(ip))[2:].count('1')%5!=0: k+=1
print(k)
Если воспользоваться генератором списков, то программу можно сократить:
import ipaddress
network=ipaddress.ip_network('112.160.0.0/255.240.0.0')
r=[ip for ip in network if bin(int(ip))[2:].count('1')%5!=0]
print(len(r))
Более универсальная программа
Вынесем проверку соответствия IP-адреса условию задачи в отдельную функцию good:
def good(ip):
binip=bin(int(ip))[2:].zfill(32)
return binip.count('1')%5!=0
import ipaddress
network=ipaddress.ip_network('112.160.0.0/255.240.0.0')
r=[ip for ip in network if good(ip)]
print(len(r))
Переменная binip - это двоичное представление IP-адреса длиной 32 бита.
Эту программу дегко адаптировать для решения других задач. Для этого достаточно изменить функцию good и поменять адрес и маску сети.
Решим следующую задачу:
Сеть задана IP-адресом 214.187.224.0 и сетевой маской 255.255.224.0. Сколько в этой сети IP-адресов, для которых количество единиц в двоичной записи IP-адреса не кратно 6, а сами адреса в двоичном виде заканчиваются на 1000?
Программа для решения:
def good(ip):
binip=bin(int(ip))[2:].zfill(32)
return binip.count('1')%6!=0 and binip[-4:]=='1000'
import ipaddress
network=ipaddress.ip_network('214.187.224.0/255.255.224.0')
r=[ip for ip in network if good(ip)]
print(len(r))
Некоторые другие задачи про IP-адреса
(Раздел в разработке, новые задачи добавляются.)
Сеть с маской 255.255.240.0 содержит узел с IP-адресом 228.172.236.0. Сколько в этой сети IP-адресов, для которых количество единиц в двоичной записи IP-адреса не кратно 5?
Задача очень похожа на первую из рассмотренных нами задач. Однако при попытке применить программу, приведенную выше, возникает ошибка. Это происходит потому, что вместо адреса сети указан IP-адрес, который содержит единичные биты в поле номера узла. В данном случае нужно указать в функции ipaddress.ip_network второй параметр, равный нулю:
network=ipaddress.ip_network('228.172.236.0/255.255.240.0',0)
(c) Ю.Д.Красильников, 2025 г.
Комментарии
Отправить комментарий