Разработка и реализация программ с массивами, страница 2

Так, для массива D: array[1..2, 1..2] real элементы массива размещаются в памяти за ростом адресов: D[1,1], D[1,2], D[2,1], D[2,2].

Задача поиска. Заданные одномерные массивы: массив элементов
A= {a1_, a2 _..., an_{} и список ключей} K= {k1_, k2 _..., kl_{}. Нужно для каждого значения} ki Î K найти все элементы с А, которые равняются ki . Часто встречается ситуация, когда K содержит один ключ k и массив А имеет не более одного такого элемента.

Эффективность алгоритма поиска S оценивается максимальным max(S) и средним avg(S) количеством сравнений, необходимых для определения элемента k, по формулам:

        (i=1,2 ..., n);   (4.1)

                                                                      (4.2)

    где qi - количество сравнений, нужных для поиска элемента ai; fi - относительная частота использования элемента ai, fi=mi/n;
mi  - абсолютная частота использования элемента ai.

Последовательный поиск. Все элементы массива пересматриваются последовательно в порядке размещения, пока не найдется элемент, ровный k. Если не известно, имеется ли искомый элемент, то нужно следить, чтоб поиск не вышел за пределы массива.

Очевидно, что max последовательного поиска равняется n. Если частота f каждого элемента массива одинаковая, f=1/n, то avg последовательного поиска равняется n/2. При разной частоте использования можно улучшить avg, размещая элементы, что встречаются чаще, в начале массива.

Задание 4.1. Представить математическую запись фрагмента программы и вычислить значение переменной Х после его выполнения, если элементы массива определяются по формуле А[I+1]=(37*A[I]+3) mod 64. Значение А[1] равно номеру варианта.

Фрагмент программы.

T:=3; N:=3; X:=A[N+1];

for j:=1 to N do X:=X+A[J]*Exp((N-J-1)*Ln(T));

Математическая запись.

A[1]=19; A[2]=(37*19+3) mod 64=0; A[3]=(37*0+3) mod 64=1;