Задание 13
В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и маске сети.
Сеть задана IP-адресом 172.16.168.0 и маской сети 255.255.248.0.
Сколько в этой сети IP-адресов, для которых количество единиц в двоичной записи IP-адреса не кратно 5?
В ответе укажите только число.
Теория
В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес, - в виде 4 байтов, причем каждый байт записывается в виде десятичного числа. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и его маске.
Например, Сеть задана IP-адресом 58.27.142.224 и сетевой маской 255.255.255.240. Важно, что в маске сети если встречается нулевой бит =0, то все биты правее тоже 0.
| Адрес сети | 58.27.142.224 | 00111010 | 00011011 | 10001110 | 11100000 |
| Маска | 255.255.255.240 | 11111111 | 11111111 | 11111111 | 11110000 |
| IP | 58.27.142.240-255 | 00111010 | 00011011 | 10001110 | 1110xxxx |
В результате получаем возможные IP-адреса в сети - в данном примере их 16 = 24. Например задача: Сколько в этой сети IP-адресов, для которых количество единиц в двоичной записи IP-адреса кратно 2? Подсчитав количество единиц слева от хххх получили 15 единиц - нечетное, значит на месте хххх или одна (4 варианта) или три единицы (тоже 4 варианта), а всего 8.
Решение
Аналитический способ
Выполним поразрядную конъюнкцию IP-адреса сети 172.16.168.0 с маской сети 255.255.248.0. Два левых байта маски 255 - это 8 единиц - 11111111. Это значит что 172 & 255 = 172 и 16 & 255 = 16. Правый байт 0 & 0 = 0 - 8 нулей. Остается выполнить 168 & 248. 168 = 128 + 32 + 8 и в двоичной системе счисления будет 101010002. 248 = 255 - 7 = 111110002. Тогда 168 & 248 = 101010002 & 111110002 = 101010002 = 168.
172 = 168 + 4 = 101011002 - 4 единицы, в 16 - 1 единица, а в 168 - 3 единицы - всего 8 единиц. В третьем байте 3 значащих нуля, в четвертом 8 нулей, т.е. всего 211 возможных адресов. Самый быстрый способ - из этого количества вычесть те комбинации, когда сумма единиц 2 или 7 в последних 11 битах (8 + 2 =10 кратно 5, 8 + 7 = 15 - тоже кратно), так как мы ищем сумму всех единиц не кратную 5.
Решим две простейшие математические задачи:
Сколькими способами можно расставить сначала 2 единицы, а потом 7 единиц на 11 позициях, который соответствуют последним 11 нулям. (В ЕГЭ по математике (профиль) в 5-м задании может быть формула Бернулли!)
Итого 211 - 55 - 330 = 1663.
Программа
1-й способ
2-й способ
Ответ
1663 (Время не более 5 минут)