Упорядочивание элементов массива по возрастанию или убыванию (сортировка)

1.   Упорядочивание элементов массива по возрастанию или убыванию (сортировка)

2.   Поиск элемента в массиве.

Рассмотрим простейший вариант сортировки массива (сортировка выбором). Пусть есть массив из n элементов; сначала найдём в нём самый маленький среди элементов с номерами 2,3,...n и поменяем местами с первым элементом, затем среди элементов с номерами 3,4,...n найдём наименьший и обменяем со вторым, и т. д. В результате наш массив окажется отсортированным по возрастанию.

program SelectSort;

const n = 10;

var a: array [1..n] of integer;

i,j,jmin,buf: integer;

{jmin - номер наименьшего элемента,

buf используется при обмене значений двух элементов}

begin

for i:=1 to 10 do begin

write('Введите элемент номер ',i,' -> ');

readln(a[i]);

end;

for i:=1 to n-1 do begin

jmin:=i;

for j:=i+1 to n do

if a[j]<jmin then jmin:=j;

buf:=a[i];

a[i]:=a[jmin];

a[jmin]:=buf;

end;

write('Результат: ');

for i:=1 to 10 do write(a[i],' ');

readln;

end.

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

program BubbleSort;

...

var i,j: integer;

buf: integer;

begin

...

for i:=2 to n do

for j:=n downto i do

if a[j]<a[j-1] then begin

buf:=a[j];

a[j]:=a[j-1];

a[j-1]:=buf;

end;

end.

Лекция 8. Тип запись

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

 

type tPerson = record

Name,Surname,SecondName: string[30];

Male: boolean;

Address: string;

Phone: longint;

end;

Объявление переменной типа запись выполняется стандартно, с помощью var. Части записи (в нашем случае: Name, Surname, SecondName, Male, Address, Phone) называются полями. Обращение к полю записи в программе производится с помощью знака ‘.’ (точка). Пример обращения к полям:

var p: tPerson;

...

begin

...

p.Surname:=’Иванов’;

p.Name:=’Иван’;

p.SecondName:=’Иванович’;

...

if (p.Phone<0) or (p.Phone>999999)

then writeln(‘Ошибка’);

...

end.

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

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

Чаще всего в качестве оператора используется составной оператор.

Пример:

with p do begin

Surname:=’ Иванов’;

Name:=’Иван’;

...

end;

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

const N = 30;

type tStaff = array [1..N] of tPerson;

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

type tPoint = record

x,y: integer;

end;

 

tRectangle = record

LeftTop: tPoint;

Width, Height: integer;

Color: integer;

end;

Для такой записи можно применять ещё одну форму оператора with, которая может «присоединять» несколько имён записей, например:

var rect: tRect;

 

with rect, LeftTop do begin

x:=100;

y:=150;

Color:=11;

...

end;

Без использования with появились бы выражения вида rect.Color, rect.LeftTop.x, rect.LeftTop.y и т. п.

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

const MaxVertex = 200;

type tPolygon = record

size: integer;

V: array [1..MaxVertex] of tPoint;

Color: tColor;

end;

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

type tFKind = (fCir,fRect,fSqr);

tFigure = record

Color: integer;

case kind: tFKind of

fCir: (Center: tPoint; r: integer);

fRect: (LeftTop,RightBottom: tPoint);

fSqr: (LT: tPoint; size: integer);

end;

В этой записи имеется одно обычное поле (Color), а остальные 6 и представляют собой вариантную часть. Для окружности в ней имеются поля Center и r, для прямоугольника — LeftTop и RightBottom, для квадрата — LT и size. Фраза kind: tFKind не является обязательной, она служит для понимания того, какие поля к каким фигурам относятся. Можно написать просто case integer of ... и нумеровать варианты целыми числами. Заметим также, что в объявлении нашей записи нет слова end, относящегося к case.

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

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

Лекция 9. Процедуры и функции

Процедура – последовательность действий (записанных на Паскале), названная каким-либо именем. Для того чтобы выполнить эту последовательность, нужно в соответствующем месте программы указать её имя (так, например, для очистки экрана при работе с графикой мы указываем ClearDevice;). Кроме того, что программа становится при использовании процедур короче и понятнее, процедуры можно вызывать из разных мест программы (в противном случае пришлось бы повторять в тексте программы одинаковые последовательности действий несколько раз).

Те действия, которые входят в процедуру, записываются до начала основной программы в следующем виде:

program ...

const ...

type ...

var ...

procedure MyProc;

begin

{действия}

end;

begin

{основная программа}

end.

Рассмотрим пример нахождения максимума из трёх чисел:

program Max1;

var a,b,c,m: integer;

begin

write('Введите a: '); readln(a);

write('Введите b: '); readln(b);

write('Введите c: '); readln(c);

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

if c>m then m:=c;

writeln('Максимум = ',m);

readln;

end.

Перепишем его с использованием процедуры:

program Max2;

var a,b,c,m: integer;

procedure FindMax;

begin

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

if c>m then m:=c;

end;

begin

write('Введите a: '); readln(a);

write('Введите b: '); readln(b);

write('Введите c: '); readln(c);

FindMax;

writeln('Максимум = ',m);

readln;

end.

Этот вариант можно улучшить. Пока наша процедура может искать минимум только среди значений конкретных переменных a, b и c. Заставим её искать минимум среди любых трёх целых чисел и помещать результат в нужную нам переменную, а не всегда в m.

Чтобы была видна польза от такой процедуры, рассмотрим пример программы для поиска максимума среди чисел a+b, b+c и a+c:

program Max3;

var a,b,c,m: integer;

procedure FindMax(n1,n2,n3: integer; var max: integer);

begin

if n1>n2 then max:=n1 else max:=n2;

if n3>max then max:=n3;

end;

begin

write('Введите a: '); readln(a);

write('Введите b: '); readln(b);

write('Введите c: '); readln(c);

FindMax(a+b,b+c,a+c,m);

writeln('Максимум из сумм = ',m);

readln;

end.

В скобках после имени процедуры (в её описании) записаны так называемые параметры. Эта запись обозначает, что внутри процедуры можно использовать целые числа, обозначенные n1, n2 и n3, а также заносить значения в переменную типа integer, которая внутри процедуры называется max (а реально во время работы программы все действия производятся над переменной m). Параметры, в которых хранятся числа (n1,n2,n3) называются параметрами-значениями; а те, которые обозначают переменные (max) – параметрами-переменными, перед ними в описании ставится слово var. Параметры, на которые имеются ссылки внутри процедуры (n1, n2, n3, max), называются формальными, а те, которые реально используются при вызове (a+b, b+c, a+c, m) — фактическими.

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

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

program Max4;

var a,b,c,m: integer;

function Max(n1,n2,n3: integer) : integer;

var m: integer;

begin

if n1>n2 then m:=n1 else m:=n2;

if n3>m then m:=n3;

Max:=m;

end;

begin

write('Введите a: '); readln(a);

write('Введите b: '); readln(b);

write('Введите c: '); readln(c);

writeln('Максимум = ',Max(a+b,b+c,a+c));

readln;

end.

Нам уже известно как вызывать функцию из программы (например sqrt, sin и т. п.). Рассмотрим описание функции. Оно очень похоже на описание процедур, но есть два отличия:

1.   После имени функции и списка параметров (если есть) через двоеточие записывается тип значения функции (возможны не только числовые типы, но и логические, строковые, символьные);

2.   Среди операторов в теле функции наиболее важными являются операторы присваивания значения функции (в нашем случае это строчка Max:=m;).

В записанной выше функции используется так называемая локальная переменная m, то есть переменная, которая «видна» только нашей функции, а другие процедуры и функции, а также главная программа её «не видят». Кроме локальных переменных в Турбо-Паскале можно определять локальные константы и типы.

Приведём другие примеры процедур и функций.

1.   Напишем на Паскале функцию .

function Cube(x: real): real;

begin

Cube:=x*x*x;

end;

2.   Вычисление площади треугольника через длины сторон. Здесь будет использована формула Герона: , где p – полупериметр треугольника, a, b, c – длины сторон.

function Square(a,b,c: real): real;

var p: real;

begin

p:=(a+b+c)/2;

Square:=sqrt(p*(p-a)*(p-b)*(p-c));

end;

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

procedure SqEquation(a,b,c: real; var RootsExist: boolean;

var x1,x2: real);

var d: real;

begin

d:=sqr(b)-4*a*c;

if d>=0 then begin

RootsExist:=true;

x1:=(-b+sqrt(d))/(2*a);

x2:=(-b-sqrt(d))/(2*a);

end

else RootsExist:=false;

end;

Можно вместо процедуры написать и функцию, по логическому значению которой мы определяем, есть ли корни, а сами корни передаются также как и в процедуре:

function EqHasRoots(a,b,c: real; var x1,x2: real) : boolean;

var d: real;

begin

d:=sqr(b)-4*a*c;

if d>=0 then begin

EqHasRoots:=true;

x1:=(-b+sqrt(d))/(2*a);

x2:=(-b-sqrt(d))/(2*a);

end

else EqHasRoots:=false;

end;

Использовать такую функцию даже проще чем последнюю процедуру:

if EqHasRoots(1,2,1,r1,r2) then writeln(r1,' ',r2) else writeln('Нет корней');

Лекция 10. Модуль CRT

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

1. Управление экраном

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

 Наиболее распространённым в настоящее время является текстовый режим 80x25 при 16 возможных цветах текста и фона. Многие графические адаптеры позволяют использовать другие режимы, например: 40x25, 80x43, 80x50 и т. д.

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

Ниже приведены основные процедуры и функции для управления экраном в текстовом режиме.

Название	Назначение
InsLine	Вставить строку в том месте где находится курсор, все строки ниже курсора сдвигаются вниз на одну позицию. Курсор остаётся на том же месте.
DelLine	Удалить строку в позиции курсора. Курсор остаётся на том же месте.
GotoXY(x,y: byte)	Переместить курсор в позицию (x,y); x — номер строки, y — номер столбца.
ClrEOL	Очистить строку от курсора и до правого края экрана. Курсор остаётся на прежнем месте
HighVideo	Устанавливает повышенную яркость для вывода текста
LowVideo	Пониженная яркость
NormVideo	Нормальная яркость
TextColor(color: byte)	Устанавливает цвет для вывода текста. Значения цветов — обычно числа от 0 до 15. Вместо этих чисел можно указывать и существующие константы (black, white, red, green, blue, magenta, cyan, brown, lightgray и т. п.). При необходимости можно заставить текст мерцать прибавляя к номеру цвета число 128 или константу Blink.
TextBackGround(color: byte)	Устанавливает цвет для фона.
ClrScr	Очистить экран и поместить курсор в левый верхний угол, т.е. в позицию (1,1) — 1-я строка, 1-й столбец. При очистке экран заполняется цветом фона (см. TextBackground)
WhereX: byte	Эта функция возвращает номер строки, в которой находится курсор.
WhereY: byte	Номер столбца, в котором находится курсор

2. Работа с клавиатурой

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

1.   KeyPressed: boolean — возвращает true, если очередь клавиатуры не пуста (то есть была нажата). Простейший пример использования — повторять какие либо действия, пока не нажата клавиша: repeat ... until KeyPressed;.

2.   ReadKey: char — возвращает символ, соответствующий нажатой клавише (из очереди клавиатуры). Если пользователь нажал клавишу, для которой имеется код ASCII, то в очередь будет положен один соответствующий символ, а если это специальная клавиша (F1, F2, ... F12, клавиши управления курсором, Ins, Del, Home, End, PgUp, PgDn), то сначала в очередь будет положен символ с кодом 0, а затем дополнительный символ. Если очередь клавиатуры пуста, то Readkey будет ждать, пока пользователь не нажмёт какую-либо клавишу.

Для демонстрации работы ReadKey можно написать такую программу:

uses Crt;

var c: char;

begin

repeat

c:=ReadKey;

writeln(ord(c));

until c=#27 {клавиша Escape};

end.

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

3. Другие возможности

При необходимости организации задержек в программе можно использовать процедуру Delay(time: word). Параметр time — время в миллисекундах, на которое нужно приостановить программу.

Ещё одна возможность модуля CRT — работа с системным динамиком. Для включения звука нужна процедура Sound(f: word) (f — частота в герцах). После включения требуется задержка (Delay) на необходимое время звучания, затем — выключение с помощью NoSound. Если не воспользоваться NoSound, то звук будет слышен даже после выхода из программы на Паскале.

Лекция 11. Графика в Турбо Паскале

В отличие от уже знакомого текстового режима, экран в графическом режиме разбит на большое количество точек, каждая из которых может иметь определённый цвет. Точки считаются одинаковыми и прямоугольными, все они плотно «уложены» на экране, то есть для любой точки можно указать, в какой строке и в каком столбце она находится. Номера строк и столбцов в графическом режиме используются как координаты точки, следовательно, координаты всегда целочисленные. В графическом режиме начало координат находится в левом верхнем углу экрана, ось x направлена вправо, ось y направлена вниз.

Заметим, что существуют разные графические режимы, они отличаются количеством точек по горизонтали и вертикали (разрешением), а также количеством возможных цветов, например: 320x200x16, 640x480x16, 640x200x16, 800x600x256 и т. п.

Все средства для работы с графикой содержаться в стандартном модуле Graph, поэтому его нужно будет упоминать после слова uses.

1. Включение и выключение графического режима.

Для включения графического режима используется процедура InitGraph(driver,mode,path) опишем назначение её параметров:

driver – переменная типа integer, в котором задаётся тип видеоадаптера, установленного в компьютере. В модуле определены константы для различных адаптеров, которые избавляют нас от необходимости запоминать числа. Имеются такие константы: CGA, EGA, EGA64, EGAMono, VGA, MCGA, IBM8514 и т. п. Для нас наиболее важной будет константа detect, при указании которой InitGraph сама подыщет наиболее мощный тип адаптера, совместимый с тем адаптером, который установлен на компьютере.

mode – также переменная типа integer, задаёт режим, в котором работает выбранный видеоадаптер (здесь также определены константы). Почти каждый видеоадаптер может работать в нескольких режимах, например, у VGA есть 640x200x16 (VGALo), 640x350x16 (VGAMed), 640x480x16 (VGAHi). Если в первом параметре было указано значение detect, то InitGraph не обращает внимания на mode, а устанавливает наилучший, на её взгляд, режим.

path – строковый параметр. Для каждого видеоадаптера (или для группы сходных видеоадаптеров) существует программа-драйвер, с помощью которой модуль Graph общается с видеоадаптером. Такие драйверы хранятся в файлах с расширением «bgi». В параметре path указывается каталог, в котором хранятся драйверы. Если они находятся в текущем каталоге, то этот параметр равен пустой строке.

Обычно для включения графики мы будем использовать InitGraph в таком виде:

const gpath = ‘Y:\WIN_APPS\BP\BGI’

var gd,gm: integer;

...

begin

...

gd:=Detect;

InitGraph(gd,gm,gpath);

...

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

2. Построение элементарных изображений

Система координат при работе с графикой имеет начало (точку (0,0)) в левом верхнем углу экрана. Ось x направлена вправо, ось y – вниз. Очевидно, что все точки экрана имеют целочисленные координаты.

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

Название	Назначение
PutPixel(x,y: integer; c: word);	Поставить точку (x,y), используя цвет c. Значение цвета обычно меняется от 0 до 15, вместо номера цвета можно употреблять цветовые константы модуля Graph.
SetColor(c: word);	Установить текущий цвет для рисования отрезков, окружностей и т. п. Все линии после употребления этого оператора будут рисоваться установленным цветом.
SetBkColor(c: word);	Установить текущий цвет для фона (то есть цвет всего экрана).
GetMaxX; GetMaxY;	Эти функции возвращают максимальные допустимые значения координат x и y, соответственно.
Line(x1,y1,x2,y2: integer);	Рисовать отрезок из (x1,y1) в (x2,y2) текущим цветом.
Rectangle(x1,y1,x2,y2: integer);	Рисует текущим цветом прямоугольник, левый угол которого – (x1,y1), а правый нижний – (x2,y2).
Circle(x,y: integer; r: word);	Рисует текущим цветом окружность с центром в точке (x,y) радиуса r.
Arc (x,y: integer; a1,a2,r: word);	Рисует дугу окружности. a1 и a2 – начальный и конечный углы (в градусах), соответственно. Угол отсчитывается традиционно, против часовой стрелки, угол величиной 0° соответствует лучу y=0, x>0.
Ellipse(x,y: integer; a1,a2,xr,yr: word);	Рисует дугу эллипса с полуосями xr и yr от угла a1 до a2.
DrawPoly(n: word; P);	Рисует многоугольник, количество сторон в котором – n, а информация о вершинах хранится в нетипизированном параметре P. В качестве P удобнее всего использовать массив из записей, каждая из которых содержит поля x,y: integer;
MoveTo(x,y: integer);	Эта процедура опирается на понятие текущей позиции. Она «запоминает» позицию (x,y) на экране, а в дальнейшем из этой позиции можно рисовать отрезки.
LineTo(x,y: integer);	Рисует отрезок из текущей позиции в точку (x,y). При этом текущая позиция перемещается в конец нарисованного отрезка.
MoveRel(dx,dy: integer);	Перемещает текущий указатель из прежнего положения (x,y) в точку (x+dx,y+dy).
LineRel(dx,dy: integer);	То же, что и предыдущая процедура, но при перемещении рисует отрезок от (x,y) до (x+dx,y+dy).
GetX; GetY;	Возвращают координаты текущего указателя (по отдельности).
ClearDevice;	Очищает экран.

Все приведённые выше процедуры для рисования выполняют только контурные рисунки (не закрашивая прямоугольник, окружность или эллипс внутри). По умолчанию рисование происходит с использованием тонкой сплошной линии, однако толщину и вид линии можно менять с помощью процедуры SetLineStyle(style,pattern,width: word). Рассмотрим назначение параметров этой процедуры.

1.   style – вид линии. Здесь удобно задавать не конкретные числа, а константы: SolidLn, DottedLn, CenterLn, DashedLn, UserBitLn. Первая обозначает сплошную линию, следующие три – разные виды прерывистых линий, последняя – линию, вид которой определяется пользователем (см. ниже).

2.   pattern – образец для вида линии, определяемого пользователем. Этот параметр вступает в действие лишь тогда, когда в предыдущем указано UserBitLn. Образец – это фрагмент линии, заданный в виде числа. Переход от конкретного фрагмента к числу выполняется, например, так:

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