Множества
Множество – это набор неповторяющихся элементов одного порядкового типа с количеством элементов 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
Для работы с файлами надо:
- Установить связь программы с файлом
- “Открыть” файл для чтения или записи
- Читать из файла или записать в файл
- Закрыть файл.
Рассмотрим следующие процедуры:
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;)
В типизированных файлах информация хранится в машинном представлении. Никаких преобразований при вводе-выводе не происходит, поэтому возрастает скорость ввода-вывода, но такую информацию нельзя просмотреть в текстовом редакторе.
Для работы с типизированным файлом надо:
- установить связь между файловой переменной и файлом на диске компьютера;
процедура
Assign (<имя файловой переменной>, ‘<путь к файлу>’);
- открыть файл для чтения или записи
Reset (<имя файловой переменной >) – открывает уже существующие файлы;
Rewrite (<имя файловой переменной >) – открывает новые файлы. Если файл уже открыт, то он сначала закрывается и затем снова открывается;
- Произвести чтение или запись
Чтение:
процедура 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,…
a1,a2,a3,…
ai= 1, i=1,2
ai-1+ai-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=ax, 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). Можно пометить строку как точку прерывания. После э