Способы описания синтаксиса языка программирования

Алгоритмы

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

Свойства алгоритма

1. Дискретность (алгоритм состоит из отдельных действий, следующих одно за другим).
2. Элементарность действий (шаги не могут подразделяться на более мелкие шаги).
3. Определенность действий (каждый шаг имеет ясную и однозначную трактовку).
4. Конечность (завершимость).
5. Результативность (после завершения алгоритма известно, что считать результатом).
6. Массовость (алгоритм применим для множества наборов исходных данных).

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

Пример. Найти max из чисел x, y, z.

Алгоритм 1. (Словесное описание)

Если x>=y и x>=z, то положить max:=x и завершить алгоритм
Если y>=x и y>=z, то положить max:=y и завершить алгоритм
Если z>=x и z>=y, то положить max:=z и завершить алгоритм

Алгоритм 2. (Описание на псевдокоде)

max:=x
Если y>max то max:=y
Если z>max то max:=z

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

Способы описания алгоритмов

1. Словесный.

2. Псевдокод.

3. C помощью блок-схем.

Пример. (алгоритм 2, представленный блок-схемой)

Альтернативная современная нотация - диаграмма деятельности (Activity Diagram) в языке UML (Universal Modelling Language).

4. C помощью языка программирования.

Язык программирования

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

Синтаксис ЯП определяет правила записи основных конструкций ЯП и устанавливает, какие фрагменты текста программы следует считать неделимыми (например,:=, <=, for, 3.14, 'abc'). Такие фрагменты называют лексемами или терминальными символами (терминалами).

Семантика ЯП определяет смысловое значение синтаксических конструкций.

Множество всех лексем образует словарь языка.

Способы описания синтаксиса языка программирования

При описании синтаксиса используются БНФ, РБНФ (разработаны в 1960 году для описания Алгола-60 Джоном Бэкусом и Петером Науром) и синтаксические диаграммы (разработаны Н. Виртом).

1. БНФ (Бэкуса-Наура форма)

Примеры.

условный оператор::= if логическое условие then оператор
| if логическое условие then оператор1 else оператор2

цифра::= 0 | 1 | 2 |... | 9

имя::= буква | имя буква | имя цифра

В формах Бэкуса-Наура, помимо терминальных, присутствуют так называемые нетерминальные символы или нетерминалы (будем записывать нетерминалы наклонным шрифтом Arial, а терминалы - шрифтом Courier), а также значки::= (есть по определению) и | (или). Нетерминалы определяются через терминалы и другие нетерминалы.

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

РБНФ (Расширенная БНФ)

Помимо значков::= и |, используются значки:

[ ] - необязательная часть (0 или 1 повторение)

{ } - 0 или более повторений

Примеры.

условный оператор::= if логическое выражение then оператор [ else оператор ]

вызов процедуры::= имя [(параметр {, параметр })]

список::= элемент [, список ]

Синтаксическая диаграмма

Примеры.

Архитектура и принцип работы компьютера

Принцип работы компьютера cформулирован Джоном фон Нейманом в 1946 году и используется в современных компьютерах с небольшими изменениями.

Язык программирования Паскаль

Комментарии в программе

{ } и (* *) – могут быть вложенными

// – до конца строки.

Комментарии игнорируются компилятором и предназначены для пояснения текста программы.

Общая структура программы

program имя; // заголовок программы (не обязателен)
раздел подключения внешних модулей // uses...
раздел описаний
begin
операторы
end.

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

Правила записи программ

1. Большие и маленькие буквы не различаются.
2. Операторы разделяются символом ";" (точка с запятой). После последнего оператора тоже может ставиться точка с запятой; в этом случае считается, что за этим оператором стоит пустой оператор.
3. Между лексемами может содержаться произвольное количество пробелов, символов перехода на новую строку, знаков TAB.

Лексемы языка Pascal

1) Специальные символы

знаки операций::= >= =
ограничители:;, (
зарезервированные слова: begin end var

2) Идентификаторы (используются в качестве имен объектов программы).

Определение. Идентификатор - последовательность латинских букв или цифр, начинающаяся с буквы. К буквам также относят символ _ (подчеркивания).

_a1 - идентификатор
3dnews - не идентификатор

3) Константные значения

3.14
1E-12
'Hello'

4) Комментарии.

Раздел описаний

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

Раздел описания переменных

var i,j: integer;
s: string;
b: boolean;
r1,r2: real;
c: char;

Раздел описания типов

type int = integer;
IArr = array [1..100] of real;

Оператор присваивания

Оператор присваивания имеет вид:

имя переменной:= выражение

Пример 1. Вычислить x¹⁶.

x:=x*x; // x^2
x:=x*x; // x^4
x:=x*x; // x^8
x:=x*x; // x^16

Пример 2. Вычислить x¹⁵=(x⁵)³.

y:=x*x; // x^2
z:=y*x; // x^3
a:=y*z; // x^5
a:=a*a*a; // x^15

Присваивание переменной некоторого начального значения называется инициализацией этой переменной.

Если переменной можно присвоить выражение, то говорят, что они совместимы по присваиванию. Переменная и выражение совместимы по присваиванию:

• если они имеют один тип;
• если переменная и выражение имеют целый тип (например, выражение имеет тип byte, а переменная - тип integer или наоборот);
• если выражение имеет целый, а переменная - вещественный тип;
• если выражение имеет символьный, а переменная - строковый тип.

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

Пример.

var i: integer;
...
i:=2.0; // неверно!

Для преобразования вещественного в целое следует использовать функции round и trunc.

i:=round(2.0);
i:=trunc(2.0);

Операторы ввода/вывода

Оператор вызова процедуры ввода имеет одну из следующих форм:

read(список переменных);
readln(список переменных);
readln;

Оператор вызова процедуры вывода имеет одну из следующих форм:

write(список выражений);
writeln(список выражений);
writeln;

Для перехода на новую строку в процессе вывода можно использовать следующий прием:

const newline = #10;
...
writeln(x, newline, y);

или

writeln('Hello'+newline+'world');

Форматы вывода

Для любых типов:

write(x:а); // а - ширина поля вывода

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

Для вещественного типа:

write(x:а:b); // a - ширина поля вывода, b - количество цифр в дробной части

Вещественные числа в этом формате выводятся в виде с фиксированной точкой.

Неправильный формат вывода игнорируется. Например, если x=14.457, то после

write(x:0:2)

будет выведено 14.46.

Выражения и операции

Выражения

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

Каждое выражение имеет тип, зависящий от типов входящих в него операндов. Выражение называют арифметическим, если его значением является число. Выражение называют логическим, если его значение имеет логический тип.

Логическое выражение всегда имеет тип boolean.

Тип арифметического выражения определяется типом операнда "старшего" типа: если в выражении есть хотя бы один операнд типа real, то выражение имеет тип real, если нет операндов типа real, но есть операнды типа integer, то выражение имеет тип integer. Исключение составляет операция деления: результатом деления целого на целое является вещественное.

Не все типы совместимы в выражении: к примеру, нельзя сложить целое и строку, нельзя из строки вычесть символ.

При вычислениях выражений со смешанными типами также происходит неявное преобразование типов. Например, если i имеет тип integer, а bt - тип byte, то при вычислении выражения i+bt происходит вначале преобразование значения bt к "старшему" типу integer и только после этого выполняется операция сложения.

Операции

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

Таблица приоритетов операций языка Pascal

1. +&nbsp- (унарные)
2. * / div mod shl shr and
3. + -(бинарные) or xor
4. < > <= >= = <> in

Примеры.

2-1+3=(2-1)+3
4/2*2=(4/2)*2
4/2/2=(4/2)/2
1*2+3*4 - операции умножения вычисляются в непредсказуемом порядке.

Логические операции

Простые: x>0 или 2*2=4

Составные: состоят из простых + логические операции (and, or, not, xor)

(x>=3) and (x<=5)
(x<3) or (x>5) = not ((x>=3) or (x<=5))

Таблица истинности

A	B	A or B	A and B	A xor B	not A

Пример. A находится между B и С.

или

Решение.

(A>B) and (A<C) or (A>C) and (A<B)

Пример. Написать условие, при котором точка с координатами (х, у) лежит внутри, вне, на границе прямоугольника с вершинами (x1,y1) и (x2,y2) и сторонами, параллельными осям координат.

var Inside, Outside, OnTheBoundary: boolean;
...
Inside:=(x>x1) and (x<x2) and (y>y1) and (y<y2);
Outside:=(x<x1) or (x>x2) or (y<y1) or (y>y2);
OnTheBoundary:= not Inside and not Outside;

Стандартные функции

abs(x)	|x|
sqr(x)	х^2
sqrt(x)	корень квадратный из х
ln(x)	ln x
exp(x)	е^х
sin(x)	sin x
cos(x)	cos x
arctan(x)	arctan x
int(x)	целая часть х (вещественный результат)
trunc(x)	целая часть х (целый результат)
frac(x)	дробная часть х (вещественный результат)
round(x)	округление вещественного х (целый результат)
Odd(i)	True, если i - нечетно, False в противном случае
sizeof(n)	Размер значения выражения n в байтах. В качестве n может также использоваться имя типа
Pi	возвращает число "пи" = 3.141592...

Пример. sqr(x+y-1)

Стандартные функции в Dephi

Требуется подключение модуля Math: uses Math;

power(x,y)	x^у
arccos(x)
arcsin(x)
sec(x)
cosec(x)
tan(x)
DivMod(x,y,d,m)	d:=x div y; m:=x mod y;
InRange(x,min,max)	min<=x<=max
Hypot(a,b)	гипотенуза треугольника с катетами a, b
log10(x)
logN(N,x)
max(x,y)
min(x,y)

В модуле Math определены также константы

const
MaxDouble = 1.7E308;
MinDouble = 5E-324;

Явление переполнения

Пример.

var x: real;
begin
x:=MaxDouble;
x:=x*2; // ошибка времени выполнения

Для избежания ошибки переполнения можно воспользоваться директивами процессора {$Q-}, {$Q+}:

var i: integer;
begin
i:=MaxInt;
{$Q-} // отключение контроля за переполнением
i:=i+1;
{$Q+} // включение контроля за переполнением

Условный оператор

if логическое выражение then оператор1 [ else оператор2 ]

Семантика оператора if задается следующей блок-схемой:

Пример. Hайти min из a, b.

if b>a then
min:=a
else
min:=b;

Пример. Упорядочить значения в a, b по возрастанию.

if a>b then
поменять значения местами

Составной оператор

begin
операторы
end

Необходимость составного оператора: составной оператор объединяет несколько операторов в один:

Пример.

if a>b then
begin
v:=a;
a:=b;
b:=v;
end;

Пример.

case Month of
4,6,9,11: DayInMonth:=30;
2: DayInMonth:=28;
else DayInMonth:=31;
end.

Циклы while, repeat и for

Оператор цикла с предусловием (цикл ПОКА)

while B do
оператор

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

Семантика оператора while задается следующей блок-схемой:

Сравнение while и repeat

• Тело repeat выполняется по крайней мере 1 раз
• Условия продолжения цикла в while и repeat противоположны
• В repeat можно записывать несколько операторов без использования begin / end

Оператор цикла с параметром

for x:=x1 to x2 do
оператор

или

for x:=x2 downto x1 do
оператор

где переменная x называется параметром цикла, x1 и x2 – выражения совместимого с x типа.

Важно! Выражения x1 и x2 вычисляются один раз до цикла.

Замечания.

1. Значение параметра цикла после выполнения цикла считается неопределенным.
2. В теле цикла нельзя изменять параметр цикла. Например:

for i:=1 to n do
i:=i-1; // ошибка!

for i:=1 to n do
read(i); // ошибка!

for i:=1 to n do
for i:=1 to m do // ошибка!

Определение. Инвариант цикла – это предикат, который истинен перед выполнением цикла и после каждой его итерации. Например, если находится сумма чисел, то инвариант цикла – сумма уже введенных чисел. Если находится минимум, то инвариант цикла: в min – минимальные из уже введенных. Инвариант цикла служит для доказательства правильности алгоритма.

Зацикливание

repeat
write(i);
until False;

или

while True do
write(i);

Примеры использования циклов

Пример 1. Сумма n чисел.

s:=0;
for i:=1 to n do
s:=s+xi

Пример 2. Произведение n чисел.

p:=1;
for i:=1 to n do
p:=p*xi

Пример 3. n!!=n*(n-2)*(n-4)*...*2 (или 1)

p:=1;
x:=n;
while x>=2 do
begin
p:=p*x;
x:=x-2;
end;

Пример 4. Сколько нечетных среди 10 введенных.

c:=0;
for i:=1 to n do
begin
read(x);
if x mod 2 <> 0 then
c:=c+1;
// if Odd(x) then Inc(c); // вариант
end;

Пример 5. Защита от неверного ввода.

repeat
write('Введите x (>0): ');
readln(x);
if x<=0 then
writeln('Неверный ввод');
until x>0;

Пример 6. Табулирование функции f(x) на отрезке [a,b] в точках, разбивающих [a,b] на N частей.

assert(N>0);
h:=(b-a)/N;
x:=a;
for i:=0 to N do
begin
writeln(x:5:2, f(x):10:4);
x:=x+h;
end;

Пример 7. Вывод 10 первых степеней двойки.

x:=10;
for i:=1 to 10 do
begin
writeln(i:2,x:5);
x:=x*2;
end;

Пример 8. Вывод всех двузначных чисел, кратных 5.

x:=1;
while x<100 do
begin
write(x:3);
x:=x+5;
end;

Пример 9. Вывести n первых чисел Фибоначчи. Числа Фибоначчи определяются следующим образом:

a:=1;
b:=1;
write(1,' ',1,' ');
for i:=3 to n do
begin
c:=a+b;
write(c,' ');
a:=b;
b:=c;
end;

Пример 10. Найти сумму цифр целого положительного числа.

read(m);
S:=0;
while m>0 do
begin
S:=S + m mod 10;
m:=m div 10;
end;

Пример 11. Найти НОД (А,В), где А,В - целые положительные.

Алгоритм Евклида: НОД (А,В) = НОД (В, А mod B); НОД (А,0)=А

read(A,B);
repeat
C:=A mod B;
A:=B;
B:=C
until C=0;
NOD:=A;

Замечание. Доказательство того, что цикл завершится: С уменьшается на каждом шаге, оставаясь >=0.

Пример 12. Найти max из N введенных чисел.

Алгоритм 1. max:= первое введенное

read(x);
max:=x;
// Инвариант I: max = максимальное из всех введенных
for i:=2 to N do
begin
read(x);
if max:=x then
max:=x
// I выполняется
end;

Алгоритм 2. max:= самое маленькое число (-MaxInt или -MaxDouble)

for i:=1 to N do
...

Пример 13. Разложение числа на простые множители.

Алгоритм на псевдокоде

цикл
если х делится на i, то
{
вывод i
x:=x/i
}
иначе увеличить i на 1
до х=1

Алгоритм на Паскале

read(x);
assert(x>1);
i:=2;
repeat
if x mod i = 0 then
begin
write(i,' ');
x:=x div i;
end
else Inc(i);
until x=1;

Пример 14. Даны a₀,..., a_n, x Вычислить значение многочлена f(x)=a₀xⁿ+a₁x^n-1+...+a_n в точке x.

Схема Горнера: f(x)=(...((a₀x+a₁)x+a₂)x+a₃...)x+a_n

read(x);
S:=0;
for i:=0 to n do
begin
read(a);
S:=S*x+a;
end;

n+1 операций "+" и n+1 операций "* "

Примеры на суммирование рядов

Если x_i = f(x_i-1), то

x:=x0;
S:=x;
for i:=2 to n do
begin
x:=f(x);
S:=S+x
end;

Пример 15. Вычислить сумму

x:=1;
S:=x;
for i:=2 to n do
begin
x:=x*y/i;
S:=S+x;
end;

Если существует предел суммы

Пример 16. Знакопеременный ряд

x_i = x_i-1 + 0.1
z_i=(-1)ⁱ
z_i=-z_i-1

z:=1;
s:=0;
x:=1; // эта часть может меняться
for i:=0 to n do
begin
s:=s+z*x;
x:=x+0.1; // эта часть может меняться
z:=-z;
end;

Пример 17. Вычислить сумму

x_i=x_i-1*y*(i-1)/i - неэффективно.

Лучше p_i=yⁱ, p_i=p_i-1*y

Код программы.

for i:=0 to n do
begin
p:=p*y;
s:=s+p/i;
end;

Пример 18. Метод половинного деления

Задача. Дана непрерывная на [a,b] функция f(x),имеющая на [a,b] ровно один корень (т.е. f(a)*f(b)<=0). Найти его с точностью eps.

Алгоритм.

fa:=f(a);
fb:=f(b);
while b-a>eps do
begin x:=(b+a)/2;
fx:=f(x);
if fa*fx<=0 then // корень расположен на (a,x]
begin
b:=x;
fb:=fx
end
else
begin
a:=x;
fa:=fx
end;
end;
writeln('корень=', (b+a)/2);

Процедуры break и continue

Задача. Есть ли среди введенных 10 чисел число К?

Решение. Способ 1.

flag:=false;
for i:=1 to 10 do
begin
read(x);
if x=k then
flag:=True
end;
write(flag);

Недостаток: после того как flag получит значение True, он уже не поменяется, поэтому дальнейшее выполнение цикла бесполезно.

Для решения подобных проблем используются специальные процедуры, меняющие порядок выполнения операторов: break и continue.

Вызов процедуры break завершает цикл досрочно.

Вызов процедуры continue досрочно завершает текущую итерацию цикла.

Процедуры break и continue могут вызываться только в цикле.

Мнение автора. Позволю себе заметить, что решение назвать break и continue процедурами мне не нравится. В C, Java это - операторы, как и goto. И правильно: обычная процедура не может менять порядок выполнения операторов: это удел синтаксических конструкций (операторов).

Решение. Способ 2.

flag:=false;
for i:=1 to 10 do
begin
read(x);
if x=k then
begin
flag:=True;
break;
end;
end;
write(flag);

Приведем другие примеры использования процедур break и continue.

Пример 1. Является ли число N простым?

IsSimple:=True;
for i:=2 to round(sqrt(N)) do
if N mod i=0 then
begin
IsSimple:=false;
break;
end;

Пример 2. Вводятся ненулевые числа, конец ввода - 0. Найти сумму и произведение положительных.

S:=0;
P:=1;
repeat
read(x);
if x=0 then break;
if x<0 then continue;
S:=S+x;
P:=P*x;
until False;

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

while B do
begin
S1
if B1 then break
S2
end;

Так выглядит программа без break:

B1:=false;
while B and not B1 do
begin
S1;
if not B1 then
S2
end;

Вложенные циклы

Цикл, вызываемый в другом цикле, называется вложенным.

Задача. Вывести таблицу значений А^k, где А=2..10.

Метод окаймления

"Заморозим" А и составим алгоритм при фиксированном А.

for A:=2 to 10 do
begin
p:=1;
for i:=1 to k do
p:=p*A;
writeln(p);
end.

Разморозим А и окаймим данный участок цикла по А от 2 до 10.

Задача. Вывести все простые числа от 100 до 999.

Переборные задачи

Задача. Вывести все тройки целых положительных a, b, c <100: a²+b²=c²
Решение 1. (В лоб)

for a:=1 to 99 do
for b:=1 to 99 do
for c:=1 to 99 do
if a*a+b*b=c*c then
writeln(a:3;b:3;c:3)

Решение 1а.

for a:=1 to 99 do
for b:=a+1 to 99 do
for c:=b+1 to 99 do
if a*a+b*b=c*c tnen
writeln(a:3;b:3;c:3)

Решение 1б.

for a:=1 to 99 do
for b:=a+1 to 99 do
c:=round(sqrt(a*a+b*b));
if a*a+b*b=c*c tnen
writeln(a:3;b:3;c:3)

Но! Нельзя заниматься преждевременной оптимизацией!

Процедуры

Пример. Составить процедуру вычисления среднего арифметического и среднего геометрического А и В. С ее помощью найти среднее арифметическое и среднее геометрическое пар A,B; A,C; B,C.

procedure Mean(A,B: real; var MA,MG: real);
// A,B-входные параметры
// MA,MG-выходные параметры
begin
assert(A>0); // предусловия процедуры
assert(B>0);
MA:=(A+B)/2;
MG:=sqrt(A*B);
end;

var A,B,C: real;
MA1,MA2,MA3,MG1,MG2,MG3: real;

begin
readln(A,B,C);
Mean(A,B,MA1,MG1);
Mean(A,C,MA2,MG2);
Mean(B,C,MA3,MG3);
writeln(MA1,MG1);
writeln(MA2,MG2);
writeln(MA3,MG3);
end.

Оператор вызова процедуры

имя [(список фактических параметров)]

Количество и типы фактических параметров при вызове процедуры должны соответствовать количеству и типам формальных параметров.

Функции

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

Пример. Функция

function sign(x: real): integer;
begin
if x<0 then
sign:=-1
else if x>0 then
sign:=1
else sign:=0
end;

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

var s,a: real;
begin
s:=sign(-3);
writeln(s);
read(a);
writeln(sign(a)+sign(1));
end.

Для сравнения реализуем вычисление sign в виде процедуры.

procedure CalcSign(x: real; var sign: integer);
begin
if x<0 then
sign:=-1
else if x>0 then
sign:=1
else sign:=0
end;

var a: real;
s,s1,s2: integer;

begin
Calcsign(-3,s);
writeln(3);
read(a);
Calcsign(a,s1);
Calcsign(1,s2);
writeln(s1+s2);
end.

Переменная Result

В Delphi и FreePascal неявно определена переменная Result, присваивание которой равносильно и хранит результат функции.

function Sum(n: integer): integer;
var i: integer;
begin
Result:=0;
for i:=1 to n do
Result:=Result+i // Inc(Result,i)
end;

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

Способы передачи параметров

Перегрузка имен подпрограмм

Перегрузка имен подпрограмм имеется в Delphi, FreePascal и отсутствует в Turbo Pascal.

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

procedure swap(var a,b: integer); overload;
...
procedure swap(var a,b: real); overload;
...

Это явление называется полиморфизмом.

Полиморфизм – использование одного имени (одного знака операции) для выполнения родственных действий.

Примеры.

writeln(a,b) – полиморфная процедура: параметры различных типов.

a+b – операция «+» используется для различных типов.

Тонкости перегрузки

Пример 1.

procedure A(i: integer); overload;
procedure A(i: real); overload;

var b: byte;
...
A(b); // ошибка - неоднозначность при вызове процедуры

Пример 2.

function f: integer; overload;
function f: real; overload;
...
r:=f; // ошибка - неоднозначность при вызове функции

Правило: тип возвращаемого значения не участвует в разрешении перегрузки.

Параметры по умолчанию

Параметры по умолчанию имеются в Delphi, FreePascal и отсутствуют в Turbo Pascal.

procedure DoOperation(a,b: real; var res: real; op: char=’+’);
begin
case op of
’+’: res:=a+b;
’-’: res:=a-b;
...
end;
end.
...
DoOperation(2,3,res);
DoOperation(2,3,res,'*');

Правило. Параметры по умолчанию всегда должны идти последними.

Предварительное объявление подпрограмм

procedure p(i: integer); forward; // Предварительное объявление. p будет определена далее

procedure q;
begin
p(3); // можно вызывать
end;

procedure p(i: integer);
begin
...
end;

Методы разработки программ

Шаг.

x:=2;
while x<1000 do
begin
if IsPrime(x) then
write(x,’ ’);
x:=x+2
end;

2 шаг. Детализируем IsPrime.

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

Метод эффективен, когда задача четко поставлена и имеется четкий алгоритм ее решения.

Модули

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

1. Объединить группу взаимосвязанных подпрограмм в единое целое, отделив от остального кода.
2. Разбить большой код на относительно независимые части.
3. Поставлять пользователям библиотеки подпрограмм без исходного текста

Структура модуля

Модуль имеет два больших раздела - раздел интерфейса и раздел реализации.

unit имя; // имя модуля должно совпадать с именем файла
interface
uses список модулей
раздел объявлений модуля // описываются лишь заголовки подпрограмм
implemetation
uses список модулей
раздел реализации модуля // описывается реализация подпрограмм
[ begin операторы ] // инициализация модуля
end.

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

Пример.

Модуль

unit MyUtils;

Interface

const Author = 'Иванов';

var n: integer;

procedure MinMax(a,b: integer; var mn,mx: integer);
function IsPrime (x: integer): boolean;

Implementation

uses Math;

procedure MinMax(a,b: integer; var mn,mx: integer);
begin
mn:= min (a,b);
mx:= max(a,b)
end;

function IsPrime(x: integer): boolean;
begin
...
end;

initialization
n:=100;
end.

Основная программа

uses MyUtils;
begin
writeln(IsPrime(15));
end.

Перечислимый тип

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

var d: (Mon,Tue,Wed,Thu,Fri,Sat,Sun);
...
d:=Mon;
d:=Succ(d); // d=Tue
Inc(d,2); // d=Thi
writeln(Ord(d)); // 3
// Ord - функция преобразования в число, нумерация с нуля
d:=Pred(d);
Dec(d)

Succ для последнего и Pred для первого элементов не определены.
Функции Succ, Pred и Ord применяются не только к перечислимому типу, но и к любому порядковому (целый, символьный, перечислимый)/

Пример.

type DayOfWeek = (Mon,Tue,Wed,Thu,Fri,Sat,Sun);

var d1,d2: DayOfWeek;

function ToString(d: DayOfWeek): string;
begin
case d of
Mon: Result:='Понедельник';
Tue:...
...
end;
end;

Перечислимый тип может использоваться в качестве переключателя в операторе case, а также параметр цикла for может иметь перечислимый тип:

for d:=Mon to Fri do

Диапазонный тип

type
WorkDay = Mon..Fri;
Digits = '0'..'9';
Days = 1..31;

Диапазонный тип совместим по присваиванию только с типом, на базе которого он построен (перечислимый, целый, символьный)

Массивы

Структурированный тип данных объединяет совокупность значений в единое целое. К структурированному типу данных в Pascal относятся: массив, запись, множество, строка, файл.

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

Описание массивов

var
A: array [1..100] of real; // [1..100] - диапазон изменения индекса, real - тип элементов
B: array ['a'..'z'] of integer; // тип индекса - char
type
DayOfWeek=(Mon,Tue,Wed,Thi,Fri,Sat,Sun);
var
C: array [DayOfWeek] of integer;
D: array [Mon..Fri] of integer;
AA: array [1..3,1..4] of real; // двумерный массив - матрица

Присваивание массивов

Массивы одного типа можно присваивать друг другу и использовать при передаче параметров.

var A,B: array [1..10] of integer;
...
A:=B; //!

Однако,

var
A: array [1..10] of integer;
B: array [1..10] of integer;
...
A:=B; // ошибка: типы считаются различными

Инициализация массивов

var A: IArr = (2,1,3,7,4,8,...); // нельзя для локальных переменных
const B: IArr = (...) // можно для локальных переменных
var AA: array [1..3,1..4] of integer = ((1,2,3,4),(5,6,7,8),(9,10,11,12));

Замечание. Элементами массива могут быть другие массивы:

var AA1: array [1..3] of integer;
AA1[3][4]:=5; // ~ AA[3,4]:=5

Хранение массивов в памяти

!!!Не сделано!!!

Открытые массивы

Используются в качестве параметров (Delphi, Free Pascal)

procedure WriteArr (A: array of integer);
var i: integer;
begin
for i:=Low(A) to High(A) do
write(A[i]:4);
end;

Для открытые массивов них недопустимы присваивания массивов, индексом всегда служит целое

Динамические массивы

(Delphi, Free Pascal);

var A: array of integer; // всегда индексируется с 0
begin
SetLength(A,10); // Length(A)
A[0]:=1;

Контроль выхода за границы диапазона - {$R±} (Range Check)

Записи

Запись - множество значений разных типов, объединенных в единое целое. Каждое значение имеет имя и называется полем записи.

Описание

record
список имен полей: тип;
...
end;

Пример.

type Student = record
name: string;
course, group: integer;
end;

Обращение к полям записи

var s1,s2,s3: Student;
name: string;
begin
s1.name:='Иванов';
s1.course:=1;
s1.group:=11;
s2:=s1;
s2.name:='Петров';
with s3 do
begin
name:='Сидоров';
course:=4;
group:=2
end;
end.

with - оператор присоединения
with a,b,c do ~ with a do
with b do
with c do

Инициализаторы записей

var s: Student = {name: 'Иванов'; course: 5; group: 2};

Сортировка массивов записей

Для сортировки массива записей по различным критериям в процедуру сортировки передают функцию сравнения, которая является бинарным предикатом. Например, для сортировки массива студентов функция сравнения имеет следующий вид:

cmp(a[j+1],a[j])

Эта функция имеет смысл операции "меньше".

BubbleSortStudent(gr1_11,36,LessName);

Индексная сортировка

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

i (виртуальный индекс) → Index[i] (реальный индекс)
a[Index[i]]

В начальный момент времени виртуальный индекс совпадает с реальным, т.е. Index[i]=i. При сортировке мы сравниваем элементы массивов используются виртуальные индексы, а меняем местами элементы индексного массива.

procedure BubbleIndexStudentSort(var a: StArr; var Index: I