Технология бесклассовой междоменной маршрутизации (CIDR) позволяет центрам распределения адресов избежать выдачи абонентам излишних адресов.
Деление IP-адреса на номера сети и узла в технологии CIDR происходит на основе маски переменной длины, назначаемой поставщиком услуг. Непременным условием применимости CIDR является наличие у организации, распоряжающейся адресами, непрерывных диапазонов адресов. Такие адреса имеют одинаковый префикс, то есть одинаковую цифровую последовательность в нескольких старших разрядах. Пусть в распоряжении некоторого поставщика услуг имеется непрерывное пространство IP-адресов в количестве 2п (рис. 15.5). Отсюда следует, что префикс имеет длину (32 - п) разрядов. Оставшиеся п разрядов играют роль счетчика последовательных номеров.
Когда потребитель обращается к поставщику услуг с просьбой о выделить ему некоторое число адресов, то в имеющемся пуле адресов «вырезается» непрерывная область 51,52 или 53, в завис. от требуемого количества адресов. При этом должны быть выполнены следующие условия:
---количество адресов в выделяемой области должно быть равно степени двойки;
---начальная граница выделяемого пула адресов должна быть кратна требуемому количеству узлов.
---Очевидно, что префикс каждой из показанных на рисунке областей имеет собственную длину — чем меньше количество адресов в данной области, тем длиннее ее префикс.
3. Сортировка. Дать определение понятия сортировка, привести различные методы сортировки. Описать сортировку выбором и обменом. Описать алгоритм бинарного поиска и поиска перебором.
Сортировка массива — это расстановка элементов массива в некотором порядке. В отсортированном массиве, за счет предварительно выполненной работы по упорядочению, поиск элемента (даже в худшем случае) можно осуществлять, не просматривая весь массив. Пример отсортированного массива — это, например, список телефонов в справочнике, список фамилий в адресной книге и т. д.
Методы сортировки:
Сортировка вставками
Сортировка выбором
3. Сортировка обменом
Сортировка выбором.
Формально его можно описать следующим образом.
На i - м шаге (i = 1,..., N — i):
выбираем из элементов с индексами от i до N максимальный элемент;
меняем местами найденный максимальный и элемент А [i], на i-м месте оказывается максимальный элемент из еще неотсортированной части массива.
После выполнения N— 1-го шага в позиции A [N] будет находиться самый маленький элемент массива.
Название метода, «сортировка выбором» определяется тем, что на каждом шаге мы находим (выбираем) максимальный элемент из еще неотсортированной части массива.
Запишем алгоритм сортировки выбором:
нц для i от 1 до N — 1
K: = i
max: = A [ i ]
нц для j от i + 1 до N
если A [ i ] > max
то max: = A [ j ]
K: = j
все
кц
A [ K ]: = A [ i ]
A [ i ]: = max
кц
Внутренний цикл ДЛЯ j ОТ i + 1 ДО N является алгоритмом поиска максимального алгоритма среди элементов с номерами от i+1 до N. Рассмотрим работу данного метода на массиве
А = {0, 1, 9, 2, 4, 3, 6, 5}.
Максимальный элемент будем подчеркивать.
1) 0, 1, 9, 2, 4, 3, 6, 5
2) 9, 1, 0, 2, 4, 3, 6, 5
3) 9, 6, 0, 2, 4, 3, 1, 5
4) 9, 6, 5, 2, 4, 3, 1, 0
5) 9, 6, 5, 4, 2, 3, 1, 0
6) 9, 6, 5, 4, 3, 2, 1, 0
7) 9, 6, 5, 4, 3, 2, 1, 0
8) 9, 6, 5, 4, 3, 2, 1, 0
Подсчитаем количество сравнений, которые пришлось сделать для упорядочения массива.
На первом шаге для нахождения максимального элемента необходимо (N— 1) сравнение, на втором (N— 2), на третьем (N— 3),..., на последнем шаге —одно сравнение. Найдем сумму:
N – 1 + N – 2 + N – 3 +... + 1 = N (N – 1) / 2 = (N2 — N) / 2.
Примечание. Сумму можно посчитать исходя из следующих соображений. Количество слагаемых равно (N— 1), сумма первого и последнего, второго и предпоследнего и т. д. равна N. Произведение N (N— 1) даст удвоенную сумму, так как каждое слагаемое будет входить в эту сумму дважды, поэтому его нужно разделить на 2.
Количество перестановок элементов равно (N— 1). Это количество определяется внешним циклом ДЛЯ.
Сортировка обменом
Рассмотрим еще один метод сортировки, который формально можно описать так:
На i-м шаге (i = 1,..., N — 1) выполняем:
1. Сравниваем первые два элемента. Если первый меньше второго, то меняем их местами.
2. Сравниваем второй и третий, третий и четвертый,.... N—i и N — i + 1, при необходимости меняя элементы местами. Самый маленький окажется на i-м месте в массиве.
После первого шага самый маленький элемент массива помещается на N-e место. Массив будет отсортирован после просмотра, в котором участвуют только первый и второй элементы.
Название метода «сортировка обменом» определяется тем, что алгоритм основывается на обмене местами двух элементов массива.
Описанный метод сортировок обменом называют также пузырьковой сортировкой.
Алгоритм метода сортировки обменом:
нц для i от 1 до N — 1
нц для j от 1 до N — i
если A [ j ] < A [ j + 1 ]
то x: = A [ j ]
A [ j ]: = A [ j + l ]
A [ j + l ]: = x
все
кц
кц
Рассмотрим его на примере того же массива A = {0, 1, 9, 2, 4, 3, 6, 5}.
1) 1, 9, 2, 4, 3, 6, 5, 0
2) 9, 2, 4, 3, 6, 5, 1, 0
3) 9, 4, 3, 6, 5, 2, 1, 0
4) 9, 4, 6, 5, 3, 2, 1. 0
5) 9, 6, 5, 4, 3, 2, 1, 0
6) 9, 6, 5, 4, 3, 2, 1, 0
7) 9, 6, 5, 4, 3, 2, 1, 0
Число сравнений в данном алгоритме равно также (N 2 - N) / 2.
При каждом сравнении возможна перестановка двух элементов в массиве. Поэтому количество перестановок (в худшем случае) будет равно количеству сравнений, т. е. (N2—N)/2.
* На последних двух проходах в приведенном выше примере массив не менялся. Заметим, что если на каком-то шаге алгоритма элементы массива уже упорядочены, то при последующих проходах по массиву перестановки больше выполняться не будут. Следовательно, как только количество выполненных на последнем проходе перестановок станет равным 0, алгоритм можно заканчивать.
Если запоминать положение (индекс) К последнего обмена, то все пары соседних элементов дальше индекса К уже находятся в желаемом порядке. Поэтому на следующем проходе просмотр можно заканчивать на индексе К.
Р: = «Истина»
К: = N — 1
нц пока Р = «Истина»
Р: = «Ложь»
R: = K
нц для j от 1 до R
если A [ j ] < A [j + 1]
то x: = A [ j ]
A [ j ]: = A [ j + l ]
A [ j + l ]: = x
Р: = «Истина»
K: = j
все
кц
кц
В приведенном фрагменте переменная Р логического типа используется для определения, были перестановки или нет, а переменная К — для хранения индекса последнего обмена. Переменная R является границей, на которой заканчивается просмотр.
Поиск перебором
Чтобы найти какие-то данные в неупорядоченном массиве,
применяется алгоритм простого перебора элементов.
Следующая функция возвращает индекс заданного элемента массива.
Её аргументы: массив с первым индексом 0, количество элементов
в массиве и искомое число. Если число не найдено, возвращается -1.
function SearchPer (Arr: array of Integer; n, v: Integer): Integer;
var
i: Integer;
begin
Result:= -1;
for i:= 1 to n do
if Arr [i] = v then begin
Result:= i;
Exit;
end;
end;
Бинарный поиск
При поиске в упорядоченном массиве можно применить гораздо
более быстрый метод поиска - бинарный.
Суть его в следующем: В начале переменная Up указывает на самый
маленький элемент массива (Up:= 0), Down - на самый большой
(Down:= n, где n - верхний индекс массива), а Mid - на средний.
Дальше, если искомое число равно Mid, то задача решена; если число меньше Mid,
то нужный нам элемент лежит ниже среднего, и за новое значение Up принимается Mid + 1;
и если нужное нам число меньше среднего элемента, значит, оно расположено
выше среднего элемента, и Down:= Mid - 1. Затем следует новая итерация цикла,
и так повторяется до тех пор, пока не найдётся нужное число, или Up не станет больше Doun.
function SearchBin (Arr: array of Integer; v, n: Integer): Integer;
var
Up, Down, Mid: Integer;
Found: Boolean;
begin
Up:= 0; Down:= n;
Found:= False; Result:= -1;
repeat
Mid:= Trunc ((Down - Up) / 2) + Up;
if Arr [Mid] = v then
Found:= True
else
if v < Arr [Mid] then
Down:= Mid - 1
else
Up:= Mid + 1;
until (Up > Down) or Found;
if Found then
Result:= Mid;
end;
