Completion requirements
Задачи с сайта К.Ю. Полякова.
На дополнительном занятии по подготовке к ЕГЭ ученик подсказал интересные задачи.
Номера с 7288 по 7292.
Задачи однотипные, но формулировка очень интересная.
Решил написать аналитическое решение данных задач.
Начнем с номера 7288.
Узлы с IP-адресами 193.45.192.104 и 193.45.206.210 находятся в одной сети. Укажите наименьшее возможное количество принадлежащих этой сети IP-адресов, в двоичной записи которых чётное число единиц.
Задачи интересны тем, что нет маски сети. Нет адреса сети.
Даются только два адреса узла сети и всё. Найдите, мол, наименьшее возможное количество ...
Давайте проанализируем данные задачи.
Первый и второй байты одинаковые, значит маска сети начинается с 255.255.
Соответственно, сама сеть начинается на 193.45.
Дальше нужно проанализировать третьи байты узлов.
Переведем их в двоичную систему счисления.
Изменения битов начались только на пятом слева бите. Значит, можно предположить, что третий байт маски имеет вид 11110000
Соответственно, в адресе сети в его третьем байте не меняются первые четыре бита (1100)
Меняются оставшиеся двенадцать битов. 4 + 8 (если в маске появился ноль, то до конца будут нули)
С первых трёх байтов адреса сети (первые два байта не изменяются - 7 единиц + 2 единицы с неизменяемой части третьего байта) находим девять единиц.
Значит нужно найти комбинации (комбинаторика), когда оставшиеся 12 бит дают нам четное количество единиц.
Используем библиотеку itertools.
Стандартный переборный алгоритм.
Постскриптум:
Вроде бы, простая задача, но на её анализ я потратил очень много времени и вот почему.
Нам сразу в условии сказали, что ищем минимальное количество IP-адресов.
А вот тут обманка)
Ну или просто хитрый вопрос.
Так как мы ищем минимальное количество IP-адресов, значит маска должна быть максимальной!
Ну, естественно наоборот)
Представим, что задача такая:
Узлы с IP-адресами 193.45.192.104 и 193.45.206.210 находятся в одной сети. Укажите наибольшее возможное количество принадлежащих этой сети IP-адресов, в двоичной записи которых чётное число единиц.
Понятно, что предполагать можно и вообще пустую маску, но давайте допустим, что первые два байта также не изменяются. Переведем третьи байты в двоичную систему счисления.
Только теперь команда искать минимальную маску!
Значит достаточно первых двух единиц.
Краткое резюме по выдуманной задаче:
Первый и второй байт адреса сети не меняются.
Остаются семь единиц.
В третьем байте не меняются первые два бита.
Семь плюс два равно девять.
Но!
В отличии от оригинальной задачи К.Ю. Полякова, в выдуманной задаче не 12 битов, которые будут меняться, а 14.
Вносим корректировку в программу.
По остальным заданиям решения под копирку.
План:
Переводим третьи байты адресов узлов в двоичную систему счисления.
Находим максимальную маску.
Считаем единицы или нули, зависит от условия задачи, которые не могут изменяться.
И программой, которая позволяем найти все варианты, просто находим количество.
Скриншоты коротких решений оставшихся заданий прикрепляю ниже.
7289
7290
7291
7292
Last modified: Wednesday, 22 October 2025, 7:41 AM