ЕГЭ, ОГЭ, программирование и робототехника в Калининграде

+7 995 326 44 86

info@future-step.ru

Корзина

Записаться

Алгоритм решения задания 10. Часть 3

Ранее мы разобрали алгоритм решения первых четырёх типов 10 задания ЕГЭ по информатике. В этой статье займёмся оставшимися тремя типами.

Именно это число нам и придётся подбирать в цикле, попутно строя сеть с данными из задания и проверяя все необходимые условия для адресов этой сети.

Разделение по типам будет такое:

  1. В заданиях пятого типа дана маска сети и IP-адрес узла сети с одним отсутствующим байтом (октетом). Нужно найти такое значение этого байта, при котором для всех адресов этой сети будет выполняться заданное условие;
  2. К заданиям шестого типа относятся те, в которых нам даётся маска сети и IP-адрес сети с отсутствующим байтом. Аналогично будем перебирать все допустимые значения для этого байта, при котором для всех адресов этой сети будет выполняться заданное условие;
  3. К оставшемуся — седьмому — типу относятся задания, в которых дан адрес сети и маска с отсутствующим байтом. Требования здесь такие же: перебрать допустимые значения, при которых адреса сети удовлетворяют условию.

Тип 5

Сначала рассмотрим такое задание:

Сеть, в которой содержится узел с IP-адресом 240.224.A.60, задана маской сети 255.255.255.128, где A — некоторое допустимое для записи IP-адреса число.

Определите минимальное значение A, для которого для всех IP-адресов этой сети в двоичной записи IP-адреса суммарное количество единиц будет больше 13.

В ответе укажите только число.

Открыть задание

Что нам нужно здесь сделать:

  1. Построить сеть по данным значениям с неизвестной переменной А;
  2. Эту переменную будем перебирать в цикле;
  3. Для каждого значения A будем проверять, все ли адреса в этой сети имеют количество единиц, большее 13;
  4. Первое же значение А, для которого выполнится условие, выведем на экран — оно и будет минимальным.

Начнём решение с импорта функций и записи маски:

from ipaddress import ip_network, ip_address

mask = '255.255.255.128'

Маску можно записать как обычной строкой, так и префиксом, если вы помните CIDR-нотацию.

Далее пишем цикл, в котором и будем перебирать значения для А:

from ipaddress import ip_network, ip_address

mask = '255.255.255.128'

for A in range(256):

В нём создаём объект IP-адреса и сети с этим адресом.

from ipaddress import ip_network, ip_address

mask = '255.255.255.128'

for A in range(256):
    ip = ip_address(f'240.224.{A}.60')
    net = ip_network(f'{ip}/{mask}', strict=False)

Можно передать в ip_network и готовый объект ip_address, и строку с адресом: оба варианта корректны. Объект ip_address здесь просто делает код понятнее и помогает отделить адрес узла от записи сети.

Нам же осталось только проверить, что во все адреса построенной сети количество единиц больше 13 и вывести на экран первое же значение А, для которого это условие истинно:

from ipaddress import ip_network, ip_address

mask = '255.255.255.128'

for A in range(256):
    ip = ip_address(f'240.224.{A}.60')
    net = ip_network(f'{ip}/{mask}', strict=False)

    if all(f'{int(ip):032b}'.count('1') > 13 for ip in net):
        print(A)
        break

Вместо строчного метода count здесь можно использовать метод bit_count, работу которого мы разбирали в прошлой статье.

Запускаем код и получаем ответ на это задание — число 127.

Пример 1

На очереди у нас такое задание:

Сеть, в которой содержится узел с IP-адресом 127.215.A.32, задана маской сети 255.255.254.0, где  — некоторое допустимое для записи IP-адреса число.

Определите максимальное значение , для которого для всех IP-адресов этой сети в двоичной записи IP-адреса суммарное количество нулей в левых двух байтах не больше суммарного количества нулей в правых двух байтах.

В ответе укажите только число.

Открыть задание

Нечто похожее мы уже решали ранее, так что на объяснение, как получить левые и правые два байта, не будем тратить время.

Импортируем функции, создаём переменную с маской, а в цикле перебираем значения А в обратном порядке, нам ведь нужно найти максимальное:

from ipaddress import ip_network, ip_address

mask = '255.255.254.0'

for A in range(256)[::-1]:

Далее идут объекты IP-адреса и сети:

from ipaddress import ip_network, ip_address

mask = '255.255.254.0'

for A in range(256)[::-1]:
    ip = ip_address(f'127.215.{A}.32')
    net = ip_network(f'{ip}/{mask}', strict=False)

В блоке if сравниваем количество нулей в обеих частях адреса:

from ipaddress import ip_network, ip_address

mask = '255.255.254.0'

for A in range(256)[::-1]:
    ip = ip_address(f'127.215.{A}.32')
    net = ip_network(f'{ip}/{mask}', strict=False)

    if all(f'{int(ip):032b}'[:16].count('0') <=
           f'{int(ip):032b}'[16:].count('0')
           for ip in net):
        print(A)
        break

Запускаем программу и получаем число 241. Его и запишем в ответ.

Пример 2

Последняя для данного типа формулировка:

Сеть, в которой содержится узел с IP-адресом 201.154.34.A, задана маской 255.255.255.224, где A — некоторое допустимое для записи IP-адреса число.

Определите количество значений A, для которых у всех узлов в этой сети в двоичной записи количество нулей в третьем байте больше, чем в четвертом.

В ответе укажите только число.

Открыть задание

Внимательно прочитайте её. Видите отличия от предыдущих? Теперь мы работаем не со всеми адресами сети, а только с адресами её узлов! То есть без широковещательного и адреса сети. Посмотрим, как это отразится на коде.

Начало стандартное:

from ipaddress import ip_network, ip_address

mask = '255.255.255.224'

count = 0

for A in range(256):
    ip = ip_address(f'201.154.34.{A}')
    net = ip_network(f'{ip}/{mask}', False)

А вот теперь нам нужно сначала проверить, что объект IP-адреса не является адресом сети и широковещательным:

from ipaddress import ip_network, ip_address

mask = '255.255.255.224'

count = 0

for A in range(256):
    ip = ip_address(f'201.154.34.{A}')
    net = ip_network(f'{ip}/{mask}', False)

    if ip not in (net.network_address, net.broadcast_address):

И только после этого сравнивать количество нулей в третьем (от 16 до 24) и четвёртом (от 24 до 32) байтах:

from ipaddress import ip_network, ip_address

mask = '255.255.255.224'

count = 0

for A in range(256):
    ip = ip_address(f'201.154.34.{A}')
    net = ip_network(f'{ip}/{mask}', False)

    if ip not in (net.network_address, net.broadcast_address):
        if all(
            f'{int(i):032b}'[16:24].count('0') >
            f'{int(i):032b}'[24:].count('0')
            for i in net.hosts()
        ):
            count += 1

print(count)

После запуска этой программы получим число 120, которое и запишем в ответ.

Тип 6

Задания шестого типа могут выглядеть так:

Сеть задана IP-адресом 32.0.А.5, где А – некоторое допустимое для записи IP-адреса число, и масок сети 255.255.240.0.

Определите минимальное значение А, для которого для всех IP-адресов этой сети в двоичной записи IP-адреса суммарное количество единиц в левых двух байтах не более суммарного количества единиц в правых двух байтах.

В ответе укажите только число.

Открыть задание

Условимся, что в первых 5 строчках у нас меняются только значения маски и IP-адреса:

from ipaddress import ip_network, ip_address

mask = '255.255.240.0'

for A in range(256):
    ip = ip_address(f'32.0.{A}.5')
    net = ip_network(f'{ip}/{mask}', False)

Далее по известному уже принципу сравниваем количество единиц в левых двух и правых двух байтах:

from ipaddress import ip_network, ip_address

mask = '255.255.240.0'

for A in range(256):
    ip = ip_address(f'32.0.{A}.5')
    net = ip_network(f'{ip}/{mask}', False)

    if all(f'{int(ip):032b}'[:16].count('1') <=
           f'{int(ip):032b}'[16:].count('1')
           for ip in net):
        print(A)
        break

Ответом здесь будет число 16.

Пример 2

Все задания этого типа довольно похожи друг на друга. Формулировка теперь следующая:

Сеть задана IP-адресом 127.254.А.10, где А – некоторое допустимое для записи IP-адреса число, и масок сети 255.255.224.0.

Определите максимальное значение А, для которого для всех IP-адресов этой сети в двоичной записи IP-адреса суммарное количество единиц в левых двух байтах не менее суммарного количества единиц в правых двух байтах.

В ответе укажите только число.

Открыть задание

Решение будет идентично предыдущему, разве что поменяются значения маски и адреса, цикл будет перебирать значения в обратную сторону, а знак «<=» заменим на «>=»:

from ipaddress import ip_network, ip_address

mask = '255.255.224.0'

for A in range(256)[::-1]:
    ip = ip_address(f'127.254.{A}.10')
    net = ip_network(f'{ip}/{mask}', False)

    if all(f'{int(ip):032b}'[:16].count('1') >=
           f'{int(ip):032b}'[16:].count('1')
           for ip in net):
        print(A)
        break

В результате получим число 159, которое и будет ответом.

Пример 2

Еще одно похожее задание:

Сеть задана IP-адресом 16.0.А.5, где А – некоторое допустимое для записи IP-адреса число, и масок сети 255.255.192.0.

Определите минимальное значение А, для которого для всех IP-адресов этой сети в двоичной записи IP-адреса суммарное количество нулей в левых двух байтах не менее суммарного количества нулей в правых двух байтах.

В ответе укажите только число.

Открыть задание

Решение здесь всё еще шаблонное, разве что теперь считаем количество нулей, а не единиц:

from ipaddress import ip_network, ip_address

mask = '255.255.192.0'

for A in range(256):
    ip = ip_address(f'16.0.{A}.5')
    net = ip_network(f'{ip}/{mask}', False)

    if all(f'{int(ip):032b}'[:16].count('0') >=
           f'{int(ip):032b}'[16:].count('0')
           for ip in net):
        print(A)
        break

В ответ на это задание записываем число 64.

Тип 7

Начнём разбор 7 типа с такой формулировки:

Сеть задана IP-адресом 191.239.130.3 и маской сети 255.255.А.0, где А – некоторое допустимое для записи маски число.

Определите минимальное значение А, для которого для всех IP-адресов этой сети в двоичной записи IP-адреса суммарное количество единиц в левых двух байтах не менее суммарного количества единиц в правых двух байтах.

В ответе укажите только число.

Открыть задание

В заданиях седьмого типа нам нужно будет перебирать значения для отсутствующего байта маски. Но давайте используем другой подход — будем перебирать не значения байта, а куда меньшие значения длины префикса.

Если неизвестен третий байт маски 255.255.A.0, префикс может принимать значения от /16 до /24 включительно. Поэтому используем range(16, 25): правая граница range не входит в перебор.

Создадим объект адреса и переберём префиксы от /16 до /24 включительно. Такой порядок нужен, потому что в условии требуется минимальное значение третьего байта маски.

from ipaddress import ip_network, ip_address

ip = ip_address('191.239.130.3')

for A in range(16, 25):

Теперь можем построить объект сети по адресу узла и текущему значению префикса:

from ipaddress import ip_network, ip_address

ip = ip_address('191.239.130.3')

for A in range(16, 25):
    net = ip_network(f'{ip}/{A}', False)

Далее идёт уже классическая проверка единиц в левых и правых двух байтах адреса:

from ipaddress import ip_network, ip_address

ip = ip_address('191.239.130.3')

for A in range(16, 25):
    net = ip_network(f'{ip}/{A}', False)

    if all(f'{int(ip):032b}'[:16].count('1') >=
           f'{int(ip):032b}'[16:].count('1')
           for ip in net):

Но теперь мы не выводим значение переменной А на экран. Нам же нужно получить именно значение третьего байта маски. Значит, как только сработает условие, получаем маску данной сети, разделяем по символу точки и выводим на экран строку под индексом 2, то есть третий байт маски:

from ipaddress import ip_network, ip_address

ip = ip_address('191.239.130.3')

for A in range(16, 25):
    net = ip_network(f'{ip}/{A}', False)

    if all(f'{int(ip):032b}'[:16].count('1') >=
           f'{int(ip):032b}'[16:].count('1')
           for ip in net):

        res_mask = str(net.netmask).split('.')
        print(res_mask[2])
        break

Запустив код, получим число 224, которое и запишем в ответ.

Пример 1

Рассмотрим еще одно задание:

Сеть задана IP-адресом 255.215.12.5 и маской сети 255.255.А.0, где А – некоторое допустимое для записи маски число.

Определите минимальное значение А, для которого для всех IP-адресов этой сети в двоичной записи IP-адреса суммарное количество нулей в левых двух байтах не более суммарного количества нулей в правых двух байтах.

В ответе укажите только число.

Открыть задание

Решается оно аналогично предыдущему. Заменяем значение адреса, подсчет единиц на подсчёт нулей и знак нестрогого сравнения:

from ipaddress import ip_network, ip_address

ip = ip_address('255.215.12.5')

for A in range(16, 25):
    net = ip_network(f'{ip}/{A}', False)

    if all(f'{int(ip):032b}'[:16].count('0') <=
           f'{int(ip):032b}'[16:].count('0')
           for ip in net):
        res_mask = str(net.netmask).split('.')
        print(res_mask[2])
        break

В результате получаем ответ — 192.

Пример 2

Заключительное задание будет с такой формулировкой:

Сеть задана IP-адресом 252.63.194.3 и маской сети 255.255.А.0, где А – некоторое допустимое для записи маски число.

Определите минимальное значение А, для которого для всех IP-адресов этой сети в двоичной записи IP-адреса суммарное количество единиц в левых двух байтах не менее суммарного количества единиц в правых двух байтах.

В ответе укажите только число.

Открыть задание

Решение будет следующим:

from ipaddress import ip_network, ip_address

ip = ip_address('252.63.194.3')

for A in range(16, 25):
    net = ip_network(f'{ip}/{A}', False)

    if all(f'{int(ip):032b}'[:16].count('1') >=
           f'{int(ip):032b}'[16:].count('1')
           for ip in net):
        res_mask = str(net.netmask).split('.')
        print(res_mask[2])
        break

А в ответ здесь запишем число 252.

Итоги

В типе 5 перебираем неизвестный байт адреса узла, строим сеть и проверяем условие для всех адресов или только для hosts — точно по формулировке.

В типе 6 неизвестный байт записан в адресе сети. Алгоритм тот же: перебор A, построение сети с strict=False и проверка all.

В типе 7 удобнее перебирать не значения байта маски, а длины префикса. Для третьего байта это диапазон от /16 до /24 включительно, после чего нужный байт берём из net.netmask.

Перед запуском проверьте три вещи: направление перебора, строгий знак сравнения и слова «все IP-адреса» или «все узлы». Именно здесь чаще всего теряется ответ.

На этом мы закончили разбор всех семи типов 10 задания ЕГЭ по информатике. А попрактиковаться в их решении вы можете в нашем тренажёре.

Разберём эту тему на бесплатном пробном занятии

Преподаватель покажет, как решать такие задачи, и подскажет, с чего начать подготовку. Группы до 8 человек, очно в Калининграде и онлайн.

Записаться на пробное занятие

Рекомендуемые статьи