Подтема 6 из 6 · дополнительный урок
Маска по условию и сочетания
Как считать адреса формулой вместо перебора и подбирать маску по условию на биты.
Выбор позиций
Дополнительный урок — для продвинутых. В нём задачи, где маску задаёт условие на биты, а сеть так велика, что адреса считают формулой; на экзаменах такие задачи пока не встречались.
Почему в сети задачи темы ровно 120 адресов с 12 единицами?
Адресов с нужным числом единиц столько, сколько способов выбрать позиции для единиц среди свободных битов. Это число сочетаний C(h, r): выбрать r позиций из h. Небольшой пример — 2 единицы в 4 свободных битах: первую позицию выбирают четырьмя способами, вторую — тремя, и каждая пара посчитана дважды: 4 · 3 / 2 = 6. Выбери набор:
- 0011
- 3, 4
- 0101
- 2, 4
- 0110
- 2, 3
- 1001
- 1, 4
- 1010
- 1, 3
- 1100
- 1, 2
В нашей сети 3 позиции из 10: 10 · 9 · 8 / (3 · 2 · 1) = 120. В Python число сочетаний считает из модуля math:
from math import combprint(comb(10, 3), 10 * 9 * 8 // 6)print(comb(4, 0), comb(4, 5))НеобязательноФормула числа сочетаний
C(h, r) = h! / (r! · (h − r)!), где n! = 1 · 2 · … · n, а 0! = 1: выбрать ни одной позиции можно одним способом. Если нужно r позиций, а их больше, чем h, способов нет — 0.
Подсчёт формулой
Если в сетевой части c единиц, а свободных битов h, адресов с k единицами — C(h, k − c), а при k < c — ноль. Функция () заменяет перебор адресов сети:
from ipaddress import ip_networkfrom math import comb def count_ones(net, k): c = f'{net.network_address:b}'.count('1') h = 32 - net.prefixlen if k < c: return 0 return comb(h, k - c) print(count_ones(ip_network('172.20.76.0/22'), 12))print(count_ones(ip_network('10.0.0.0/8'), 20))В сети 10.0.0.0/8 — 16 777 216 адресов, а ответ C(24, 18) = 134 596 получается сразу: в сетевой части две единицы, в 24 свободных битах нужно 18.
Маска по условию
Если маску задаёт условие на биты, программа проверяет его для каждой из 33 длин префикса. Пусть в адресе сети узла 25.140.77.201 единиц столько же, сколько нулей в маске. Сколько адресов этой сети содержат ровно 12 единиц?
from ipaddress import ip_networkfor p in range(33): net = ip_network(f'25.140.77.201/{p}', strict=False) c = f'{net.network_address:b}'.count('1') if c == 32 - p: print(net, c, count_ones(net, 12))Подходит одна маска /23: в адресе сети девять единиц, в маске девять нулей; нужно ещё 3 единицы в 9 свободных битах — C(9, 3) = 84. Если подходят несколько масок, ответ выбирают среди них, как в подтеме 4.
Условие бывает и на номер узла (подтема 3): номер с c единицами среди h битов можно выбрать C(h, c) способами.
from ipaddress import ip_address, ip_networkfrom math import comba = ip_address('129.0.5.96')best = 0for p in range(33): net = ip_network(f'{a}/{p}', strict=False) c = f'{net.network_address:b}'.count('1') number = int(a) - int(net.network_address) if c == f'{number:b}'.count('1'): print(p, c, comb(32 - p, c)) best = max(best, comb(32 - p, c))print(best)Тонкости:второй узел по описанию
«В сети узла 61.200.37.5 есть узел, у которого первый байт совпадает с четвёртым, а второй — с третьим». При маске длиннее 15 битов первые два байта у всех адресов сети — 61 и 200, значит, это узел 61.200.200.61. Дальше — задача о двух узлах: 37 и 200 различаются уже в первом бите третьего байта, C = 16.
Итого
- СочетанияC(h, r) — r позиций из h
- ПодсчётC(h, k − c); при k < c — 0
- comb
from math import comb - Маска по условиюпроверить все 33 длины, ответ выбрать среди них
Проверьте себя
Ответь сначала сам, потом открой ответ.
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Четыре единицы в /27
Сколько адресов сети 10.0.0.0/27 содержат ровно 4 единицы в двоичной записи?
Введите число.
Подсказка
Выбери позиции недостающих единиц среди свободных битов.
Решение
У 10 = 00001010 две единицы, свободных битов 5. Нужно ещё 2 единицы: C(5, 2) = 10.
Решение программой
from math import comb print(comb(5, 4 - 2))Ответ: 10
Десять единиц в /12
Сколько адресов сети 172.16.0.0/12 содержат ровно 10 единиц?
Введите число.
Подсказка
Считай формулой C(h, k − c): перебор сети /12 долгий.
Решение
172 = 10101100 — четыре единицы, первые четыре бита 16 — 0001, одна: c = 5, h = 20. Нужно ещё 5 единиц: C(20, 5) = 15 504 — без перебора миллиона адресов.
Решение программой
from ipaddress import ip_address, ip_network def ones(address): return bin(int(address)).count('1') from math import comb net = ip_network('172.16.0.0/12')c = ones(net.network_address)h = 32 - net.prefixlenprint(comb(h, 10 - c))Ответ: 15504
Маска по условию на единицы
Известно, что в двоичной записи адреса сети, к которой принадлежит узел 12.34.56.78, содержится столько же единиц, сколько нулей в двоичной записи маски этой сети. Сколько адресов, в двоичной записи которых ровно 10 единиц, содержится в этой сети?
Введите число.
Подсказка
Проверь условие для каждой из 33 длин маски.
Решение
Перебор 33 длин находит одну маску /25: в адресе сети семь единиц, в маске семь нулей. Нужно ещё 10 − 7 = 3 единицы в 7 свободных битах: C(7, 3) = 35.
Решение программой
from ipaddress import ip_address, ip_network def ones(address): return bin(int(address)).count('1') from math import comb for p in range(33): net = ip_network(f'12.34.56.78/{p}', strict=False) c = ones(net.network_address) if c == 32 - p: print(comb(32 - p, 10 - c))Ответ: 35
То же условие для другого узла
То же условие для узла 19.6.140.33. Сколько адресов этой сети содержат ровно 12 единиц?
Введите число.
Подсказка
Проверь условие для каждой из 33 длин маски.
Решение
Подходит маска /24: в адресе сети восемь единиц, в маске восемь нулей. Нужно ещё 4 единицы в 8 свободных битах: C(8, 4) = 70.
Решение программой
from ipaddress import ip_address, ip_network def ones(address): return bin(int(address)).count('1') from math import comb for p in range(33): net = ip_network(f'19.6.140.33/{p}', strict=False) c = ones(net.network_address) if c == 32 - p: print(comb(32 - p, 12 - c))Ответ: 70
Условие на номер узла
Для узла 129.0.1.200 количество единиц в двоичной записи адреса сети равно количеству единиц в двоичной записи номера узла в пределах сети. Какое наибольшее число узлов, адреса которых обладают тем же свойством (включая уже названный), может быть в этой сети?
Введите число.
Подсказка
Номер узла — расстояние от адреса сети; номеров с c единицами — C(h, c).
Решение
Свойство выполняется только при /24: у адреса сети три единицы, у номера узла 200 = 11001000 — тоже три. Номеров с тремя единицами среди восьми битов C(8, 3) = 56.
Решение программой
from ipaddress import ip_address, ip_network def ones(address): return bin(int(address)).count('1') from math import comb node = ip_address('129.0.1.200')best = 0for p in range(33): net = ip_network(f'{node}/{p}', strict=False) c = ones(net.network_address) if ones(int(node) - int(net.network_address)) == c: best = max(best, comb(32 - p, c))print(best)Ответ: 56
Ровно 56 адресов с девятью единицами
Узел 10.66.129.3 принадлежит сети, в которой ровно 56 адресов содержат в двоичной записи по 9 единиц. Сколько единиц в двоичной записи маски этой сети?
Введите число.
Подсказка
Проверь каждую длину маски формулой C(h, k − c).
Решение
Для каждой длины считаем адреса с девятью единицами формулой. Ровно 56 их только при /24: c = 6, h = 8, C(8, 3) = 56.
Решение программой
from ipaddress import ip_address, ip_network def ones(address): return bin(int(address)).count('1') from math import comb for p in range(33): net = ip_network(f'10.66.129.3/{p}', strict=False) c = ones(net.network_address) if 9 >= c and comb(32 - p, 9 - c) == 56: print(p)Ответ: 24
Второй узел по описанию
В сети узла 61.200.37.5 есть узел, у которого первый байт совпадает с четвёртым, а второй — с третьим. Укажи наименьшее возможное количество адресов этой сети, в двоичной записи которых ровно 12 единиц.
Введите число.
Подсказка
Сначала построй второй узел по описанию.
Решение
Второй узел — 61.200.200.61. 37 = 00100101 и 200 = 11001000 различаются уже в первом бите третьего байта, самая маленькая общая сеть — 61.200.0.0/16. В ней c = 5 + 3 = 8, h = 16, нужно 4 единицы: C(16, 4) = 1820.
Решение программой
from ipaddress import ip_address, ip_network def net(node, p): return ip_network(f'{node}/{p}', strict=False) def ordinary(node, p): n = net(node, p) address = ip_address(node) return address not in (n.network_address, n.broadcast_address) a, b = '61.200.37.5', '61.200.200.61'same = [p for p in range(33) if net(a, p) == net(b, p)]def ones(address): return bin(int(address)).count('1') from math import comb p = max(p for p in same if ordinary(a, p) and ordinary(b, p))c = ones(net(a, p).network_address)print(comb(32 - p, 12 - c))Ответ: 1820