Указатели и динамические структуры

Множества

Множество – это набор неповторяющихся элементов одного порядкового типа с количеством элементов n: n=0,..,255. Значения элементов множества задаются в квадратных скобках:

x:=[5,3,1]; y:=[ ] – пустое множество.

Описание типа:

Type

<имя> =set of <тип>

Пример задания множеств и описания множеств.

Var s: set of char;

set of ‘A’..’Z’;

set of byte;

set of 0..9

 

Const

Alfavit [‘A’..’Z’, ‘a’..’z’];

 

Digits [0..9];

 

Операции над множествами

* пересечение (А В)

+ объединение (А В)

- разность (А\В)

 

Сравнение

= - проверка эквивалентности (True или False)

<> - проверка неэквивалентности

<= проверка вхождения (A B), <, >, >=

In – проверка принадлежности (а А)

 

Добавление элемента к множеству:

S:=[ ];

S:=S+[ch], где S: set of char;

ch: char;

Пример.

X=[‘A’,’B’,’D’];

Y=[‘A’,’P’];

Напечатать множество X (X\Y). (Ответ: BD).

Решение:

Program …

Var X,Y,Z: set of char;

c:char;

Begin

X:=[‘A’, ‘B’,’D’];

Y:=[ ];

Z:=X*(X-Y);

For c:=’A’ to ‘P’ do

If c in Z then write(c);

End.

Записи.

Запись – это совокупность конечного числа разнородных (разнотипных) элементов, называемых полями.

Описание записи:

type <имя типа записи> = record

< имя поля 1 >: < тип поля 1>;

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

< имя поля n>: < тип поля n>;

end;

 

var < имя переменной >: <имя типа записи >;

 

Обращаться к полю надо по составному имени:

<имя записи. имя поля>

Можно использовать оператор присоединения with:

with < имя записи > do

begin

…..

< имя поля >

end;

 

Пример.

№	ФИО	Оценки за 3 экз.
	Иванов	5 3 4
	Петров	5 5 5
	Сидоров	4 4 5

 

Описание:

Type spisok = record

N: integer;

Fam: string[15];

BALL: array [1..3] of integer;

End;

Var b:spisok;

 

Найдем средний балл:

1). S:=(b.BALL[1]+ b.BALL[2]+ b.BALL[3])/3;

или

2). With b do

S:=(BALL[1]+ BALL[2]+ BALL[3])/3;

 

Пример. Создать базу данных, состоящую из 10 записей по 3 поля в каждой: фамилия, имя, телефон. Вывести на экран записи, в которых содержатся сведения об Иванове.

 

Решение:

uses crt;

type student=record;

Fam, Name:string[15];

Tlf: string[10];

end;

var baza: array [1..10] of student;

i:integer;

begin

for i:=1 to 10 do

begin

with baza[i] do

begin

writeln(‘Фамилия’); readln(Fam);

writeln(‘Имя’); readln(Name);

writeln(‘Телефон’); readln(Tlf);

end;

end;

writeln;

for i:=1 to 10 do

begin

with baza[i] do

if Fam:=’Иванов’ then writeln(Fam:16, Name:10, Tlf:10);

writeln;

end;

readkey;

end.

 

Файлы

В TP различают:

o текстовые файлы (text);

o типизированные файлы (file of real,

integer,

char);

o нетипизированные файлы (file).

 

Текстовые файлы

Рассмотрим текстовые файлы, т.е. файлы, состоящие из строк. Каждая строка заканчивается символами с кодами #10 и #13. Оканчивается файл признаком конца файла EOF (EOF – End Of File).

 

строка1 #13 #10

строка2 #13 #10

………………

EOF

 

Для работы с файлами надо:

1. Установить связь программы с файлом
2. “Открыть” файл для чтения или записи
3. Читать из файла или записать в файл
4. Закрыть файл.

 

Рассмотрим следующие процедуры:

Assign (f, ’c:\file.dat’) – связывает внешний файл с файловой переменной f.

Reset (f) – открывает файл только для чтения.

Rewrite (f) – открытие файла только для записи.

Append(f) – открытие файла для пополнения.

Close (f) – закрытие файла.

 

Write (f, x) – записывает в файл f значение x

Writeln (f,x) - ……………..(аналогично)

 

Read (f,x) – читает данные из файла f и помещает прочитанное в переменную x.

Readln (f,x) - ……………(аналогично)

 

Фукции:

Eof(f) – True, если указатель находится в конце файла.

Eoln(f) – True, если указатель находится в конце строки.

 

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

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

Текстовый файл можно создать или преобразовать с помощью текстового редактора.

 

Пример. Файл file.txt содержит текст. Посчитать количество строк в тексте.

 

program….

var f1:text;

k:integer;

begin

assign (f1, ‘c:\temp\file.txt’);

reset (f1);

k:=0;

while not Eof(f1) do

begin

readln(f1);

k:=k+1; {считаем количество символов в строке}

end;

writeln(‘Количество строк =’, k);

close(f1);

end.

 

Пример. В текстовом файле file.txt определить длину самой большой строки.

program ….

var f1:text;

max, k:integer;

c:char;

begin

assign (f1, ‘c:\temp\file.txt’);

reset (f1);

max:=0;

while not Eof(f1) do

begin

k:=0;

while not Eof(f1) do {каждая строка прочитывается посимвольно}

begin

read(f1, c);

k:=k+1; {считаем количество символов в строке}

end;

if k>max then max:=k;

readln(f1);

end;

writeln(‘Наибольшая строка имеет’, max, ‘знаков’);

close(f1);

end.

 

Замечание: в этом примере строки прочитываются посимвольно, т.к. var с: char (можно считывать всю строку, тогда var c: string,

readln(f1,c); k:=length(c), без второго цикла while).

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

Program File_2;

var

ftext:text;

name:string[8];

Procedure OpenFile;

{Процедура открытия для записи файла }

begin {OpenFile}

write (‘введите имя файла’);

write (‘(не более 8 символов); ’);

read (name);

assign (ftext, ‘c:\temp\name.txt’);

{файловая переменная ftext связывается с именем файла}

rewrite (ftext);

{файл открывается для записи}

end; {OpenFile }

 

Procedure WriteToFile

{процедура ввода данных в текстовый файл}

var

x:real;

begin { WriteToFile }

write (‘последовательно вводите’);

writeln (‘действительные числа.’);

write (‘ввод каждого числа завершайте’);

writeln (‘нажатием клавиши Enter.’);

write (‘для окончания ввода данных’);

writeln (‘нажмите клавиши Ctrl+Z и Enter’);

while not Eof do

begin

readln(x); {ввод очередного числи с клавиатуры}

writeln(ftext,x:5:2); {запись очередного числа в файл}

end;

close(ftext) {файл закрывается}

end; { WriteToFile }

 

Procedure ReadFile;

{процедура открывает для чтения текстовый файл и выводит на экран содержащиеся в нем числа, а так же определяет их сумму}

var

s, sum: real;

begin {ReadFile}

sum:=0;

reset (ftext); {файл открывается для чтения}

write (‘Файл ’, name:9);

writeln (‘содержит следующие числа‘);

while not Eof do

begin

readln (ftext,x); {чтение очередного числа их файла}

writeln (x:10:5); {вывод очередного числа на экран}

sum:=sum+x; {вычисление суммы}

end;

writeln (‘сумма чисел в файле: ’, sum:10:5);

end; {ReadFile}

 

begin {Program}

write (‘определение суммы чисел ’);

write (‘содержащихся в’);

writeln (‘текстовом файле’);

writeln;

OpenFile;

WriteToFile;

RwadFile:

readln;

end. {Program}

 

 

Типизированные файлы

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

Описание:

var <имя файловой переменной>: file of <базовый тип>;

Например:

var f1: file of char; (string; integer;)

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

Для работы с типизированным файлом надо:

1. установить связь между файловой переменной и файлом на диске компьютера;

процедура

Assign (<имя файловой переменной>, ‘<путь к файлу>’);

 

1. открыть файл для чтения или записи

Reset (<имя файловой переменной >) – открывает уже существующие файлы;

Rewrite (<имя файловой переменной >) – открывает новые файлы. Если файл уже открыт, то он сначала закрывается и затем снова открывается;

 

1. Произвести чтение или запись

Чтение:

процедура Read (<имя файловой переменной>, v1,v2,..,vn);

Запись:

процедура Write (<имя файловой переменной >, v1,v2,..,vn);

где v1,v2…,vn – переменные базового типа (того же, что и элементы файла);

Для произвольного доступа можно применить:

 

a. процедура Seek (<имя файловой переменной >, <номер элемента>: longint);

- устанавливает указатель файла на элемент с указанным элементом. Первая компонента файла имеет номер 0, последняя (n-1), где n – количество компонент в файле.

 

b. функция FilePos (<имя файловой переменной >):longint;

- определяет текущее положение указателя файла.

 

с. функция FileSize (<имя файловой переменной >):longint;

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

 

Т.к. типизированные файлы не разбиты на строки, процедуры Readln и Writeln для них не имеют смысла.

 

4. Закрыть файл.

процедура Close (<имя файловой переменной >);

 

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

Решение: аналогично программе с текстовым файлом, только ftext надо заменить на freal и исправить процедуру WriteToFile.

var

freal:file of real;

name:string[8];

Procedure OpenFile;

<аналогично>

……………….

 

Procedure WriteToFile

……………….

while not Eof do

begin

readln(x); {ввод очередного числи с клавиатуры}

writeln(freal,x); {запись очередного числа в файл}

end;

……………….

 

Procedure ReadFile;

<аналогично>

……………….

begin {Program}

<аналогично >

……………….

Базы данных

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

Задача: составить программу ввода списка курсантов группы с указанием фамилии курсанта и года рождения в файл и вывода содержимого файла на экран дисплея.

 

 

Исходные данные:

№	Фамилия и инициалы	Год рожд.
	Иванов С.А.
	Андреев П.И.

Программа решения задачи имеет вид:

Program Spis_gr;

uses crt;

type zap=record

fio:string[10];

gr:integer;

end;

var

f_zap: file of zap;

b: zap;

i,n: integer;

begin

clrscr;

assign (f_zap, ‘c:\temp\sp.dat’);

rewrite (f_zap);

write (‘введите количество курсантов’);

readln (n);

write (‘введите фамилию и год рождения курсанта’);

for i:=1 to n do

begin

write(‘=>’);

read (b.fio);

readln (b.gr);

write (f_zap, b);

end;

close (f_zap);

i:=1;

writeln;

writeln (‘ СПИСОК КУРСАНТОВ’);

writeln (‘---------------------------------------’);

writeln (‘№ | Фамилия | Год Рождения’);

writeln (‘---------------------------------------’);

reset (f_zap);

while not Eof(f_zap) do

begin

read (f_zap, b);

writeln (i:2, ’|’, b.fio:10,‘|’, b.gr);

i:=i+1;

end;

writeln (‘---------------------------------------’);

writeln (‘конец’);

readln;

end.

 

Внешние подпрограммы

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

Можно отдельно создать внешние подпрограммы, либо модули. Рассмотрим внешние подпрограммы. В это случае исходный текст каждой процедуры или функции хранится в отдельном файле с расширением.inc и при необходимости включается в текст основной программы с помощью специальной директивы компилятора {$I <имя файла>}.

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

Например: Создадим внешнюю процедуру на сортировку одномерного массива – файл sort.inc, сохраним его в с:\temp

 

Procedure sort; {Сортировка A[n]}

begin

………

……….

……….

end;

 

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

program

var

a[1..50]:array of integer;

i:integer;

 

{$I C:\temp\sort.inc}

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

read (n); randomize;

for i:=1 to n do

begin

a[i]:=20-random(41);

write(a[i], ‘ ‘);

end;

writeln;

sort;

for i:=1 to n do

write(a[i], ‘ ‘);

readln;

end.

 

Модули

 

Подключается модуль с помощью оператора uses. Модуль начинается заголовком unit <имя модуля>. Файл модуля должен иметь то же имя, что и модуль. После трансляции модуль получает расширение.tpu (при трансляции в меню должна быть строка Compile-Destination Disk, иначе.tpu не сохранится).

 

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

 

Модуль имеет следующую структуру:

unit <имя модуля>; {заголовок модуля}

interface

{интерфейсная часть} – раздел внешних описаний

implementation

{раздел реализации} – раздел внутренних описаний

begin

{раздел инициализации модуля}

end.

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

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

Раздел инициализации содержит операторы, которые должны быть выполнены сразу же после запуска программы, использующей модуль. Этот раздел может вообще отсутствовать.

 

Указатели и динамические структуры

Данные в TP могут быть:

1. Статистические. Память под статистические переменные выделяется во время компиляции и сохраняется в течение всей работы программы (статическая память).

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

Использование динамической памяти позволяет:

1. Увеличить объем обрабатываемых данных.

2. Создавать структуры данных переменного размера.

 

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

 

Описание указателя:

var <имя>: <ссылочный тип>;

 

var <имя>: <^тип>; - если тип известен

: ^pointer; - если тип неизвестен

 

Например:

var p1:^integer;

var p2:^char;

 

Указатель – это переменная, значением которой является адрес в памяти. Для переменных, объявленных с помощью указателя, память выделяется в динамической области, размер которой намного (4-5 раза) превосходит размер сегмента, где размещаются обычные переменные. Такой способ объявления может использоваться при большом количестве массивов большой размерности.

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

 

Как происходит выделение памяти под динамическую величину? – в результате выполнения процедуры

New(<указатель>);

 

Например.

New(p1); New(p2);

 

После этого выделяется память под динамические величины

p1^, p2^. Им можно присваивать значения:

p1^:=10; p2^:=’B’;

Запись вида uk^ определяет содержимое по адресу, на который ссылается указатель uk.

 

Nil – это пустая ссылка, т.е. которая никуда не указывает.

 

Ввод и вывод указателей не допускается.

 

Значения указателей можно сравнивать (= и <>), для работы с ними используют следующие стандартные процедуры и функции:

new (указатель); -процедура, по которой указатель получает в качестве значения адрес в динамической памяти и по этому адресу выделяется в соответствии с типом нужное количество байт;

dispose (указатель); - процедура, по которой память, выделенная new, освобождается;

getmem (указатель, <кол-во байт>); - процедура, по которой указатель получает значение, и по этому адресу выделяется не одна область памяти (как new), а n областей;

freemem (указатель, <кол-во байт>) – процедура, освобождающая n областей памяти;

addr (переменная) – функция, которая указателю присвоит адрес переменной (аналогичное действие выполнит и операция @переменная);

maxavail – функция, возвращающий максимальный непрерывный свободный участок в heape памяти (тип longint);

memavail – функция, возвращающая всю свободную динамическую память (тип longint).

 

Пример: Даны a и b. Найти с=a+b с использованием указателей.

 

var ua, ub, uc: ^integer;

begin

new (ua); new(ub); new(uc); {выделяем память}

read (ua^, ub^);

uc^:=ua^+ub^;

writeln (uc^:10);

end.

 

Замечание. При достижении end. память освобождается, поэтому dispose(ua), dispose(ub), dispose(uc), можно не записывать.

Объекты

Объектно-ориентированное программирование (ООП) – методология программирования, основанная на объектах.

Тип object – это структура данных, которая содержит поля и методы.

Описание объектного типа:

type <имя типа> = object;

<поле>;

……….

<поле>;

<метод>;

………..

<метод>;

end;

<описание методов – алгоритмы для методов>;

var <имя>: <имя типа объекта>;

 

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

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

Правила работы с объектами:

 

1. объект обладает свойством наследования. Объект-потомок наследует поля и методы объекта-предка.

Пример. Рассмотрим объект koor (координаты) и point (точка):

type koor:=object

x,y:real;

end;

point=object(koor) {все, что объявлено в типе koor, наследует тип point}

vis: boolean;

end;

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

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

4. Алгоритмы методов записываются после описания объекта. Имена методов состоят их двух частей:

имя объекта. имя метода

Например:

procedure koor.init; {установка координат}

brgin

x:=xp; y:=yp;

end;

 

5. Полиморфизм – это свойство, по которому метод с одним именем может применятся к различным родственным объектам.

Например, чтобы показать на экране или стереть точку, круг и т.д. можно использовать методы yesris, noris:

point. yesris;

cir. yesris;

(один метод yesris используется для решения разных задач).

 

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

<имя метода>; virtual;

Например:

procedure yesris; virtual;

procedure noris; virtual;

 

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

В заголовке такого метода слово procedure заменяется на constructor. Для освобождения памяти используется метод с заголовком destructor.

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

 

Пример. Даны три объекта: координата (koor), точка (point), окружность (cir). Методы: инициализация (init), рисование на экране

(yesris), стирание с экрана (noris).

В программе:

1) рисуется окружность;

2) стирается окружность;

3) в случайных точках экрана появляются разноцветные окружности.

 

Программа:

uses graph, crt;

type koor=object {объект koor}

x,y:integer;

end;

 

point=object(koor) {объект point наследует поля и методы koor}

vis: boolean;

end;

 

cir=object(point) {объект cir наследует поля и методы point}

rad:integer;

constructor init (xp,xy,rp: integer);

procedure yesris;virtual;

procedure noris;virtual;

end;

 

{описание методов-алгортмы}

constructor cir.init; {задаем координаты окружности}

begin

x:=xp; y:=yp;

rad: =rp;

end;

 

procedure cir.yesris; {рисование окружности}

var c:integer;

begin

vis:=true; circle(x,y,rad);

end;

 

procedure cir.noris; {стирание окружности}

var с:integer;

begin

vis:false; с:=getcolor;

setcolor(getbkcolor);

circle(x,y,rad]; setcolor(c);

end;

 

var vcir:cir;

dr,mo,x,y:integer;

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

randomize;

dr:=detect;

initgraph (dr,mo,'с:\prg\tp\bgi');.

vcir.init(320,240,50); {устанавливаем координаты и радиус}

vcir.yesris; {рисуем окружность}

readln;

vcir.noris; {стираем окружность}

readln;

repeat {в случайных точках рисуем разноцветные окр-ти}

x:=random(getmaxx-2*50)+50;

у:=random(getmaxy-2*50)+50;.

vcir.init (x,y, 50); delay (5000);

setcolor (x); vcir.yesris;

until keypressed;

end.

 

Сортировка и поиск

Для решения многих задач удобно сначала упорядочить данные по некоторому признаку, т.е. провести сортировку. Это может быть сортировка массивов, записей, файлов. Сортировка массива – простейший вид сортировки (внутренняя сортировка), сортировка файлов(внешняя сортировка).

Рассмотрим сортировку массива методами:

1) простого выбора;

2) простого обмена (пузырьковая);

3) вставки.

 

1). Рассмотрим A(n). Чтобы отсортировать по возрастанию надо: из n элементов найти max и поменять его местами с последним, из оставшихся (n-1) элементов найти max и поменять местами с (n-1)-ым элементом и т.д. пока весь массив не будет отсортирован (либо из n элементов найти min и поменять с первым и т.д.).

 

Пример. 6 2 9 3; n=4;

 

1 шаг: i=4 –(рассмотрим весь массив), ищем max, ставим на последнее место.

6 2 9 3

=> 6 2 3 9; {9 на своем месте}

2 шаг: i=3 – (рассмотрим все элементы кроме последнего), ищем max, ставим на предпоследнее место.

6 2 3 9

=> 3 2 6 9. (6 и 9 на своем месте).

 

3 шаг: i=2 – (рассматриваем оставшиеся элементы), находим max и меняем местами.

3 2 6 9

=> 2 3 6 9

– ответ (i=1 рассматривать не нужно, т.к. оставшийся элемент стоит на своем месте).

 

Т.е. внешний цикл for i:=n downto 2, где i – количество элементов в рассматриваемой части массива. Во внутреннем цикле надо организовать поиск max элемента a(k) и обмен элементов a(i) на a(k).

 

2). Заключается в обмене местами соседних элементов.

Пример. 6 2 9 3.

i- № пары, т.е. элементы a(i), a(i+1)

k- № шага

 

1 шаг: i:=1 - 6 2 9 3 (обмен)

i:=2 - 2 6 9 3 (нет обмена)

i:=3 - 2 6 9 3 (обмен)

=> 2 6 3 9 (число 9 стоит на своем месте);

 

2 шаг: i:=1 – 2 6 3 9 (нет обмена)

i:=2 – 2 6 3 9 (обмен)

=> 2 3 6 9 (числа 6 и 9 стоят на своих местах);

 

3 шаг: i:=1 – 2 3 6 9 (нет обмена)

=> 2 3 6 9 (числа 3, 6, 9 стоят на своих местах);

Ответ: 2 3 6 9.

 

for k:=1 to (n-1) do

for i:=1 to (n-k) do

if a[i]>a[i+1] then {сравнение соседних элементов}

begin

{обмен};

end;

end;

end;

 

3). При сортировке вставкой вначале упорядочиваются 2 элемента массива. Затем выполняется вставка третьего элемента в соответствующее место по отношению к первым двум элементам, …, на очередном шаге i-ый элемент вставляется на соответствующее место в упорядоченном массиве из первых (i-1) элементов и т.д.

 

Пример. d c a b.

 

1 шаг: d c a b – рассмотрим первые два элемента d и с. ‘c’ ставится в нужное место,‘d’ – сдвигается, т.е. его индекс в массиве увеличивается на 1.

2 шаг: c d a b – рассмотрим первые три элемента, где первый и второй упорядочены. ‘a’ – ставится на нужное место,’c’ и ’d’ - сдвигаются.

3 шаг: a c d b – рассмотрим четыре элемента, где первые три упорядочены. ‘b’ – ставится на нужное место,’c’ и ’d’ - сдвигаются.

=> ответ: a b c d.

 

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

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

Методы поиска:

1). Линейный, т.е. последовательный просмотр массива и сравнение очередного элемента с эталоном x.

2). Бинарный (делением пополам).

Пусть есть массив A(n) – отсортированный по возрастанию. Число x – эталон. Надо найти такое i, что A(i)=x, или сообщить, что эталона x в массиве нет. Идея метода в том, что находим средний элемент и сравниваем с эталоном x. Если совпадает, то средний элемент и есть эталон. Если нет, то либо:

a) x<среднего элемента, тогда все элементы правее среднего элемента можно исключить из рассмотрения в силу упорядоченности массива, и дальше делить только левую часть;

b) x>среднего элемента, тогда исключаем элементы левее среднего элемента и далее применяем метод к правой части.

Средний элемент в обоих случаях в дальнейшем не рассматривается.

 

Пример. 1 3 4 6 8.

x =6 – эталон.

1) a=1, b=n, c=(a+b)\2=(1+5)\2=3 – целочисленное деление.

A(c)=4.

x>A(c) – следовательно исключаем левую часть массива, рассматриваем массив: 6 8.

2) c=(a+b)\2=(4+5)\2=4.

A(c)=6, следовательно элемент найден, стоит на 4 месте.

Программа. Пусть A(n) – упорядоченный массив, x – эталон.

 

a:=1: b:=n: f:=false;

repeat

sred:=(a+b) div 2;

if a[sred]=x then f:=true;

if a[sred]<x then a:=sred+1 else b:=sred;

until (a>=b) or (f);

if f then writeln(‘найден эталон на’, sred, ‘месте’)

else writeln(‘эталон не найден’);

readln;

 

Пример.

1) Массив A(n) отсортировать методом вставки;

2) Дан A(n). Отобрать четные элементы и отсортировать их методом вставки.

 

Program sort_vstavka;

Uses crt;

Type ar=array[1..20] of integer;

Var a,c:ar;

i,j,n,k1:integer;

procedure vvod;

begin

writeln(‘введите размерность’);

readln(n);

for i:=1 to n do

a[i]:=-20+random(41);

writeln(‘исходный массив:’);

for i:=1 to n do

write(a[i]), ‘ ‘);

writeln;

end;

 

procedure vstavka_vozr (var b:ar; n1:integer);

var x:integer;

begin

for i:=2 to n1 do

begin

x:=b[i]; j:=i-1;

while (j>0) and (x<=b[j]) do

begin

b[j+1]:=b[j];

j:=j-1; {сдвиг вправо}

end;

b[j+1]:=x; {вставка}

end;

writeln(‘после сортировки по возрастанию методом вставки’);

for i:=1 to n1 do

write (b[i], ‘ ‘);

writeln; writeln;

end;

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

clrscr;

randomize;

vvod; vstavka_vozr(a,n);

vvod;

writeln(‘отобранный массив: ’);

for i:=1 to n do

if not(odd(a[i])) then

begin

k1:=k1+1;

c[k1]:=a[i];

write(c[k1], ‘ ‘);

end;

writeln;

vstavka_vozr(c,k1);

readkey;

end.

 

Рекурсия

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

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

“Правила предосторожности” при написании рекурсивных программ:

1) Рекомендуется компилировать программу с директивой {$S+}, которая включает проверку переполнения стека (области памяти, в которой хранится состояние вызывающей подпрограммы), а так же использовать директиву {$R+} проверки диапазона переменных (тогда если будет переполнение стека, программа завершится и на экране появится сообщение об ошибке).

2) в начале процедуры (функции), вызываемой рекурсивно, можно разместить строку if keypressed then Halt. В этом случае при зависании программы вместо перезагрузки будет достаточно нажать на любую клавишу.

 

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

 

Пример. Вычисление факториала.

n!=1*2*…*n=n*(n-1)!,

0!=1

1 способ.

Function Fact(n:integer):longint;

begin

if n=1 then Fact:=1 {n=1-барьер}

else Fact:=n*Fact(n-1)

end;

 

2 способ.

F:=1;

for i:=1 to n do

F:=F*i

 

Пример. Вывести n-е число последовательности Фибоначчи

 

1,1,2,3,5,8,13,…

a₁,a₂,a₃,…

a_i= 1, i=1,2

a_i-1+a_i-2, i>2

 

1 способ. (рекурсивный)

Function F(n:integer):longint;

begin

if keypressed then Halt;

if ((n=1) or (n=2)) then F:=1 {барьер}

else F:=F(n-2)+F(n-1);

end;

 

2 способ.

 

Function G(n:integer):longint;

var x,y,t: longint;

i:integer;

begin

x:=1; y:=1;

for i:=3 to n do

begin

t:=y;{t- дополнительная переменная для хранения}

y:=x+y;

x:=t;

end;

G:=y;

end;

 

Упражн. Вычисление целой степени вещественного числа.

y=a^x, a<>0

 

 

Задача “Ханойская башня”

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

На площадке A находится пирамида из дисков, уменьшающихся от основания к вершине. Эту пирамиду в том же виде нужно перенести на площадку В, используя площадку С, как вспомогательную. При этом:

· перекладывать можно только по одному диску;

· класть диск можно только на диск с большим диаметром или на основание площадки.

A (исходный) В (конечный) С (промежуточный)

 

Пусть n – количество дисков.

1) n=2: A→C; A→B; C→B – всего 3 хода.

2) n=3: A→B; A→C; B→C; A→B; C→A; C→B; A→B

– всего 7 ходов.

 

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

Алгоритм задачи следующий:

1) если n=0, то ничего не делать.

2) если n>0, то 1 шаг: переместить (n-1) диск на С через В

2 шаг: переместить 1 нижний диск с А на В

3 шаг: переместить (n-1) диск с С на В через А

 

Program bashnja;

var n:integer;

 

procedure Hanoi (n:integer; A,B,C:char);

begin

if n>0 then {барьер}

begin

Hanoi (n-1, A,C,B); {1 шаг}

writeln(A, ‘=>’,B); {2 шаг}

Hanoi (n-1, C,B,A); {3 шаг}

end;

end;

 

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

writeln (‘введите n’);

readln (n);

Hanoi (n,A,B,C);

end.

 

 

Рекурсия в графике

 

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

 

Пример. Треугольник Серпинского
Этапы выполнения программы в TP

 

исх.модуль трансляция объектный модуль компоновка выполняемый модуль выполнение

(.pas) (компиляция) (.obj) (редактирование (.exe)

связей)

Для выполнения каждого этапа в системе Turbo Pascal применяются специальные средства:

- редактор текстов (editor);

- компилятор (compiler);

- компоновщик (linker);

- отладчик (debugger).

Исходный модуль можно подготовить, используя встроенный текстовый редактор, либо в любом другом текстовом редакторе, хранящим текст в ASCII-кодах, добавив к имени файла расширение.pas.

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

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

 

Отладка и тестирование

Существуют три основных типов ошибок:

- Ошибки времени компиляции.

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

- Ошибка времени выполнения.

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

- Логические ошибки.

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

 

В системе Turbo Pascal имеется встроенный отладчик, дающий возможность интерактивного выполнения программы, во время которого производится наблюдение за значения определенных переменных или выражений. Рассмотрим возможности Turbo Pascal (debugger):

- Трассировка F7 (Run®Trace Into) при этом программа в начале компилирует, затее начинает ее пошагово выполнять. При каждом нажатии F7 выполняется очередная строка. Полезно использовать окно просмотра (Watch), нажав Ctrl+F7 (Debung®Add Watch) и в появившемся окне набрать имя переменной, текущее значение которой надо узнать. Таким образом, используя F7 и Ctrl+F7 можно провести полный анализ работы программы.

- Пошаговое выполнение F8 (Run ®Step Over). Отличие от F7 в том, что при использовании F7 происходит заход внутрь процедур и функций, а применение F8 приводит к обходу подпрограмм. Для прерывания пошаговой отладки используется Ctrl+F2 (Run®Program Reset).

- Переход на курсор F4 (Run®Go To Cursor). Дает возможность передвинуть курсор на определенную строку, а затем указать отладчику выполнить программу до этой строки.

- Точка прерывания Ctrl+F8 (Debug®Breakpionts). Можно пометить строку как точку прерывания. После э