Массив – однородная совокупность элементов

Самой распространенной структурой, реализованной практически во всех языках программирования, является массив.

Массивы состоят из ограниченного числа компонент, причем все компоненты массива имеют один и тот же тип, называемый базовым. Структура массива всегда однородна. Массив может состоять из элементов типа integer , real или char , либо других однотипных элементов. Из этого, правда, не следует делать вывод, что компоненты массива могут иметь только скалярный тип.

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

Индекс массива

Номер элемента массива называется индексом. Индекс – это значение порядкового типа, определенного, как тип индекса данного массива. Очень часто это целочисленный тип ( integer , word или byte ), но может быть и логический и символьный.

Описание массива в Паскале. В языке Паскаль тип массива задается с использованием специального слова array (англ. – массив), и его объявление в программе выглядит следующим образом:

Type < имя _ типа >= array [ I ] of T;

где I – тип индекса массива, T – тип его элементов.

Можно описывать сразу переменные типа массив, т.е. в разделе описания переменных:

Var a,b: array [ I ] of T;

Обычно тип индекса характеризуется некоторым диапазоном значений любого порядкового типа : I 1 .. I n . Например, индексы могут изменяться в диапазоне 1..20 или ‘ a ’..’ n ’.

Ввод массива Паскаля

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

Пример фрагмента программы ввода массива Паскаля

Var    A : array [1..10] of integer ;    I : byte ; {переменная I вводится как индекс массива} Begin    For i:=1 to 10 do       Readln (a[i]); { ввод i- го элемента производится с клавиатуры }

Рассмотрим теперь случай, когда массив Паскаля заполняется автоматически случайными числами, для этого будем использовать функцию random ( N ).

Пример фрагмента программы заполнения массива Паскаля случайными числами

Var    A: array [1..10] of integer;    I : byte ; {переменная I вводится как индекс массива} Begin    For i :=1 to 10 do       A [ i ]:= random (10); { i -му элементу массива присваивается «случайное» целое число в диапазоне от 0 до 10}

Вывод массива Паскаля

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

Пример фрагмента программы вывода массива Паскаля

Var    A: array [1..10] of integer;    I : byte ; {переменная I вводится как индекс массива} Begin    For i :=1 to 10 do       Write ( a [ i ],’ ‘); {вывод массива осуществляется в строку, после каждого элемента печатается пробел}

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

50. Вычисление суммы элементов массива

Вычисление суммы и количества элементов массива с заданными свойствами

Еще одна задача — посчитать сумму элементов, которые удовлетворяют какому-то условию. Наверное, вы уже поняли общий принцип: перебираем все элементы массива (цикл for) и проверяем для каждого элемента выполнение условия (оператор if). Если условие выполнено, добавим элемент к сумме (S := S+A[i]).

Пример 8.5. Вычисление суммы положительных элементов массива

program PositivSumm; const N=10; . type Mas=array [1..N] of integer; var a: Mas; i: integer; { Счетчик цикла} S: integer; { Копилка - переменная для суммирования , положительных элементов } begin { Заполним массив случайными числами в диапазоне -100. .+100 } randomize; for i:=1 to N do begin a[i]:=-100+random(201); write(a[i]:5) end; writeln; { Присвоим переменным начальные значения } S:=0; { Переменная S - аккумулятор. Она будет накапливать фшу всех положительных элементов. Нужно присвоить ей такое начальное значение, чтобы оно не повлияло на результат суммирования. Таким числом является ноль } for i:=l to N do { Перебираем все элементы массива } if A[i]>0 then { Проверяем каждый элемент на положительность } S:=S+A[i]; { Если элемент положительный, добавляем значение элемента к аккумулятору } { Выводим результат на экран: } writeln('Сумма положительных элементов=',S); readln end.

51. Вычисление произведения элементов массива

Тоже что и п.50

52. Подпрограммы

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

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

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

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

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

При работе с подпрограммами важными являются понятия формальных и фактических параметров. Формальные параметры — это идентификаторы входных данных для подпрограммы. Если формальные параметры получают конкретные значения, то они называются фактическими. Формальные параметры могут получить конкретные значения только в той программе, где производится обращение к данному модулю-подпрограмме. Тип и порядок записи фактических параметров должны быть такими же, как и формальных параметров. В противном случае результат работы программы будет непредсказуемым. Из этого следует, что фактические параметры используются при обращении к подпрограмме из основной, а формальные параметры — только в самом модуле.

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

При составлении подпрограмм с параметрами надо соблюдать следующие правила:

1) каждая подпрограмма имеет свое имя и список формальных параметров;

2) процедура из основной программы вызывается командой вызова, которая по форме ничем не отличается от вызова команды исполнителя. Результат присваивается одной или нескольким переменным, которые находятся в списке формальных параметров. Но результатом могут быть, конечно, не только значения переменных, но какое либо действие, выполненное ЭВМ.

Вызов процедуры осуществляется следующим образом:

<Идентификатор (имя) процедуры>(<список фактических параметров>);

Например,

Nod(Abs(E), F, G);

По способу передачи фактических значений в подпрограмму в Turbo Pascal 7.0 выделяют параметры-переменные, параметры-значения, параметры-константы и массивы открытого типа, строки открытого типа, параметры-процедуры, параметры-функции (подробности — в литературе).

Функция (в отличие от процедуры) всегда возвращает единственное значение.

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

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

53. Рекурсия

Рекурсия — это такой способ организации вспомогательного алгоритма (подпрограммы), при котором эта подпрограмма (процедура или функция) в ходе выполнения ее операторов обращается сама к себе. Вообще, рекурсивным называется любой объект, который частично определяется через себя.

Например, приведенное ниже определение двоичного кода является рекурсивным:

<двоичный код> ::= <двоичная цифра> | <двоичный код><двоичная цифра>

<двоичная цифра> ::= 0 | 1

Здесь для описания понятия были использованы, так называемые, металингвистический формулы Бэкуса-Наура (язык БНФ); знак "::=" обозначает "по определению есть", знак "|" — "или".

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

Приведём другие примеры рекурсивных определений.

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

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

54. Строковой тип. Редактирование строк при помощи встроенных подпрограмм

Познакомимся с типом данных, который относится к числу структурированных. Это строковый тип данных (строка). Строка — это последовательность символов. Каждый символ занимает 1 байт памяти (код ASCII). Количество символов в строке называется ее длиной. Длина строки может находиться в диапазоне от 0 до 255. Строковые величины могут быть константами и переменными. Особенностью строки в Turbo Pascal является то, что с ней можно работать как с массивом символов, с одной стороны, и как с единым объектом, — с другой. За счет этого обработка строк достаточно гибка и удобна. Строковая константа есть последовательность символов, заключенная в апострофы. Например: 'это строковая константа', ‘272’. Строковая переменная описывается в разделе описания переменных следующим образом:

Var <идентификатор> : string[<максимальная длина строки>];

Например:

Var Name : string[20];

Параметр длины может и не указываться в описании. В таком случае подразумевается, что он равен максимальной величине — 255. Например: Var slovo : string.

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

Символы внутри строки индексируются (нумеруются) от единицы. Каждый отдельный символ идентифицируется именем строки с индексом, заключенным в квадратные скобки. Например: N[5], S[i], slovo[k+l]. Индекс может быть положительной константой, переменной, выражением целого типа. Значение индекса не должно выходить за границы описания.

Тип string и стандартный тип char совместимы. Строки и символы могут употребляться в одних и тех же выражениях.

Строковые выражения строятся из строковых констант, переменных, функций и знаков операций. Над строковыми данными допустимы операции сцепления и операции отношения.

Операция сцепления (конкатенации) (+) применяется для соединения нескольких строк в одну результирующую строку. Сцеплять можно как строковые константы, так и переменные.

Пример: 'Мама ' + 'мыла ' + 'раму'. В результате получится строка: 'Мама мыла раму'. Длина результирующей строки не должна превышать 255.

Операции отношения: =, <, >, <=, >=, <>. Позволяют произвести сравнение двух строк, в результате чего получается логическое значение (true или false). Операция отношения имеет приоритет более низкий, чем операция сцепления. Сравнение строк производится слева направо до первого несовпадающего символа, и та строка считается больше, в которой первый несовпадающий символ имеет больший номер в таблице символьной кодировки. Если строки имеют различную длину, но в общей части символы совпадают, считается, что более короткая строка меньше, чем более длинная. Строки равны, если они полностью совпадают по длине и содержат одни и те же символы.

Пример:

Выражение	Результат
‘True1’<’True2’	True
‘Mother’>’MOTHER’	True
‘Мама ‘ <> ‘Мама’	True
‘Cat’=’Cat’	True

Функция Copy(S, Pozition, N) выделяет из строки S подстроку длиной N символов, начиная с позиции Pozition. Здесь N и Pozition — целочисленные выражения.

Пример:

Значение S	Выражение	Результат
‘Мама мыла раму’	Copy(S, 6, 4)	‘мыла’
‘Маша ела кашу’	Copy(S, 1, 8)	‘Маша ела’

Функция Concat(S1, S2, …, SN) выполняет сцепление (конкатенацию) строк S1, S2, …, SN в одну строку.

Пример:

Выражение	Результат
Concat('Маша ', 'ела ', 'кашу')	'Маша ела кашу'

Функция Length(S) — определяет текущую длину строки S. Результат — значение целого типа.

Пример:

Значение S	Выражение	Результат
'test-5'	Length(S)	6
'(A+B)*C'	Length(S)	7

Функция Pos(S1, S2) — обнаруживает первое появление в строке S2 подстроки S1. Результат — целое число, равное номеру позиции, где находится первый символ подстроки S1. Если в S2 подстроки S1 не обнаружено, то результат равен 0.

Пример:

Значение S2	Выражение	Результат
'abcdef'	Pos('cd', S2)	3
'abcdcdef'	Pos('cd', S2)	3
'abcdef'	Pos('k', S2)	0

Процедура Delete(S, Poz, N) — удаление N символов из строки S, начиная с позиции Poz.

Пример:

Исходное значение S	Оператор	Конечное значение S
'abcdefg'	Delete(S, 3, 2)	'abefg'
'abcdefg'	Delete(S, 2, 6)	'a'

В результате выполнения процедуры уменьшается текущая длина строки в переменной S.

Процедура Insert(S1, S2, Poz) — вставка строки S1 в строку S2, начиная с позиции Poz.

Пример:

Исходное значение S2	Оператор	Конечное значение S2
'ЭВМ РС'	Insert('IBM-', S2, 5)	'ЭВМ IBM-PC'
'Рис. 2'	Insert('N', S2, 6)	'Рис. N 2'

55. Множественный тип. Представление, действия

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

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

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

Такие ограничения связаны с формой представления множества в языке и объясняются тем, что функция Ord для элементов используемого базового типа должна быть в пределах от 0 до 255.

Множество имеет зарезервированное слово set of и вводится следующим описанием

Type   < имя типа > = set of < имя базового типа >; Var   < идентификатор,... >:< имя типа >;

Рассмотрите примеры описаний множеств:

Type   SetByte = set of byte; {множество 1, определённое над типом byte}   SetChisla = set of 10 .. 20; {множество 2, определённое в диапазоне от 10 до 20}   Symbol = set of char; {множество, определённое на множестве символов}   Month = (January, February, March, April, May, June, July, August, September, October, November, December);   Season = set of Month; {тип множества, определённый на базе перечислимого типа Month} Var   Letter, Digits, Sign : Symbol; {множествa, определённые над символьным типом}   Winter, Spring, Summer, Autumn, Vacation, WarmSeason : Season;   Index : SetChisla=[12, 15, 17];   Operation : set of (Plus, Minus, Mult, Divid);   Param : set of 0..9=[0, 2, 4, 6, 8];

Для переменных типа множества в памяти отводится по 1 биту под каждое возможное значение базового типа. Так, под переменные Letter, Digits, Sign будет отведено по 256/8=32 байта. Для переменной Winter, базовый тип которой (Month) имеет 12 элементов, необходимо 2 байта, причем второй используется только наполовину. Если множество содержит какой-то элемент, то связанный с ним бит имеет значение 1, если нет - 0.

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

Sign:=['+', '-']; Spring:=[March, April, May]; b:=[ 'k', 'l', 'd' ]

либо определение через диапазон. В этом случае в множество включены все элементы диапазона.

Digits:=['0'..'9']; WarmSeason := [May .. September];

Обратите внимание, что в определении множества Digits использованы символы в таблице ASCII-кодов, а не целые числа.

Обе формы конструирования могут сочетаться:

Vacation:=[January, February, June .. August];

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

{постоянное множество допустимых символов} Const   YesOrNo = ['Y', 'y', 'N', 'n'];   {множества - типизированные константы} Const   Digits : set of char=['0'..'9'];   DigitsAndLetter : set of char=['0'..'9', 'a'..'z', 'A'..'Z'];   {применение операции "+" для объявления множества-константы} Const   Yes = ['Y', 'y'];   No = ['N', 'n'];   YesOrNo = Yes+No;

56. Записи. Записи с вариантами

Запись — структурированный тип данных. Записи являются неоднородными неупорядоченными структурами с прямым доступом к компонентам. Компоненты записи называют полями записи.

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

Например, информация о рекордах по бегу у мужчин для открытых стадионов может содержать следующие атрибуты

рекордсмен

страна

статус соревнований (Олимпиада, чемпионат мира)

длина дистанции

год рекорда

время

Структурная диаграмма для записи

Запись может быть объявлена в разделе type:

идентификатор типа = Record

поле1: тип;

поле2: тип;

…

полеN: тип

end;

Например,

type beg = record

fam: string[25];

srtana: string[20];

status: boolean; {Олимпиада - true; чемпионат мира - false}

dlina: longint;

god: 1900..2009;

vr: string[15];

end;

Var a: beg;

К каждому элементу записи можно обратиться, используя составное имя, которое имеет следующую структуру:

<имя переменной>.<имя поля>

Например,

a.fam; a.dlina и т.п.

Если, например, требуется полю "status" присвоить значение «true», то это делается так:

a.status := true;

Поля записи могут иметь любой тип, кроме файла, в частности, сами могут быть записями.

Например,

type beg1 = record

fam: string[25];

srtana: string[20];

status: boolean; {Олимпиада - true; чемпионат мира - false}

dlina: longint;

god: 1900..2009;

vr: record min: longint;

sec: real

end

end;

Var a: beg1;

Поля такой записи, находящиеся на третьем уровне, идентифицируются тройным составным именем. Например,

a.vr.min

a.vr.sec

В программе могут использоваться массивы записей.

Любая обработка записей, в том числе ввод и вывод, производится поэлементно.

Например,

var b: array[1..200] of beg1;

...

write('Число рекордсменов? '); readln(n);

for i:=1 to n do

with b[i] do

begin

write('Фамилия спортсмена? '); readln(fam);

write('Гражданин какой страны спортсмен? '); readln(strana);

write('Статус соревнования? '); readln(status);

write('Длина дистанции? '); readln(dlina);

write('Год проведения соревнования? '); readln(god);

write('Время, за которое спортсмен пробежал дистанцию (мин, сек)? '); readln(vr.min, vr.sec);

end;

...

В примере был использован оператор присоединения, который имеет следующий вид:

with <переменная типа запись> do <оператор>;

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

Объём памяти, занимаемый записью, определяется суммарным объёмом, занимаемым её полями:

type beg1 = record

fam: string[25]; {26 байт}

srtana: string[20]; {21 байт}

status: boolean; {1 байт}

dlina: longint; {4 байта}

god: 1900..2009; {2 байта}

vr: record min: longint; {4 байта}

sec: real {6 байт}

end

end;

Всего получаем: 26+21+1+4+2+4+6=65 байт

Массив, описанный выше, занимает 65 байт × 200 элементов = 13000 байт оперативной памяти.