Файл: Массивы.doc

Простейшим методом поиска элемента, находящегося в неупорядоченном массиве, является последовательны просмотр каждого элемента массива. Перебор элементов заканчивается либо тогда. Когда найдется элемент с искомым значение, либо когда достигнут конец массива – это значит, что такого элемента в массиве нет.

В результате поиска желательно получить индекс искомого элемента, если элемент найден.

Пример – простой перебор в не отсортированном массиве с использование цикла while

{поиск значения X в массиве А}

const n=10;

var a: array [1..n] of integer;

i, X : integer ;found:Boolean ; //признак –элемент найден(true)/не найден(false)

begin

{ввод элементов массива A и значения Х}

found:=false; //пока не начали поиск – элемент не найден

i:=1; // поиск начинаем с первого элемента

{условия выполнения цикла while: пока не найдем (not found), пока не переберем все элементы(i<=n) }

while not found and (i<=n) do

if a[i] =X then found:=true

else inc(i);

if found then writeln(‘значение найдено в позиции ‘, i)

else writeln(‘значение не найдено’);

end.

В этом алгоритме выход из цикла осуществляется по двум условиям: элемент найден или достигнут конец массива. В данном примере цикл while можно заменить на цикл for. В данном случае при нахождении искомого элемента необходимо выйти из цикла с помощью процедуры break. Переменная цикла i не может служить для хранения номера найденного элемента, т.к. ее значение после выхода из цикла неопределенно (это зависит от версии компилятора, от характера оптимизации кода). Поэтому для запоминания номера найденного элемента необходимо ввести дополнительную переменную.

Пример – простой перебор в не отсортированном массиве с использование цикла while

{поиск значения X в массиве А}

const n=10;

var a: array [1..n] of integer;

i, X,p : integer ;found:Boolean ; //признак –элемент найден(true)/не найден(false)

begin

{ввод элементов массива A и значения Х}

found:=false; //пока не начали поиск – элемент не найден

for i:=1 to n do

if a[i] =X then begin

found:=true; p:=i; break; end;

if found then writeln(‘значение найдено в позиции ‘, p)

else writeln(‘значение не найдено’);

end.

Проверку выхода за границу массива можно опустить (тем самым, уменьшив время проверки), если искомый элемент гарантированно находиться в массиве. Такой гарантией может служить барьер – нулевой элемент массива, значение которого равно искомому элементу. Установка барьера производиться до цикла поиска. Обратите внимание, что нумерация в массиве начинается с нуля, и этот элемент не используется для хранения данных.

{Пример – поиск с барьером}

const n=10;

var a: array [0..n] of integer;

i, X : integer ;

begin

{ввод элементов массива A и значения Х}

i:=n; // поиск начинаем с последнего элемента массива

while a[i] <>X do i:=i-1;

if i<>0 then writeln(‘значение найдено в позиции ‘, i)

else writeln(‘значение не найдено’);

end.

Результат поиска равен либо индексу найденного элемента, либо нулю, т.е. индексу барьера, если в массиве элемента нет. Для поиска в среднем требуется (n=1)/2 сравнений. Таким образом, порядок алгоритма линейный.

Поиск можно ускорить, если массив упорядочен. В этом случае чаще всего применяется метод деления пополам или бинарный поиск. Суть этого метода заключается в следующем. Сначала искомый элемент сравнивают со средним элементом массива. Если искомый элемент больше среднего, то поиск продолжается в правой части массива, если меньше среднего – то в левой части. При каждом сравнении из рассмотрения исключается половина элементов: действительно, не имеет смысла искать элемент, значение которого больше среднего, в левой, меньшей по значению элементов половине массива. Максимальное число требующихся сравнений равно log₂n

{Пример - бинарный поиск}

const n=10;

var a: array [0..n] of integer;

Left ,Right,m,i, X : integer ;

begin

{ввод элементов массива A и значения Х}

Left:=1; Right:=n; // задаем начальные значения левой и правой границ поиска

Repeat

m:=(Left+Right) div 2;// нахождение номера m среднего элемента

If x>a[m] then

Left:=m+1 //новая левая граница поиска

Else

Right:=m-1; // новая правая граница поиска

Until (a[m] =x) or (left> right)

if a[m]=X then writeln(‘значение найдено в позиции ‘, m)

else writeln(‘значение не найдено’);

end.

Условия выхода из цикла – искомый элемент найден (a[m]=X) или уже негде искать (left> right).

Ввод-вывод элементов двумерного массива.

Матрицы, как и массивы, нужно вводить (выводить) поэлементно. Блок-схема ввода элементов матрицы изображена на рис.7, построчного вывода на рис.8

Рис.7 Ввод элементов матрицы.

Рис.8 Вывод элементов матрицы.

Пример - Ввод элементов матрицы

const n=3;m=5;

var A: array [1..n,1..m] of integer;{матрица А из n строк и m столбцов}

i,j:integer;

begin

for i:=1 to n do // цикл по строкам

for j:=1 to m do // цикл по элементам i-й строки

begin

write(‘A[‘ , i ,’,’ , j , ’] = ’); readln(A[i,j])

end;

end.

Пример - Вывод элементов матрицы

const n=3;m=5;

var A: array [1..n,1..m] of integer;{матрица А из n строк и m столбцов}

i,j:integer;

begin

…….

for i:=1 to n do // цикл по строкам

begin

for j:=1 to m do // цикл по элементам i-й строки

write(A[i,j]:4);

writeln; // после вывода элементов строки переводим курсор на новую строку

end;

end.

Пример – Фрагмент программы, вычисляющей сумму элементов строк матрицы.

for i:=1 to n do // цикл по строкам

begin

s:=0; // начальное значение суммы для i-й cnhjrb

for j:=1 to m do // цикл по элементам i-й строки, суммируем элементы

s:=s+A[i,j];

writeln(‘Сумма строки №’,i,’ = ‘,s); // вывод суммы

end;

Динамические массивы.

Динамические массивы не имеют фиксированного размера или длины. Память для динамического массива выделяется при вызове процедуры SetLength(var S; NewLength: Integer), где параметры S - динамический массив, а NewLength – новое число элементов. Динамический массив определяется следующей структурой:

array of baseType;

Например, такое объявление:

Var MyArray :array of Real;

задает одномерный динамический массив вещественных чисел. Декларация не распределяет память под элементы массива MyArray. Сама переменная MyArray хранит адрес, по которому располагаются элементы массива. В начале программы самого массива не существует. Для того чтобы создать массив в памяти, необходимо вызвать процедуру SetLength(). Например, такой вызов:

SetLength(MyArray,20);

распределяет массив MyArray из 20-ти вещественных чисел, пронумерованных от 0 до 19. Индекс у динамических массивов всегда целочисленный и начинается с нуля. В процессе выполнения программы размер массива MyArray можно увеличить с помощью процедура SetLength(), задав новое значение числа элементов - SetLength(MyArray,40). Число элементов увеличивается до 40, причем значения первых 20-ти элементов останутся без изменения. В программе не рекомендуется часто увеличивать размер массива на малое число элементов, т.к. изменение размера в большую сторону связано с новым выделением области памяти и копированием туда старых значений массива, с последующим освобождением области памяти, которое они занимали. Такие процедуры могут замедлить выполнение программы. Поэтому лучше увеличивать размер с некоторым запасом.

Для освобождения динамического массива необходимо присвоить переменной массива значение nil (пустой адрес). Динамический массив длины 0 имеет ссылку nil. В программе можно проверить, задан массив или нет сравнив со значением nil. Например:

If MyArray=nil then SetLength(MyArray,20);

При работе с динамическими массивами всегда следует помнить, что переменные хранят ссылки (адреса) на массивы. Поэтому если X и Y – динамические массивы, то оператор X:=Y приведет не к копированию элементов из Y в X, а к распределению элементов X по длине Y (т.е. две переменные будут ссылаться на одну физическую область памяти). Например, после выполнения следующего кода:

Var A, B: array of integer;

Begin

SetLength(A,1);

A[0]:=1;

B:=A;

B[0]:=2;

End.

получаем, что величина А[0] будет равна 0. Если бы А и В были статическими массивами, то А[0] было бы равно единице. Доступ к элементам динамического массива не отличается от доступа к элементам статического массива. Выход за допустимый диапазон индексов не сообщается во время компиляции. В отличие от статических массивов, динамические массивы можно сравнивать на = и <>, при этом будут сравниваться ссылки. Таким образом, после выполнения кода:

Var A, B: array of integer;

Begin

SetLength(A,1); SetLength(B,1);

A[0]:=2;B[0]:=2;

End.

имеем А <> B, но A[0] = B[0].

Для того чтобы усечь динамический массив, можно использовать функцию Copy(). Например, присваивание A:=Copy(A,0,10) оставляет первые 10 элементов массива А.

Если динамический массив распределен, можно использовать стандартные функции Lenght(), High() и Low(). Функция Lenght() возвращает количество элементов в массиве, High() возвращает самое большое значение индекса массива (равное Lenght()-1), а Low() всегда возвращает 0.

Для объявления многомерного динамического массива повторно используют конструкцию array of …, например, выражение:

Type Matrix = array of array of integer;

Var A:Matrix

или

Type Vector = array of integer;

Matrix = array of vector;

Var A:Matrix

объявляет двумерный массив (матрицу) А из целых чисел.

Чтобы выделить память для этого массива, необходимо вызвать процедуру SetLength(A,n,m) с двумя целочисленными параметрами n и m, которые определяют число строк и столбцов в матрице А. Можно создать и непрямоугольный динамический массив. На первом шаге необходимо задать число строк в матрице SetLength(A,9) (задаем 10 строк), далее в цикле зададим число элементов в каждой строке.

For i:=Low(A) to High(A) do

SetLength(A[i],i+1);

После выполнения цикла в первой строке матрицы А – 1 элемент, во второй – 2 элемента и т.д.

Директива компилятора {$R+}

Директива {$R+} - включить (отключить) контроль границ диапазона.

Синтаксис {$R+} или {$R-}

{$RANGECHECKS ON} или {$RANGECHECKS OFF}

Значение по умолчанию {$R-}

{$RANGECHECKS OFF}

При включенной директиве в программу добавляется специальный код, проверяющий все операции с массивами на предмет допустимости заданного индекса. Если при обращении к элементу массива задан индекс, выходящий за диапазон допустимых значений, то программа останавливается и выводит сообщение об ошибке. Директиву {$R+} применяют на стадии отладки программы для выявления ошибок при работе с массивами. В окончательном варианте программы директива должна быть выключена {$R-}, т.к. дополнительный код увеличивает размер исполняемого файла и замедляет работу программы.

Задачи.

Задан массив S(N). Определить максимальный и минимальный элементы массива и их номера. Если таких элементов несколько, то определить сколько их.
Задан массив S(М). Вычислить сумму двух наибольших элементов массива (М>5).
Задан массив S(М). Вычислить сумму двух наименьших элементов массива (М>5).
Задан массив Х(К). Найти разность между средним арифметическим и минимальным элементом массива.
Задан массив Х(К). Найти разность между средним арифметическим и максимальным элементом массива.
Задан массив S(К). Найти сумму элементов с четными индексами и произведение элементов с нечетными индексами.
В массиве Н(N) все отрицательные элементы замените максимальным.
В массиве Н(N) все положительные элементы замените минимальным.
В массиве Х(N) поменять местами минимальный и максимальный элементы.
Задан массив Т(К). Найти минимальный элемент среди элементов с нечетными индексами.
Задан массив Т(К). Найти максимальный элемент среди элементов с четными индексами.
Задан массив Р(M). Найти номер элемента, наиболее отличающегося (по модулю) от среднего значения.
Заданы массивы Х(N), У(N) - координаты точек на плоскости. Определить, какая из точек наиболее удалена от точки А с координатами (x,y).
Заданы массивы Х(N), У(N) - координаты точек на плоскости. Определить, какая из точек наименее удалена от точки B с координатами (k,m).
Задан массив R(K). Вычислить количество элементов, больших среднего арифметического.
Задан массив R(K). Вычислить сумму элементов, меньших среднего арифметического.
Найти максимальный по модулю элемент массива X(N) и поставить его первым.
Найти минимальный по модулю элемент массива X(N) и поставить его последним.
Найти сумму положительных элементов массива У(K) с нечетными индексами.
Найти произведение отрицательных элементов массива Z(K) с четными индексами.
Найти произведение элементов массива H(N), меньших среднего арифметического.
Определить, какой элемент в массиве H(N) расположен раньше: наибольший или наименьший?
Найти сумму и произведение отрицательных элементов массива Z(N).
Задан массив Р(N). Переписать все его элементы, за исключением максимального в массив D.
Задан массив Р(N). Переписать все его элементы, за исключением минимального в массив D.
Задан массив U(K). Вычислить количество элементов, принадлежащих интервалу [a,b].
Задан массив Р(N). Переписать все его элементы, за исключением элементов, принадлежащих интервалу [a,b] в массив D.
Найти количество элементов массива X(N), больших среднего арифметического.
Найти количество элементов массива X(N), меньших среднего арифметического.
Задан массив X(K). Сформировать массив L — номеров положительных элементов массива X.
Проверить является ли матрица Х(N,N) единичной. Матрица является единичной если диагональные(i=j) элементы равны 1, а все остальные – 0.
Задана матрица Х(N,M). Найти номер строки с наибольшим средним значением.
Найти произведение положительных элементов матрицы X(М,N), расположенных по периметру.
Задана матрица Т(N,М). Вычислить максимальный элемент среди лежащих выше диагонали.
Задана матрица Т(N,М). Вычислить минимальный элемент среди лежащих ниже диагонали.
Задана матрица М(N,M). Сформировать вектор Р(N), куда записать максимальные элементы каждой строки.
Задана матрица T(N,M). Максимальный элемент в каждой строке заменить на 0.
Задана матрица T(N,M). Минимальный элемент в каждой строке заменить на 1.
Задана матрица T(N,M). Сформировать вектор Р(M), куда записать максимальные элементы каждого столбца.
Задана матрица H(N,N). Найти максимальный и минимальный элементы, среди лежащих на главной диагонали.
Преобразовать матрицу таким образом, чтобы последний элемент каждой строки был равен среднему арифметическому предыдущих элементов той же строки.
Задана матрица U(M,M).Найти произведение ненулевых элементов матрицы, лежащих выше главной диагонали.
Задана матрица U(M,M). Найти сумму элементов матрицы, лежащих ниже главной диагонали.
Задана матрица U(N,N). Найти максимальный по модулю элемент матрицы и сумму элементов, лежащих на главной диагонали матрицы.
Задана матрица T(N,N). Сформировать массив Р, куда записать номера тех строк, у которых диагональный элемент больше суммы всех остальных.
Задана матрица T(N,M). Сформировать вектор Р(N), где P_i-среднее арифметическое элементов i-ой строки.
Задана матрица P(N,M). Найти сумму положительных элементов и произведение отрицательных элементов матрицы.
Задана матрица T(N,M).Поменять местами К-ю и L-ю строки.(Предварительно проверив существование строк с номерами K и L)
Задана матрица P(N,M). Вывести номера строк, не содержащих нулевые элементы.
Задана матрица P(N,M). Вывести номера столбцов, не содержащих нулевые элементы.

Смотрите также файлы

Модули.doc

Социология_Волков, Добреньков, Нечипуренко, Попов_Учебник_2003 -512с.doc

Немецкий за 3 недели. Иллюстрированный немецко-русский разговорник_Келлер_2000 (with Audio).pdf

kutuzov.doc

Феликс Шарков.Социология общественного мнения. ПРограмма.doc

Файл: Массивы.doc

Поиск в массиве.

Ввод-вывод элементов двумерного массива.

Динамические массивы.

Директива компилятора {$R+}

Задачи.

Смотрите также файлы

Информация

Списки файлов

Дополнительно