Program Lab7_2; Var

A : Array [1..3] Of Integer; Begin

A[l] : = 8; А[2] : = 12;

А[3] : = А[1] + А[2]; WriteLn('Первый : ', A[l]); WriteLn('Второй : ', А[2]); WriteLn('Третий : ', А[3]); End.

Пояснения к задаче 2

Массив А содержит 3 элемента типа Integer. Размерность массива задана явно в описании массива. Изменение значений элементов массива происходит с помощью оператора присваивания. Результат работы программы мы видим в табл. 14.

		Таблица 14
A[l] – первый элемент	A[2] – второй элемент	A[3] – третий элемент
массива	массива	массива
8	12	20

Задача 3

Приведем пример программы, заполняющей элементы массива размерностью n квадратами их индексов и вывод результата работы программы с помощью оператора цикла For.

Program Lab7_3; Const

n = 9;

Var

A : Array [1..n] Of Integer; I : Integer;

BEGIN {1}

For i : = l To n Do A[i] : = I * i;

WriteLn;

For I : = l To n Do Begin {2}

WriteLn (i, ‘-й элемент’); WriteLn (A[i]);

End; {2}

End. {1}

90

Пояснения к задаче 3

Массив А содержит n элементов типа Integer. Размерность массива задана равной 9 в операторе Const перед описанием массива.

Изменение значений элементов массива происходит с помощью оператора присваивания в цикле с изменением счетчика i последовательно от 1 до 9. На каждом шаге цикла элементу массива с номером i присваивается значение i * i, т. е. квадрат его индекса.

Вывод результата происходит с помощью второго цикла for. На каждом шаге цикла производится вывод значения элемента массива с индексом i.

Результатом работы программы будет столбик чисел, представляющих собой квадраты чисел от 1 до 10, т. е.: 1, 4, 9, 16, ..., 81 с соответствующими пояснениями, какой именно элемент массива выводится.

2.3. Стандартные операции с массивами

Массивы предусмотрены в подавляющем большинстве языков программирования и используются в широком круге задач. При этом все-таки имеются некоторые стандартные операции с массивами, которые часто применяются вне зависимости от функциональной направленности решаемой задачи. Это операции поиска в массиве или его части минимального и (или) максимального значения, а также упорядочение массива или его части – выстраивание элементов некоторым образом, обычно просто по возрастанию или убыванию.

Имеется большое разнообразие задач на одномерные массивы. Как и все задачи вообще, условно их можно разделить на три вида:

1)задачи, решаемые в «одно соображение»;

2)стандартные задачи;

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

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

1.В массиве а каждый элемент равен 0 или 1. Заменить все нули единицами и наоборот.

Решение: достаточно одного оператора присваивания a[i] : = l – a[i] в теле цикла.

2.В массиве каждый элемент равен 0, 1 или 2. Переставить элементы массива так, чтобы сначала располагались все 0, затем все 1 и, наконец, все 2. Дополнительного массива не заводить.

Решение: можно не переставлять элементы массива, а подсчитать количества 0, 1, 2 и заполнить массив заново требуемым образом.

3.Даны два n-элементных массива х и у одного типа. Обменять места-

ми все хi и уi (i = 1, ..., n), не используя промежуточные величины.

Решение: обмен можно выполнить в цикле для всех i от 1 до n с помощью серии из трех операторов присваивания: x[i] : = x[i] + y[i]; y[i] : = x[i] – y[i]; x[i] : = x[i] – y[i].

Перечислим стандартные (типовые) задачи на одномерные массивы:

1)нахождение наибольшего (наименьшего) элемента;

91

2)суммирование элементов (безусловное и условное);

3)подсчет (замена) элементов, удовлетворяющих заданному условию;

4)поиск заданного элемента:

а) в неупорядоченном массиве; б) в упорядоченном массиве;

5)определение заданного расположения элементов;

6)удаление элемента, включение элемента в заданную позицию;

7)переразмещение (инвертирование, циклический сдвиг) элементов;

8)случайная выборка элементов (с повторениями и без повторений);

9)слияние двух упорядоченных массивов в упорядоченный массив;

10)сортировка массива (простые методы).

Мы рассмотрим некоторые задачи из перечня 1–10. Они обязательны, так как формируют основные навыки и некоторые приемы обработки массивов.

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

Ксложным задачам можно отнести улучшенные методы сортировки массивов, поиск моды и медианы массива; алгоритмы генерирования комбинаторных объектов, алгоритмы на графах и т. д.

Задача 4

В некоторых видах спортивных состязаний выступление каждого спортсмена оценивается независимо несколькими судьями. Затем из всей совокупности оценок удаляются наиболее высокая и низкая, а для оставшихся оценок вычисляется среднее арифметическое, которое и идет в зачет спортсмену. Если наиболее высокую оценку выставило несколько судей, то удаляется только одна такая оценка. Аналогично поступают с наиболее низкими оценками.

Дано натуральное число n, положительные действительные числа a1, ..., an (n > 3). Считая, что числа a1, ..., an – это оценки, выставленные судьями одному из участников соревнований, определить оценку, которая пойдет в зачет

этому спортсмену. Program LAB7_4;

Const n = 10;

A : Array [l..n] of Real = (5.4, 5.6, 5.3, 5.8, 5.4, 5.5, 5.5, 5.6, 5.0, 5.7); Var i : 1. .n;

min, max, sum: Real; BEGIN {1}

min : = a[1]; max : = a[1]; sum : = a[1]; for i : = 2 to n do

begin {2}

sum : = sum + a[i];

if a[i] > max Then max : = a[i]; if a[i] < min Then min : = a[i]; end; {2}

92

WriteLn(‘Оценка в зачет: ', (sum – max – min)/(n – 2) : 2 : 2); ReadLn;

END.{1}

Пояснения к задаче 4

Числа-оценки a1, ..., an будем считать элементами массива а. Опишем данные в блоке Const как простую (n) и сложную (массив a) константы. После этого они доступны и хранятся внутри программы. Одномерные массивыконстанты задаются перечислением их элементов в круглых скобках, что равносильно заданию значения присваиванием: а[1] : = 5.4, ..., а[10] : = 5.7.

Пусть max – одна из наивысших оценок, min – одна из самых низких оценок, а sum – сумма всех n (n > 3) оценок, выставленных судьями. Тогда искомую оценку найдем по формуле (sum – max – min)/(n – 2).

Алгоритм поиска минимального (максимального) элемента в неупорядоченном массиве следующий.

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

В программе мы делаем поиск минимального и максимального элементов в массиве вещественных чисел. В этом же цикле суммируем оценки судей и заносим в переменную sum.

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

3. Многомерные массивы

Рассмотрим прямоугольные таблицы, состоящие из чисел и содержащие произвольное число m строк и произвольное число n столбцов. В математике их называют матрицами, а числа, входящие в состав матрицы – ее элементами. Если число строк матрицы совпадает с числом ее столбцов, то матрица называется квадратной.

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

Вобщем виде описание двумерного массива выглядит так:

имя массива : array [НижняяГраницаИндекса1..ВерхняяГраницаИндекса1, НижняяГраницаИндекса2..ВерхняяГраницаИндекса2} of Тип;

array – слово языка Pascal, показывающее, что объявляемый элемент данных является массивом;

93

НижняяГраницаИндекса1, ВерхняяГраницаИндекса1, НижняяГраница-

Индекса2, ВерхняяГраницаИндекса2 – целые константы, определяющие диапазоны изменения индексов и, следовательно, число элементов массива;

тип – тип элементов массива.

1. Можно, например, задать описание массива следующим образом : Var

Map : Array [1..168, 1..9] of Byte;

задает двумерный массив, т. е. прямоугольную таблицу, состоящую из 168 строк и 9 столбцов.

2.Этот же массив можно задать иначе, непосредственно при описании полной переменной:

Var

Map : Array [1..168] of Array [1..9] of Byte;

3.Можно задать описание массива так :

Type

Vector = Array [1..9] of Byte; Var

Map : Array [1..168] of Vector;

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

Map [100], [7] или Map [100, 7] – это элемент, находящийся на пересечении сотой строки и седьмого столбца.

Число элементов массива равно произведению числа строк m на число столбцов n. Следовательно, массив Map содержит 168 * 9 = 1 512 элементов.

3.1. Использование двумерных массивов

Двумерный массив хорошо иллюстрирует различие между физическим и логическим представлением данных. Он представляет собой логическую структуру данных, которая удобна для программирования и решения задач. Двумерный массив может оказаться полезным при описании объекта, который является двумерным физически (например, шахматная доска или карта). Его используют также при организации набора значений или при вычислениях, зависящих от двух параметров, например вычислении значений двойных сумм (задача 5).

В языке Паскаль допускается работа с массивами, размерность которых больше двух. Трехмерный действительный массив может быть объявлен следующим образом:

Var

A : Array [1..3, 1..4, 1..5] of Real;

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

94