Последовательное распределение. С вычислительной точки зрения простейшим представлением конечной последовательности является список ее членов, расположенных по порядку в последовательных ячейках памяти.
Рис. 2.1.
Последовательное распределение последовательности
для каждого элемента которой требуется
ячеек
Так,
хранится, начиная с ячейки
,
хранится, начиная с ячейки
,
хранится, начиная с ячейки
и так далее, где
- число ячеек, требуемых для хранения одного элемента последовательности.
Описанное выше представление последовательности имеет ряд преимуществ. Во-первых, оно легко осуществимо и требует небольших расходов в смысле памяти. Кроме того, оно полезно и потому, что существует простое соотношение между
и адресом ячейки, в которой хранится
:
Это соотношение позволяет организовать прямой доступ к любому элементу последовательности. Наконец, последовательное представление имеет достаточно широкий диапазон и включает в себя в качестве специального случая представление многомерных массивов.
Например, чтобы представить массив размером
(2.4)
будем рассматривать его как последовательность
, в которой каждое
в свою очередь является последовательностью из
элементов
-й строки нашей матрицы. Таким образом, число ячеек, требуемых для записи элемента
(будем обозначать это число символом
), равно
, где
- число ячеек, требуемых для записи элемента
. Поскольку последовательность
начинается в ячейке
ячейка для
будет иметь следующий адрес:
Это представление известно как построчная запись матрицы; постолбцовая запись получается, если (2.4) рассматривать как последовательность
в которой каждое
в свою очередь является последовательностью из элементов
-го столбца матрицы.
Последовательное распределение, наряду с преимуществами, имеет значительные недостатки. Например, такое представление становится неудобным, если требуется изменить последовательность путем включения новых и исключения имеющихся там элементов. Включение между
и
нового элемента требует сдвига
вправо на одну позицию; аналогично, исключение
требует сдвига тех же элементов на одну позицию влево. С точки зрения времени обработки, такое передвижение элементов может оказаться дорогостоящим, и в случае динамических последовательностей лучше использовать технику связного распределения, рассматриваемую в следующей лекции.
Характеристические векторы. Важной разновидностью последовательного распределения является случай, когда такому представлению подвергается последовательность некоторой основной последовательности
В этом случае можно представить последовательность более удобно, используя характеристический вектор - последовательность из нулей и единиц, где
-й разряд равен единице, если
принадлежит рассматриваемой последовательности, и нулю в противном случае.
Например, характеристический вектор начального сегмента последовательности (2.3)
характеристический вектор для простых чисел:
Здесь основной последовательностью является последовательность целых положительных чисел. В ЭВМ с 32-разрядными словами для запоминания простых чисел, меньших
, потребуется
слов. Замечая далее, что для
число
не простое, можно сэкономить половину этого поля, выписывая разряды только для чисел видов
, и запоминая, что простое число 2 отсутствует. Таким образом, простые числа, меньшие чем
, можно записать только 15625 словами. Поскольку число простых чисел, меньших
, равно 78498, последовательное представление, описанное ранее, потребовало бы поля в пять раз меньшего размера.
Характеристические векторы полезны в ряде случаев. Их полезность вытекает из их компактности, существования простого фиксированного соотношения между
и адресом
-го разряда и возможности при таком представлении очень легко исключать элементы.
Главное неудобство характеристических векторов состоит в том, что они не экономичны. Исключение составляют "плотные" последовательности последовательностей
. Кроме того, их трудно использовать, если не существует простого соотношения между
и
.Если такое соотношение сложное, то использование характеристических векторов может быть очень не экономичным в смысле времени обработки. Если последовательности недостаточно плотные, то значительным может оказаться объем памяти. В случае простых чисел между
и
имеется простое соотношение:
(или
, если использовать только нечетные числа). Теорема о простых числах утверждает, что число простых чисел, меньших
, приблизительно равно
; таким образом, простые числа относительно плотно распределены в множестве целых чисел.
