|
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. Возникает вопрос, что будет, если вызвать снова процедуру выделение памяти для этого же динамического массива?
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 – переменная булевского типа, принимает значение Истина, если искомый элемент будет найден, в противном случае принимает значение Ложь.
Ниже представлена программа решающую поставленную задачу. 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. Поиск минимального, максимального элемента массива. Подсчет суммы всех элементов массиваЛюбая программа, работающая с большими объемами информации, прежде всего, должна решать задачу построения информационной модели предметной области, то есть представления данных. Массивы в этом смысле являются классическим и достаточно удобным средством хранения большого количества однотипных данных. Следующим шагом возникает проблема обработки этих данных: поиск минимального, максимального элемента массива, подсчет суммы всех элементов массива, сортировка элементов массива. Постановка задачи поиска максимального элемента в массиве формулируется следующим образом: в заданной последовательности числе найти максимальное значение. Представим словесное описание алгоритма:
Поиск минимального элемента в массиве осуществляется аналогичным образом. Лишь на втором шаге используется другая операция сравнения «меньше». Ниже представлена программа решающую поставленную задачу. 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-ым элементом массива.
Перейдем к написанию программы выполняющую сортировку элементов массива используя метод выбора. 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-ым элементом массива.
Ниже представлен код программы осуществляющая сортировку массива с помощью метода пузырьком. 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. Метод сортировки включениемЭтот метод похож на метод пузырька. Происходит такое же разбиение массива на отсортированную и не отсортированную части, но перемещение первого элемента остатка на принадлежащее ему место в итоге делается не сравнением двух соседних элементов, а с помощью метода двоичного поиска.
Реализуем программу сортировки элементов массива методом включения. 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(s:string):integer Пример использования функции length. n := length('Pascal'); {n будет равно 6}
Объявление функции 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(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 (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 (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 (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), а также присвоить каждому элементу матрицы значение некоторого выражения. Способ заполнения двумерного массива выбирается в зависимости от поставленной задачи Рассмотрим задачу над двумерными массивами: дана целочисленная квадратная матрица. Найти в каждой строке наибольший элемент и поменять его местами с элементами главной диагонали. Составим краткое словесное описание алгоритма решения задачи:
Ниже представлен листинг программы, решающую поставленную задачу. 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. Использованные источники информации
2.7.2. Дополнительная литература2.7.3. Информационные ресурсы сети Интернет
|
|
© a-urusov2011 |