Program Demo;

Var a, b ,c : real ;

Procedure Ring (var s , l : real ; d : real);

Begin L:=3.14 *d; {длина окружности }

S:=cir (d) ; {компилятор еще не знает о функции cir}

End;

Function Cir (d: real): real; {площадь круга }

Begin cir:= 3.14* sqr(d) / 4;

End;

………………………………………………………………………

Очевидный выход – поменять порядок строк так, чтобы функция Cir была определена перед процедурой Ring(…) .Однако можно и иначе.

Действия:

1. Оставить подпрограмму (функцию cir) на своем месте, вычеркнув из ее заголовка все параметры: Function cir;

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

Function cir (d: real): real;

1. После полного заголовка добавить слово Forward.

5. РЕГУЛЯРНЫЕ ТИПЫ

5.1. Одномерный массив, или переменные с индексами

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

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

Описание в разделе переменных:

Var имя массива: Array [тип индекса] of тип элемента;

Тип индекса может быть любым простым типом, кроме Real и Integer (Boolean, Char, перечислимый, ограниченный).

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

Var A: Array [1..5] of Real;

Это массив из пяти действительных чисел: А[1], А[2], А[3], А[4], А[5].

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

Пример: Var B: Array [1582..1994] of Integer;

Var C: Array [-754..-1] of Integer;

(это, например, население за какие-то годы нашей эры и до нашей эры).

Массив латинских букв: (можно посчитать частоту появления в тексте):

Var Lat: Array [‘A’..’Z’] of Integer;

Массив t⁰C воздуха на островах:

Type Остров = (Gaiti, Sumatra, Taimir);

Var T: Array [Остров] of Real;

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

Var А: Array [5] of Real;

Var А: Array[Integer] of Real;

Пример:

Var

Massiv: Array [1..N] of Real;

Year: Array [янв..дек] of Integer;

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

Var А, В, С: Array[1..50] of Real;

Здесь объявлено списком три массива действительных чисел, каждый из которых содержит по 50 элементов:

А[1], A[2],… A[50].

B[1], B[2],… B[50].

C[1], C[2],… C[50].

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

Элементы массива записываются в разделе операторов как идентификатор с индексом в квадратных скобках.

B[5]:=B[3]-1;

Sum:=Sum-C[K];

P1:=A[2*3+1];

Для ввода и вывода числовых значений элементов массива используются циклы.

Пример:

For I:=1 to 9 do

Read(A[I]);

Это ввод 9-ти значений элементов массива А.

For I:=1 to 9 do

Writeln(A[I]);

Это их вывод.

Пример: Вычислить сумму 15-ти целых чисел.

Program Sum;

Var X: Array [1..15] of Integer;

I: 1..15;

Sum: Integer;

Begin

Sum:=0;

For I:=1 to 15 do

Begin

Read(X[I]);

Sum:=Sum+X[I];

End;

End.

В языке программирования Паскаль помимо явного описания массивов в разделе переменных есть другая форма описания, состоящая из двух этапов. Сначала в разделе описания типов Type указывается тип массива, затем в разделе описания переменных Var перечисляются массивы, относящиеся к донному типу.

Type имя типа = Array [тип индекса] of тип элементов массива;

Var имя массива: имя типа;

Пример: Программа с двумя процедурами: одна – для ввода элементов массива, другая для вычисления суммы и произведения элементов.

Program TI4;

Type Massiv = Array [1..20] of Real;

Var A, B: Massiv;

Sum, Pr: Real;

Procedure Vvod (N:Integer; Var X:Massiv);

Var I: Integer;

Begin

Writeln(‘Ввод’);

For I:=1 to N do Read(X[I]);

End;

Procedure Summa (N:Integer; Var X:Massiv; Var Sum, Pr: Real);

Var I: Integer;

Begin

Sum:= 0;

Pr:=1;

For I:=1 to N do

Begin

Sum:=Sum+X[I];

Pr:=Pr*X[I];

End;

End;

Begin

Vvod(8,A); (*вызов процедуры*)

Summa(8,A,Sum,Pr); (*вызов процедуры*)

Writeln (‘Sum=’,Sum:7:2,’ ’:3,’Pr=’,Pr);

Writeln;

Vvod(15,B);

Summa(15,B,Sum,Pr);

Writeln (‘Sum=’,Sum:7:2,’ ’:3,’Pr=’,Pr);

End.

В основной программе описан тип массива длинной 20 элементов, а реально используются массивы А (8 элементов) и В(15 элементов).

Пример: Расположить элементы заданного действительного массива в порядке убывания: 1 2 3 4  4 3 2 1

Program Rangir;

Const N=10;

Var A: Array [1..N] of Real;

I, K: Integer; R: Real;

Begin

Writeln(‘Ввод’);

For I:=1 to N do Read (A[I]);

For K:=1 to N do

For I:=1 to N-K do

If A[I]<A[I+1] then

Begin

R:= A[I];

A[I]:= A[I+1];

A[I+1]:=R;

End;

For I:=1 to N do Write (A[I]);

End.

K - номер просмотра строки (всего N-1 просмотров)

I - номер сравнение элементов в просмотре (N-K сравнений).

Пример: Массив R состоит из 10-ти элементов действительного типа.

Type Mas = Array [1..10] of Real;

Var R: Mas;

Если в программе несколько таких массивов, то изменится лишь раздел описания переменных:

Var R, A, B, C: Mas;

В разделе операторов программы используются массивы R, A, B, C. Тип массива Mas введен формально только в разделе описаний и нигде в программе не указывается и не обрабатывается.

Пример: Найти наибольшее из 10-ти заданных целых чисел.

Program Max;

Const N=10;

Type Massiv = Array [1..N] of Integer;

Var K: Massiv;

Max, I: Integer;

Begin

Writeln(‘Ввод’);

For I:=1 to N do Read (K[I]);

Max:=K[1];

For I:=2 to N do

If K[I]>Max then Max:=K[I];

Writeln;

Write (‘Max=’, Max:4);

End.

Здесь 2 независимых цикла:

1-ый – для ввода значений массива;

2-ой – для нахождения максимального элемента.

Сначала первый элемент массива K[1] обозначается именем Мах. Затем каждый последующий элемент сравнивается со значением Мах, и если он оказывается больше, то получает имя Мах.

Пример: Составить программу определения минимального и максимального элементов заданного массива.

Program Minmax;

Const N=9; (*число элементов*)

Type Massiv = Array [1..N] of Real;

Var A: Massiv; (*массив элементов*)

I: Integer; (*параметр цикла*)

Max, Min: Real; (*максимальный и минимальный элементы*)

Procedure Maxmin (K: Integer; Var X: Massiv; Var Max, Min: Real);

Var J: Integer;

Begin

Max:=X[1];

Min:=X[1];

For J:=2 to K do

Begin

If X[J] > Max then Max:= X[J];

If X[J] < Min then Min:= X[J];

End;

End;

Begin

Writeln (‘Ввод массива’);

For I:=1 to N do Read (A[I]);

Maxmin (N, A, Max, Min); (*вызов процедуры*)

Writeln (‘макс. элемент=’, Max:4:1);

Writeln (‘мин. элемент=’, Min:4:1);

End.

В процедуре Maxmin определяются максимальный и минимальный элементы массива. Переменная J и формальные параметры процедуры K, X, Max, Min являются локальными. В основной программе происходит ввод значений массива, вызов процедуры и вывод результатов. Константа N, тип Massiv, а также переменные A, I, Max и Min являются глобальными.

Пример: Дан массив действительных чисел {A_i}, где i=1,2,3,4,..M. Пусть M = 15. Вычислить сумму элементов с 1-го по 12-ый и сумму элементов с 8-го по 15-ый. Затем найти произведение этих сумм.

Program Pr2;

Const M=15;

Var A: Array [1..M] of Real;

P: Real; (*произведение сумм*)

J: Integer; (*параметр цикла*)

Function Summa (N, K: Integer): Real;

Var I: Integer;

S: Real;

Begin

S:=0;

For I:=N to K do S:=S+A[I];

Summa:=S;

End;

Begin

Writeln (‘Ввод массива’);

For J:=1 to M do Read (A[J]);

P:=Summa (1,12)* Summa(8,15);

Writeln(‘произведение=’,P:6:3);

End.

Пример: Дан массив (Х₁,Х₂,…Х₁₀₀). Записать отдельно положительные и отрицательные элементы.

Program Sort;

Const Nmax=100;

Var X,Pol,Otr: Array [1..Nmax] of Real;

I,N,K: Integer;

Begin

N:=0; K:=0;

For I:=1 to Nmax do

Begin

Read (X[I]);

If X[I] >0 then

Begin

K:=K+1;

Pol[K]:=X[I];

End

Else

Begin

N:=N+1;

Otr[N]:=X[I];

End;

End;

For I:=1 to K do Write (Pol[I]);

Writeln;

For I:=1 to N do Write (Otr[I]);

End.

Пример: Вычислить среднее арифметическое массива D из N элементов (N500).

Program Sred;

Const NM=500;

Var D: Array [1..NM] of Real;

I,N,Nvar: Integer;

Sum, Srd: Real;

Begin

Sum:=0;

Writeln (‘Nvar=?’);

Readln(Nvar);

Writeln (‘Ввод массива’);

For I:= 1 to Nvar do

Begin

Read (D[I]);

Sum:= Sum + D[I];

End;

Srd:=Sum/Nvar;

Writeln(‘Srd=’,srd);

End.

Пример: Вычислить n!

Program Nfact;

Var NF, K, N:Integer;

Begin

Writeln(‘N=?’);

Readln (N);

NF:=1;

For K:=1 to N do NF:=NF*K;

Writeln(‘NF=’,NF);

End.

Пример: Найти наибольший элемент массива (b₁,b₂,…b₁₀₀) и его №.

Program Max;

Const NMax=100;

Var B: Array [1..NMax] of Real;

I,Imax: Integer;

Bmax: Real;

Begin

Writeln (‘Ввод массива’);

For I:=1 to NMax do Read (B[I]);

Bmax:=b[1]; Imax:=1;

For I:=2 to NMax do

If B[I]>Bmax then

Begin

Bmax:=B[I];

Imax:=I;

End;

Writeln (‘Bmax=’, Bmax, ’Imax=’, Imax);

End.

Пример: Найти скалярное произведение двух векторов:

X=(x₁,x₂,…x_n) _n

Y=(y₁,y₂,…y_n) (X,Y)= x_iy_i

ⁱ⁼¹

Program Scal;

Const N=3;

Type Vektor = Array [1..N] of Real;

Var X, Y: Vektor;

I: Integer;

S: Real;

Begin

S:=0;

Writeln (‘Ввести X,Y’);

For I:=1 to N do

Begin

Read(X[I],Y[I]);

S:= S+ X[I]*Y[I];

End;

Writeln(‘Scal=’,S);

End.

Пример: Перемножить два вектора:

X=(x₁,x₂,x₃) _ _ _

Y=(y₁,y₂,y₃) Z = X * Y

Program V;

Type Vektor = Array [1..3] of Real;

Var X, Y, Z: Vektor;

I: Integer;

Begin

Writeln (‘Ввести X,Y’);

For I:=1 to 3 do

Begin

Read (X[I],Y[I]);

Z[I]:= X[I]*Y[I];

End;

Writeln (‘Вектор Z’);

For I:=1 to 3 do Write (Z[I]);

End.

(x₁, x₂, x₃) * (y₁, y₂, y₃) = (x₁y₁, x₂y₂, x₃y₃)

1. Алгоритмы сортировки массивов

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

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

- сравнение, определяющее упорядоченность пары элементов;

- перестановку, меняющую местами пару элементов;

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

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

1. Метод пузырька (метод обменной сортировки с выбором)

Идея этого метода отражена в его названии. Самые легкие элементы массива "всплывают" наверх, самые "тяжелые" - тонут. Алгоритмически это можно реализовать следующим образом. Мы будем просматривать весь массив "снизу вверх" и менять стоящие рядом элементы в там случае, если "нижний" элемент меньше, чем "верхний". Таким образом, мы вытолкнем наверх самый "легкий” элемент всего массива. Теперь повторим всю оперно для оставшихся неотсортироваными N-1 элементов (т.е. для тех, которые лежат "ниже" первого. Как видно, алгоритм достаточно прост, но, как иногда замечают, он является непревзойденным в своей неэффективности. Немного более эффективным, но таким наглядным является второй метод.

2. Сортировка выбором