Основные алгоритмы для работы с одномерными массивами

Одномерным массивом будем называть массив, в котором для указания местоположения элемента достаточно одного индекса.

В разделе описания переменных мы объявили тип массив, а затем отнесли переменную к данному типу. В памяти ЭВМ будет отведено место для размещения элементов массива. Следует особо отметить, что размерность (количество элементов) массива определяется при объявлении типа и изменить количество элементов в процессе работы программы нельзя. Можно пользоваться меньшим количеством элементов.

Наша задача заполнить массив, т.е. каждому элементу дать свое значение, а затем уже обрабатывать по заданному алгоритму. Есть несколько основных алгоритмов, которые необходимо знать. Любую задачу по обработке одномерных массивов можно решить, используя эти основные алгоритмы (такие алгоритмы мы уже называли базовыми).

Перечислим базовые алгоритмы:

1. заполнение одномерного массива значениями;

2. вывод на экран значений элементов одномерного массива;

3. нахождение суммы элементов одномерного массива;

4. подсчет количества элементов, удовлетворяющих заданному условию;

5. поиск максимального (минимального) элемента одномерного массива и его номера.

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

Заполнение.

Заполнить элементы одномерного массива значениями мы можем:

• вводя значения с клавиатуры;

• случайным образом;

• по формуле.

Надо помнить, что во всех трех случаях нам не обойтись без организации цикла.

Поиск максимального (минимального) элемента массива.

Пусть мы имеем одномерный массив:

20,-2, 4, 10,7, 21,-12, 0, 4, 17.

Подумаем, какие операции нужно выполнить, если требуется найти максимальный элемент. Естественно, операцию сравнения Мы не задумываемся над тем, что сравниваем всегда пару, "пробегая" глазами все элементы массива. Алгоритм поиска максимального (минимального) элемента мы построим таким образом чтобы сравнивать пару чисел, повторяя действие сравнения нужное количество раз.

Итак, нам необходимо ответить на два вопроса:

1) какие числа входят в пару, составляющую операцию отношения;

2) сколько раз необходимо повторить операцию сравнения. Введем дополнительную переменную с именем mах. Она и будет одним из чисел, второе число — это очередной элемент массива. Для того, чтобы провести первую операцию сравнения необходимо переменной mах присвоить некоторое начальное значение. Здесь могут быть два варианта:

1) присвоить переменной mах первый элемент массива;

2) присвоить число заведомо меньшее всех элементов массива.

Массив содержит сведения о количестве студентов каждой группы I курса. Определить группу с максимальным количеством студентов, считая, что номер группы соответствует порядковому номеру числа в массиве (считаем, что такая группа единственная).

Другими словами, мы должны найти максимальный элемент и его номер.

program max_num;

type mas=array[ 1.. 10] of byte;

var a: mas;

num, i: byte;

max: byte;

Begin

{блок заполнения}

for i:=l to 7 do

readln(a[i]);

{поиск максимального и его номера}

max:==0;

{вводим самое маленькое число для данного массива}

for i:=l to n do

if a[i]>max then begin

num:=i;

max:=a[i]

end;

writeln('максимальное число студентов=',mах);

writeln('номер группы=',num);

End.

3) Найти минимальный элемент среди четных элементов массива.

Пояснение: мы не можем переменной min присвоить первый элемент массива, т.к. он может быть нечетным. Следовательно мы должны выбрать какое-то очень большое число для данного типа данных.

Если мы объявим элементы массива integer, то таким числом будет +32767.

program min_even;

Var

a:array [1..10] of integer;

i: integer;

min:integer;

Begin

for i:=l to 10 do beein

writeln('введите очередной элемент массива ');

readln(a[i]);

end;

min:=32767;

for i:=l to 10 do

if (a[i]<min) and (a[i] mod 2=0) then min:=a[i];

if min=32767 then writeln ('в массиве нет четных элементов') else writein ('минимальный элемент среди четных элементов массива=',min)

End.

Обратите внимание: необходимо проверить, изменилось ли значение переменной min, т.к. четных элементов могло и не быть.

Двумерные массивы

В предыдущих параграфах мы рассматривали массивы, каждый элемент которых содержал только один индекс. Такие массивы мы называли одномерными. В математике часто используют многомерные массивы, т.е. массивы массивов. Особенно широкое распространение получили двумерные массивы. Такие массивы условно можно изобразить в виде таблицы. С информацией, представленной в виде таблицы, мы очень часто встречаемся в различных областях знаний — экономике, статистике, математике физике, химии и т.д.

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

В математике квадратные и прямоугольные таблицы часто называют матрицами.

Первый индекс — это номер строки, который изменяется только с переходом на следующую строку; второй индекс _ номер столбца. При решении экономических, статистических задач очень часто информация заносится в таблицы, в информатике каждая таблица это тоже двумерный массив.

Про матрицу, имеющую m строк и n столбцов, говорят, что она имеет размер m*n.

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

При решении задач с использованием двумерных массивов во всех случаях (кроме некоторых частных) организуются вложенные циклы.

Перемещение по строке:

For i:=l to m do —> внешний цикл, изменяется номер строки

For j:=l to n do —> внутренний цикл, изменяется номер столбца

Перемещение по столбцу:

For j:=l to n do — > внешний цикл, изменяется номер столбца

For i:=l to m do —> внутренний цикл, изменяется номер строки

Перечислим базовые алгоритмы и рассмотрим каждый из них. Заполнение двумерного массива:

а) по строке,

б) по столбцу.

2. Печать в виде таблицы.

3. Вычисление суммы элементов каждой строки и каждого столбца.

4. Поиск максимального (минимального) элементов каждой строки (столбца) и их индексов.

5. Сумма элементов массива.

6. Максимальный (минимальный) элемент массива.