2.1. Массивы в языке Free Pascal
|
|
Массивы являются одним из наиболее востребованных объектов разделов вычислительной математики. Примерами прикладных задач, при решении которых используются массива являются расчеты электрических цепей, статическая обработка результатов наблюдений, задачи линейного и не линейного программирования и многие другие.
Большие объемы однотипных данных представляются средствами языка программирования, в виде так называемых регулярных типов или массивов.
Использование массивов позволяет заменить большое количество индивидуальных имен каждого объекта одним групповым именем набора данных, за которым в квадратных скобках указывается индекс, определяющий местоположение требуемого значения.
Free Pascal поддерживает массивы двух категорий: статические массивы и динамические массивы.
Для задания статического массива требуется указать его имя (идентификатор), размерность (вектор, матрица, трехмерный массив и т.д.), число элементов по каждому измерению и способ индексации элементов в каждом измерении (тип индекса). При объявлении статического массива в явном или косвенном виде указываются конкретные границы изменения каждого индекса.
Конструкция объявления типа массив имеет следующий вид:
<имя типа> : array[<тип(ы) индекса(ов)>] of <тип элемента>;
Здесь используются два зарезервированных слова: array (массив) и of. Конструкция задает размерность массива и способ индексации.
Приведем примеры объявлений массивов:
Sequence : array[1..10] of Real;
MatrixOfInt : array[-100..100] of Integer;
CubeOfChar : array['a'..'z'] of Char;
Стоит отметить в примерах число элементов массива задается, как число элементов порядкового типа, выбранного в качестве типа индекса. Это означает, что размер памяти, занимаемой массивом, фиксируется во время компиляции и не может быть изменен при исполнении программы – так называемое статическое распределение памяти.
Вторая категория массивов – динамические массивы, объявление которых не содержит указания о границах изменения индексов. Для объявления динамического массива используется стандартная конструкция array без указания диапазона индексов.
<Имя типа данных> : array of <Тип элемента>;
Ниже представлены примеры объявлений динамических массивов:
Sequence : array of Real;
MatrixOfInt : array of Integer;
Так как при объявлении динамического массива не указывается число элементов массива, то компилятор выделяет 4 байта. Фактическое выделение памяти под динамические массивы производится только во время работы программы путем использования процедуры SetLength. Например, SetLength(Sequence,100) выделяется память для хранения 100 элементов для динамического массива Sequence. Важно отметить индексы для динамических массивов всегда отсчитываются от 0. Возникает вопрос, что будет, если вызвать снова процедуру выделение памяти для этого же динамического массива?
- SetLength (Sequence,110) – в этом случае, значения ранее вычисленных элементов сохраняются, а всем добавляемым элементам присваиваются нулевые значения.
- SetLength (Sequence,90) – в этом случае, сохраняются значения начальных 90 элементов, оставшиеся 10 будут безвозвратно потеряны.
2.1.1. Операции над однотипными массивами
В языке Free Pascal выделяет массивы, совместимые по операции присваивания. Рассмотрим пример объявления массивов:
type
my_array = array [1..100] of integer
var
a: my_array;
b: my_array;
c: array [1..100] of integer;
d,e: array [1..100] of integer;
В представленном примере впервые встретился оператор type, который в языке Free Pascal используется для объявление типа. В общем виде объявление выглядит следующим образом:
type
<имя типа> = <определение типа>;
Имя типа – это произвольный идентификатор. Определение типа – синтаксическая конструкция, индивидуальная для различных способов объявления типов данных.
В приведенном примере фрагменты массивов a, b совместимы между собой по операции присваивания. Массив с не совместим ни с одним из представленных массивов Массивы d,e также совместимы между собой по операции присваивания, но не совместимы с другими массивами.
Для массивов, совместимых по операции присваивания разрешается выполнение следующей операции:
a := b;
Стоит отметить данная операция по-разному выполняется для статических и динамических массивов. Операции над динамическими массивами рассматриваются в более поздних главах.
При работе с массивами важно иметь возможность доступа к элементу массива. Индекс элемента записывается в квадратных скобках после имени массива. Индекс представляет собой в общем случае выражение указанного при объявлении массива типа. Например, элементу 2 массива Х присваивается значение 10.
x[2] := 10;
Или на экран выводится значение 5 элемента массива Y.
Writeln (y[5]);
Присваивание значений элементам массива может осуществляться разными способами: пользователь вводит значения элементов массива, программист в коде программы указывает значения элементов массива, значения элементов массива формируются с помощью датчика случайных чисел в случае использования массива целых чисел. Ниже представлен код программы, в которой значения элементов массива определяются пользователем.
program InputData;
var
N, i: Word;
A: array [1..100] of integer;
begin
...
Writeln('Введите количество чисел последовательности');
Readln(N);
for i := 1 to N do
begin
writeln('Введите число’);
readln(A[i])
end;
...
end.
2.2. Поиск элемента массива на основе линейного просмотра
Поиск элемента массива является одной из наиболее распространенных задач обработки массивов. Рассмотрим пример постановки подобной задачи: дан список абитуриентов поступивших в высшее учебное заведение, определить зачисление по заданной фамилии абитуриента. При разработке алгоритма решения данной задачи возникает вопрос: список студентов упорядочен по алфавиту или нет? В формулировке задачи не указано, что список поступивших отсортирован по алфавиту. Для поиска фамилии абитуриента в списке поступивших необходимо сравнивать каждую фамилию из списка с заданной фамилией. Если будет найдено полное соответствие, значит, абитуриент поступил, в противном случае после проверки всех фамилий можно утверждать данный абитуриент не поступил. Данное описание поиска носит название линейный просмотр.
Для представления словесного описания линейного поиска введем обозначения переменных: переменная val – искомое значение; переменная pos – индекс ячейки массива, в которой содержится искомое значение; переменная ResultOk – переменная булевского типа, принимает значение Истина, если искомый элемент будет найден, в противном случае принимает значение Ложь.
- Полагается Pos:=0 и ResultOk :=false, значение переменной цикла j :=1;
- Если A[j] = Val, то переменные Pos и ResultOk присваиваются соответственно значения Pos := j, ResultOk := true и алгоритм завершает работу. В противном случае значение переменной цикла увеличивается на единицу j := j + 1;
- Если j <= Last, где Last число элементов массива А, то выполняется шаг 2, в противном случае – работа алгоритма завершена.
Ниже представлена программа решающую поставленную задачу.
program Line_find;
var
N, j, Pos: Word;
A: array [1..100] of String;
Val:string;
ResultOk: Boolean;
begin
...
Writeln('Введите фамилию абитуриента');
Readln(Val);
{ Цикл поиска }
ResultOk:= false;
for j := 1 to N do { N – общее число поступивших
абитуриентов }
if A[j] = Val then
begin
ResultOk:= true;
Pos := j; { Запоминаем номер }
break; { Если нашли, заканчиваем цикл }
end;
if ResultOk = true then
Writeln('данный абитуриент поступил', Pos)
else
Writeln('к сожалению, данный абитуриент не поступил');
...
end.
В представленной программе для выхода из цикла используется оператор break. В процессе поиска искомая фамилия абитуриента может быть найдена и продолжать поиск дальше смысла не имеет. В тоже время цикл с известным количеством повторений будет работать дальше, до тех пор, пока не будут выполнены заданные количество повторений. Поэтому для остановки поиска и завершения работы цикла используется оператор break.
2.3. Поиск минимального, максимального элемента массива. Подсчет суммы всех элементов массива
Любая программа, работающая с большими объемами информации, прежде всего, должна решать задачу построения информационной модели предметной области, то есть представления данных. Массивы в этом смысле являются классическим и достаточно удобным средством хранения большого количества однотипных данных. Следующим шагом возникает проблема обработки этих данных: поиск минимального, максимального элемента массива, подсчет суммы всех элементов массива, сортировка элементов массива.
Постановка задачи поиска максимального элемента в массиве формулируется следующим образом: в заданной последовательности числе найти максимальное значение. Представим словесное описание алгоритма:
- Объявляем переменную max,в которой будет хранится максимальный элемент массива. Данной переменной присваиваем значение первого элемента массива;
- Устанавливаем значение счетчика цикла равным двум (значение первого элемента массива рассматривалось на предыдущем шаге). Сравниваем значения элементов массива с переменной max. Если значение элемента массива больше значения переменной max, то присваиваем переменной max значение элемента массива;
- Если остались не рассмотренные элементы массива увеличиваем счетчик цикла на единицу и повторяем предыдущий шаг. В противном случае алгоритм завершает работу.
Поиск минимального элемента в массиве осуществляется аналогичным образом. Лишь на втором шаге используется другая операция сравнения «меньше».
Ниже представлена программа решающую поставленную задачу.
program Find_max_min;
var
N, i: Word;
A: array [1..100] of integer;
max, min: integer;
pos_max, pos_min: word;
begin
...
min := A[1];
pos_min := 1;
max := A[1];
pos_max := 1;
{ Цикл поиска }
for i := 2 to N do { N – общее число чисел
последовательности }
begin
if A[i] > max then
begin
max := A[i];
pos_max := i; { Запоминаем номер }
end;
if A[i] < min then
begin
min := A[i];
pos_min := i; { Запоминаем номер }
end;
end;
Writeln('максимальный элемент последовательности’, max , ’находится в ячейке с индексом’,pos_max);
Writeln('минимальный элемент последовательности’, max , ’находится в ячейке с индексом’,pos_max);
...
end.
Перейдем к следующей задаче: подсчет суммы всех элементов массива. Алгоритм решения данной задачи будет состоят из нескольких шагов. На первом шаге объявляется переменная Summa, в которой будет хранится сумма всех элементов. Значение этой переменной обнуляется. Далее в цикле от первого до последнего элемента массива значения каждой ячейки добавляются к переменной Summa. Код программы выполняющая суммирование всех элементов массива представлен ниже:
program summa_value;
var
N, i: Word;
A: array [1..100] of integer;
Summa: integer;
begin
...
Summa := 0;
{ Цикл суммирования }
for i := 1 to N do { N – общее число чисел
последовательности }
Summa := Summa + A[i]
Writeln('Сумма всех элементов массива равна’, Summa);
...
end.
2.4. Упорядочивание (сортировка) массивов
Рассматривается задача сортировки (упорядочивания) массива в порядке возрастания (убывания) его элементов. При решении этой задачи требуется исходный массив, содержащий произвольные целые числа преобразовать к виду, когда каждый элемент массива находится перед другим элементов этого массива, если его значение меньше (больше), чем значение сравниваемого элемента.
Задачи сортировки являются важными и широко распространенными в практике. Например, поставщики компьютеров, утверждают, что в среднем более 25% времени общего использования машин тратится на сортировку.
2.4.1. Метод сортировки выбором
Алгоритмическое описание метода сортировки выбором. Исходный массив длиной N разбивается на две части: итог и остаток. Участок массива, называемый итогом, располагается в начале массива и должен быть упорядоченным, а участок массива, называемый остатком, располагается вплотную за итогом и содержит исходные числа не отсортированной части исходного массива. Пусть первый элемент остатка является j-ым элементом массива.
- Полагается j:= 1, т.е. считается, что итоговый участок пуст.
- В остатке массива ищется минимальный и меняется местом с первым элементом остатка ( j – ым элементом массива). После чего значение j увеличивается на единицу, тем самым расширяя итоговый участок массива (отсортированную часть исходного массива)
- Если j < N, то повторяется шаг 2. В противном случае - завершение работы алгоритма, т.к. итог становится равным всему массиву.
Перейдем к написанию программы выполняющую сортировку элементов массива используя метод выбора.
program SelectSort;
var
N, i, j: Word;
A: array[1..100] of Integer;
temp: Integer;
begin
...
{ Сортировка }
for j := 1 to N -1do
for i := j+1 to N do
if A[i] < A[j] then
begin
temp := A[i];
A[i] := A[j];
A[j] := temp;
end;
...
end.
2.4.2. Метод сортировки пузырьком
Алгоритмическое описание метода пузырьком. Аналогично, как и в методе выбора, исходный массив длиной N разбивается на две части: отсортированную (итог) и не отсортированную (остаток). Пусть первый элемент остатка является j-ым элементом массива.
- Пусть j := 2, т.е. итоговой участок состоит из одного элемента.
- Берется первый элемент остатка и перемещается на место в итоговый участок массива так, чтобы итог остался упорядоченным. Первый элемент остатка назовем перемещаемым. Перемещение выполняется путем сравнения перемещаемого элемента с предшествующим ему элементом. Если предшествующий элемент меньше сравниваемого элемента, то процесс перемещения закончен. В противном случае сравниваемые элементы переставляются и, если элемент не достиг начала массива, то повторяется шаг 2
- После того, как первый элемент остатка переместился в итоговый участок, увеличивается на единицу значение переменной j, тем самым увеличивая отсортированную часть массива. Если j < N, то управление передается на шаг 2. В противном случае - завершение работы алгоритма.
Ниже представлен код программы осуществляющая сортировку массива с помощью метода пузырьком.
program BubbleSort;
var
N, i, j: Word;
A: array[1..100] of Integer;
temp: Integer;
begin
...
{ Сортировка }
for i := 2 to N do
for j := N downto i do
if A[j] < A[j - 1] then
begin
temp := A[j];
A[j] := A[j - 1];
A[j - 1] := temp;
end;
...
end.
2.4.3. Метод сортировки включением
Этот метод похож на метод пузырька. Происходит такое же разбиение массива на отсортированную и не отсортированную части, но перемещение первого элемента остатка на принадлежащее ему место в итоге делается не сравнением двух соседних элементов, а с помощью метода двоичного поиска.
- Пусть j := 2, т.е. итоговой участок состоит из одного элемента.
- Берется первый элемент остатка и перемещается в отсортированную часть массива так, чтобы итоговый участок остался упорядоченным. Далее с помощью метода двоичного поиска (см [3]), определяется номер элемента массива, на месте которого должен бы находиться перемещаемый элемент. Если этот номер указывает на место в итоговом участке массива, то сдвигаются все элементы итогового участка массива, начиная с этого номера на одно место вправо, а перемещаемый элемент ставится на освобожденное место.
- После того, как первый элемент остатка переместился в итоговый участок, увеличивается на единицу значение переменной j, тем самым увеличивая отсортированную часть массива. Если j < N, то управление передается на шаг 2. В противном случае - завершение работы алгоритма.
Реализуем программу сортировки элементов массива методом включения.
program InsertSort;
var
N, i, j: Word;
A: array[1..100] of Integer;
temp: Integer;
left, right,middle, pos:integer;
begin
{ Сортировка методом включением}
for i := 2 to N do
begin {поиск в массиве бинарным способом}
left := 1;
right := i-1;
repeat
middle := left + (right-left) div 2;
if (A[middle]>A[i]) then
begin
right := middle;
pos := right;
end
else begin
left :=middle;
pos := left;
end;
until right-left <=1;
if (pos <> i-1) then begin
temp := A[i];
for j := i downto pos do
A[j] := A[j - 1];
A[pos] := temp;
end;
end;
...
end.
2.5. Обработка строковой информации
Строковый тип данных, рассмотренный в главе 2, в языке Free Pascal представляют собой массив символов длиной не более 255. При этом нулевой байт содержит фактическую длину строки, остальные 255 –символы. Элементами массива принадлежат типу Char. Например:
var
S: String;
begin
S := 'Пример';
end.
В представленном примере переменная S представляет массив символов (см рис. 3.1).
Рис. 3.1.Строка – одномерный массив символов
Первый байт указывает длину строки равной 6.
При написании программ можно использовать функции и процедуры, работающие над строковыми данными. Отметим процедуры и функции рассматриваются в следующей главе.
- Функция Length - позволяет определить фактическую длину текстовой строки, хранящейся в указанной переменной
Объявление функции Length
Length(s:string):integer
Пример использования функции length.
n := length('Pascal'); {n будет равно 6}
- Функция Concat (Str1, Str2, ..., StrN) выполняет конкатенацию (или сцепление) строк Str1, Str2, ..., StrN в том порядке, в каком они указаны в списке параметров. Общее количество символов всех сцепленных строк не должно превышать 255.
Объявление функции Concat
Concat(s1,[s2,...,sn]:string):string
Пример использования функции Concat
program DemoFunctionConcat;
var
Word : string;
Word1, Word2 : string[20];
begin
Word1 := 'Free ';
Word2 := 'Pascal';
Word := Concat(Word1,Word2);
writeln(Word); {выводится текст 'Free Pascal'}
end.
- Функция Copy позволяет копировать фрагмент некоторой строки из одной переменной в другую. Вызывая эту функцию, нужно указать следующие параметры: имя строки, из которой должен извлекаться копируемый фрагмент, позицию в строке, начиная с которой будет копироваться фрагмент, число копируемых символов.
Объявление функции Copy
Copy(s:string; index:integer; count:integer):string
Пример использования функции Copy
program DemoFunctionCopy;
var
Word : string;
Word1 : string[20];
begin
Word1 := 'Free Pascal';
Word := Copy(Word1,1,4);
writeln(Word); {выводится текст 'Free'}
end.
- Функция Delete позволяет удалить подстроку в строке. Вызывая эту функцию, нужно указать следующие параметры: имя строки, в которой будет удаляться подстрока; позицию в строке, начиная с которой будет осуществляться удаление, число удаляемых символов.
Объявление функции Delete
Delete (var s:string; index:integer; count:integer):string
Пример использования функции Delete
program DemoFunctionDelete;
var
Word : string;
Word1 : string[20];
begin
Word1 := 'Free Pascal';
Word := Delete(Word1,6,6);
writeln(Word); {выводится текст 'Free'}
end.
- Функция Insert осуществляет вставку в строку другой строки начиная с некоторой позиции. Вызывая эту функцию, нужно указать следующие параметры: имя строки, в которую будет осуществляться вставка строки; указать вставляемую строку; позицию в строке, с которой будет осуществляться вставка другой строки.
Объявление функции Insert
Insert (source:string; var s:string; index:integer);
Пример использования функции Insert
program DemoFunctionInsert;
var
Word : string;
Word1 : string[20];
begin
Word1 := 'Fr Pascal';
Word := Insert(Word1,’ee’,3);
writeln(Word); {выводится текст 'Free Pascal'}
end.
- Функция Pos осуществляет поиск некоторого фрагмента в строке. Если заданный фрагмент в строке присутствует, то функция возвращает номер позиции, с которой он начинается. Если фрагмент не найден, то функция возвращает нуль.
Объявление функции Pos
Pos (substr, s:string): byte;
Пример использования функции Pos
program DemoFunctionPos;
var
Word : string;
Word1 : string[20];
i : integer;
begin
Word1 := 'Free Pascal';
Word := ‘Pascal’;
i := pos (Word, Word1);
writeln(i); {выводится текст '6'}
end.
2.6. Многомерные массивы
При решении практических задач часто приходится иметь дело с различными таблицами данных, математическим эквивалентом которых служат матрицы. Такой способ организации данных, при котором каждый элемент определяется номером строки и номером столбца, на пересечении которых он расположен, называется двумерным массивом или таблицей.
Объявление двумерного массива в языке Free Pascal:
<имя типа> : array[<тип(ы) индекса(ов)>, <тип(ы) индекса(ов)>] of <тип элемента>;
Для последовательного ввода элементов двумерного массива потребуется два цикла for. Первый цикл будет последовательно менять номер строки, второй цикл будет последовательно перебирать номера столбцов.
Рассмотрим пример ввода двумерного массива с клавиатуры:
var
N, i, j : integer;
A : array [1..15, 1..15] of integer;
begin
write('Введите количество элементов в массиве: ');
readln(N);
for i := 1 to N do
for j := 1 to N do
begin
write('Введите число');
readln(A[i, j]);
end;
Двумерный массив в Free Pascal можно заполнить случайным образом, т.е. использовать функцию random (N), а также присвоить каждому элементу матрицы значение некоторого выражения. Способ заполнения двумерного массива выбирается в зависимости от поставленной задачи
Рассмотрим задачу над двумерными массивами: дана целочисленная квадратная матрица. Найти в каждой строке наибольший элемент и поменять его местами с элементами главной диагонали. Составим краткое словесное описание алгоритма решения задачи:
- Определить размер матрицы. Заполнить матрицу значениями.
- Счетчик цикла присвоить значение 1.Поиск наибольшего значения начинается с первой строки
- В строке матрицы найти наибольший элемент
- Поменять найденный наибольший элемент с элементом главной диагонали.
- Увеличить счетчик цикла на единицу. Если счетчик меньше количества строк матрицы, то повторить шаг 3 и шаг 4.
Ниже представлен листинг программы, решающую поставленную задачу.
program obmen;
var
N, i, j, Max, Ind, Vsp : integer;
A : array [1..15, 1..15] of integer;
begin
write('Введите количество элементов в массиве: ');
readln(N);
for i := 1 to N do
for j := 1 to N do
begin
write('Введите число');
readln(A[i, j]);
end;
for i := 1 to N do
begin
max := A[i, 1];
Ind := 1;
for j := 2 to N do
iF A[I, J] > Max then
begin
Max := A[i, j];
Ind := j
end;
Vsp := A[i, i];
A[i, i] := A[i, Ind];
A[i, Ind] := Vsp;
end;
for i := 1 to N do
begin
writeLn;
for j := 1 to N do
write(A[i, j]);
end;
end.
2.7. Литература
2.7.1. Использованные источники информации
- Грудзинский А.О., Мееров И.Б., Сысоев А.В. Методы программирования. Курс на основе языка Object Pascal.– Нижний Новгород: Изд-во Нижегородского госуниверситета, 2006. – С. 392.
- Кетков Ю.Л., Кетков А.Ю. Свободное программное обеспечение. Free Pascal для студентов и школьников – СПб.: БХВ-Петербург, 2011. – 384 c.
- Грогоно П. Программирование на языке Паскаль.–М.: Наука, 1982. – 382с.
- Епанешников А.М., Епанешников В.А. Turbo Pascal 7.0. М: Стрикс, 1997. – 336c.
- Культин Н.Б. Turbo Pascal в задачах и примерах –СПб.: БХВ-Петербург, 2000. – 256с.
- Немнюгин С.А. Turbo Pascal.–СПб.: Питер, 2000. – 496с.
- Фаронов В.В. Turbo Pascal 7.0. Начальный курс. Учебное пособие.–М.: Нолидж, 1997. – 616с.
- Язык прогррамирование TurboPascal.
2.7.2. Дополнительная литература
2.7.3. Информационные ресурсы сети Интернет
- Free Pascal –advanced open source Pascal compiler for Pascaland Object Pascal.