Лекция Алгоритм его свойства и формализация. Принципы разработки алгоритмов и программ для решения прикладных задач
| Вид материала | Лекция |
- «Понятие об алгоритме. Примеры алгоритмов. Свойства алгоритмов. Типы алгоритмов, построение, 84.9kb.
- Тест по теме "Алгоритм и его свойства", 17.58kb.
- 8 Понятие об алгоритме и исполнителе алгоритмов. Свойства алгоритмов, 109.92kb.
- Алгоритм разработки программы учебного курса, 651.27kb.
- Рабочей программы дисциплины Пакеты прикладных программ для экономистов по направлению, 36.76kb.
- Дисциплина «Инженерия знаний» Реферат "онтологии как основа для разработки пакетов, 160.76kb.
- Примерный перечень вопросов для подготовке к зачёту по дисциплине, 6.31kb.
- Основы алгоритмизации, 754.96kb.
- Программа курса «компьютерные науки» Специальность нм, 1 курс, 1 и 2 семестры (2008-2009, 88.62kb.
- Программа вступительных испытаний по «Методам вычислений» направление 010500. 68 Прикладная, 72.41kb.
1 2
^ Циклические конструкции
Циклом или командой повторения называется такая форма организации действий, при которой одна и та же последовательность действий повторяется до тех пор, пока сохраняется значение некоторого логического выражения. При изменении значения логического выражения на противоположное повторения прекращаются (цикл завершается).
Иначе говоря, циклы позволяют многократно выполнять отдельный оператор или последовательность операторов, причем при этом нет необходимости записывать в тексте программы одинаковые операторы несколько раз.
^ Для организации цикла необходимо выполнить следующие действия:
- перед началом цикла задать начальное значение параметра;
- внутри цикла изменять параметр цикла с помощью оператора присваивания;
- проверять условие повторения или окончания цикла;
- управлять циклом, т.е. переходить к его началу, если он не закончен, или выходить из цикла в противном случае.
Различают циклы с известным числом повторений (цикл с параметром) и итерационные (с пред- и постусловием).
В цикле с известным числом повторений параметр изменяется в заданном диапазоне.
Если в цикле изменяется простая переменная, то она является параметром цикла; если в цикле изменяется переменная с индексом, то индекс этой переменной является параметром цикла.
По сравнению с циклом с параметром итерационные циклы являются универсальными. Для организации итерационных циклов используются операторы цикла с предусловием While ... do и цикла с постусловием Repeat..until.
Эти операторы не задают закон изменения параметра цикла, поэтому необходимо перед циклом задавать начальное значение параметра с помощью оператора присваивания, а внутри цикла изменять текущее значение этого параметра.
While оператор1 do оператор2
{оператор2} выполняется до тех пор, пока {оператор1} не станет ложным.
program pro;
var st: integer
begin
while st<10 do
begin
write (‘Значение счетчика равно: ’,st);
writeln;
st =: st+2;
end;
end.
Repeat оператор1 until оператор2
В цикле Repeat..until операторные скобки begin ... end могут быть опущены. {оператор1}выполняется до тех пор, пока {оператор2} не станет ложным.
program pro;
var st: integer
repeat
begin
write (‘Значение счетчика равно: ’,st);
writeln;
st =: st+2;
end;
until st = 10;
end.
Цикл со счетчиком
Для организации цикла с известным числом повторений в Паскаль используется перечисляемый цикл или цикл со счетчиком, реализуемый оператором FOR.
^ В операторе FOR обязательно указываются следующие параметры:
- имя переменной, в которой хранится число повторений цикла (переменной цикла или счетчика цикла),
- переменная цикла должна быть обязательно целого типа (Integer),
- некоторое начальное значение для переменной цикла (счетчика), которое она получает при первом выполнении цикла,
- некоторое конечное значение для переменной цикла, достигнув которое повторение цикла прекращается (условие завершения цикла).
Структура цикла, организованного с помощью этого оператора, имеет вид:
^ FOR Переменная_цикла := Начальное_значение TO Конечное_значение DO
BEGIN
Оператор_1;
Оператор_2;
…
Оператор_N;
END;
Массивы
Массив – это пронумерованная последовательность величин одинакового типа, обозначаемая одним именем. Элементы массива располагаются в последовательных ячейках памяти, обозначаются именем массива и индексом. Каждое из значений, составляющих массив, называется его компонентой (или элементом массива).
Массив данных в программе рассматривается как переменная структурированного типа. Массиву присваивается имя, посредством которого можно ссылаться как на массив данных в целом, так и на любую из его компонент.
Переменные, представляющие компоненты массивов, называются переменными с индексами. Индекс (порядковый номер элемента) записывается в квадратных скобках после имени массива. Например, A[7] — седьмой элемент массива А; D[6] — шестой элемент массива D. Индекс в обозначении компонент массивов может быть константой, переменной или выражением порядкового типа.
Если за каждым элементом массива закреплен только один его порядковый номер, то такой массив называется линейным. Вообще количество индексов элементов массива определяет размерность массива. По этом признаку массивы делятся на одномерные (линейные), двумерные, трёхмерные и т.д.
Массив описывается так:
имя_массива: Array [начальное_значение_индекса .. конечное_значение_индекса] Of базовый_тип;
Например:
Var Mass : Array [1..5] Of Real;
R : Array [1..34] Of Char;
Здесь описываются массивы c именем Mass, состоящий из 5 элементов и символьный массив с именем R, состоящий из 34 элементов.
Массивы бывают одномерные и многомерные. Из многомерных наиболее часто приходится иметь дело с двумерными. Двумерные массивы хранятся в памяти ПК по строкам. Двумерный массив можно представить как матрицу элементов. Описание такого массива выглядит так:
Type
Matrix = array [1..20, 1..10] of Real;
Var
X, Y: Matrix;
Z: array [1..10, 1..10] of Integer;
Массивы X и Y имеют двадцать строк и десять столбцов. Массив Z представляет собой квадратную матрицу размером 10X10.
Для доступа к элементам массива необходимо указать идентификатор массива с одним или несколькими индексами в скобках (в зависимости от размерности массива). Конкретный элемент массива обозначается с помощью имени переменной массива, за которой указывается индекс, определяющий данный элемент.
^ Индексные выражения обозначают компоненты в соответствующей размерности массива. Число выражений не должно превышать числа индексных типов в описании массива. Более того, тип каждого выражения должен быть совместимым по присваиванию с соответствующим индексным типом. В случае многомерного массива можно использовать несколько индексов или несколько выражений в индексе.
Если тип элемента в типе массив также является массивом, то результат можно рассматривать как массив массивов или как один многомерный массив.
Например, array[boolean] of array[1..100] of array[Size] of Real интерпретируется компилятором точно так же, как массив: array[boolean,1..10,Size] of Real.
Массив вида: array[0..X] of Char, где X - положительное целое число, называется массивом с нулевой базой. Массивы с нулевой базой используются для хранения строк с завершающим нулем, и, когда разрешен расширенный синтаксис (с помощью директивы компилятора {$X+}), символьный массив с нулевой базой совместим со значением типа PChar.
Для работы со всем массивом используется идентификатор массива без указания индекса. К массивам приемлемы только операции отношения "=", "<>". Массивы, являющиеся операндами, должны соответствовать друг другу по структуре, т.е. быть одного типа (одинаковые количество и типы элементов). Таким образом, для двух однотипных массивов
X, Y:array [1..30] of Integer;
приемлемы следующие выражения:
- - X=Y (равно TRUE, если значения каждого элемента массива X равны соответствующим элементам массива Y);
- - X<>Y (TRUE, если хотя бы одно значение элемента массива X неравно значению соответствующего элемента массива Y).
Инициализация элементов массива
Поскольку каждый элемент массива имеет свой порядковый номер, то к каждому элементу можно обращаться непосредственно, указывая имя массива и в квадратных скобках порядковый номер элемента.
Для ввода или вывода массива в список ввода или вывода помещается переменная с индексом, а операторы ввода или вывода выполняются в цикле, изменяя при каждой итерации значение индекса.
Инициализация массивов (присвоение начальных значений всем компонентам массивов) осуществляется двумя способами. Первый способ - с использованием типизированных констант, например:
type
Mass= Array[1..10] of Real;
const
K: Mass= ( 0, 2.1, 4, 5.65, 6.1, 6.7, 7.2, 8, 8.7, 9.3 );
При инициализации двумерных массивов значения компонент каждого из входящих в него одномерных массивов записывается в скобках:
type
Mass3x2= Array[1..3,1..2] of Integer;
const
L: Mass3x2= ( (1, 2)(3, 4)(5, 6) );
Второй способ инициализации - использование разновидности процедуры FillChar:
FillChar( var V; NBytes: Word; B: {Byte|Char} );
Эта процедура заполняет участок памяти однобайтовым значением. Например, для обнуления массива A[1..10] of Real можно записать:
FillChar(A, 40, 0); или FillChar(A, SizeOf(A), 0);
Пример. Ввод элементов двумерного массива
B:array [1..20,1..20] of Real.
For i:=1 to 20 do
For i:=1 to 20 do
begin
Write('Введите B[', i,']');
Read(B[i])
end;
Процедуры и функции
В Turbo Pascal различают два вида подпрограмм - это процедуры и функции. Процедура и функция - это именованная последовательность описаний и операторов. При использовании процедур или функций Pascal - программа должна содержать текст процедуры или функции и обращение к процедуре или функции. Тексты процедур и функций помещаются в раздел описаний процедур и функций.
Процедура - это независимая именованная часть программы, которую можно вызвать по имени для выполнения определённой в ней последовательности действий. Процедуры служат для задания совокупности действий, направленных на изменение внешней по отношению к ним программной обстановки.
Функция отличается от процедуры тем, что возвращает результат указанного при её описании типа. Вызов функции может осуществляться из выражения, где имя функции используется в качестве операнда. Функции являются частным случаем процедур, и обязательно возвращают в точку вызова результат как значение имени этой функции. При использовании функций необходимо учитывать совместимость типов в выражениях.
Описание процедуры производится в разделе описаний основной программы. Любая процедура оформляется аналогично программе, может содержать заголовок, разделы описаний и операторов. Синтаксис заголовка процедуры:
Procedure
… {Раздел описаний}
^ Begin
…{Раздел операторов процедуры}
End;
где Procedure - служебное слово; Name - произвольный идентификатор, определяющий имя процедуры.
Procedure MyProc (A,B,C: Real; var X1,X2: Real);
Begin
WriteLn('A=',A, ' B=', B, 'C=', C);
X1:=A+B;
X2:=A*B-C
End;
Разделы описаний процедуры подобно основной программе могут содержать разделы описания меток (Label), констант (Const), типов (Type), переменных (Var) и раздел процедур и функций. Раздел операторов помещается после служебного слова Begin и заканчивается служебным словом End, после End становится " ; ". В основной программе процедуры располагают перед разделом операторов (телом программы) основной программы.
^ Формальные параметры - это переменные, посредством которых передаются данные из места вызова процедуры в её тело, либо из процедуры в места вызова. Список формальных параметров может отсутствовать, при этом символ " ; " ставится сразу за именем процедуры и данные из места вызова процедуры в её тело не передаются.
Вызов процедуры производится указанием имени процедуры и списком фактических параметров:
Name(<Список фактических параметров>);
MyProc(K, L+M, 12, Y1, Y2);
Выполнение оператора вызова процедуры состоит в том, что все формальные параметры заменяются соответствующими фактическими. После этого создается динамический экземпляр процедуры, который и выполняется. После выполнения процедуры происходит передача управления в основную программу, т.е. начинает выполняться оператор, следующий за оператором вызова процедуры.
^ Фактические параметры - это переменные (или значения заданные явно), которые передаются в процедуры на место формальных параметров. Если в вызываемой процедуре отсутствует список формальных параметров, то список фактических параметров тоже отсутствует.
Количество фактических параметров должно соответствовать количеству формальных параметров; соответствующие фактические и формальные параметры должны совпадать по порядку записи и по типу данных.
Описание, определение и вызов функций
Оформляется функция аналогично процедуре. Отличительной особенностью функции является то, что она возвращает только один результат выполнения. Этот результат обозначается именем функции и возвращается (передается) в основную программу (место вызова). Функция состоит из заголовка, раздела описаний и раздела операторов.
Function
… {Раздел описаний}
^ Begin
…{Раздел операторов процедуры}
Name:=<выражение соответствующего типа&;
…
End;
где Function - служебное слово; Name - произвольный идентификатор, определяющий имя функции. В отличии от процедур в разделе операторов тела функции обязательно должен быть хотя бы один оператор присвоения имени функции выражения или значения соответствующего типа. После работы функции результат присваивается имени функции.
Таким образом, алгоритм можно оформить в виде функции в том случае, если в качестве результата получается одно единственное значение. Для вызова функции достаточно указать ее имя (с фактическими параметрами) в любом выражении, где тип результата функции будет приемлем. Имя функции можно использовать в арифметических выражениях и других командах.
Пример. Разработать функцию, определяющую по двум катетам гипотенузу прямоугольного треугольника.
Function Gepoten(a,b:real):real;
Begin
Gepoten:=Sqrt(Sqr(a)+Sqr(b))
End;
Вызов функции из основной программы может выглядеть следующим образом:
z:=Gepoten(x, y); {z присваивается значение гипотенузы}
или
^ WriteLn('Значение гипотенузы', Gepoten(x, y));
Передача параметров в подпрограммы
При передаче параметров по значению в формальный параметр передаётся копия значения соответствующего фактического параметра, при этом сам формальный параметр создаётся в стеке. Для параметров-значений компилятор при вызове процедуры выделяет место в сегменте стека (специальная область оперативной памяти) для каждого формального параметра, вычисляет значение фактического параметра и передаёт его в ячейку, соответствующую формальному параметру, выполняет тело процедуры. После завершения работы процедуры, формальные параметры уничтожаются, а фактические остаются неизменными (по значению).
^ Формальный параметр-значение обрабатывается, как локальная по отношению к процедуре или функции переменная, за исключением того, что он получает свое начальное значение из соответствующего фактического параметра при активизации процедуры или функции.
Соответствующее фактическое значение параметра-значения должно быть выражением и его значение не должно иметь файловый тип или какой-либо структурный тип, содержащий в себе файловый тип. Фактический параметр должен иметь тип, совместимый по присваиванию с типом формального параметра-значения. Если параметр имеет строковый тип, то формальный параметр будет иметь атрибут размера, равный 255.
Пример: У Ани было некоторое количество конфет. Она решила угостить своих подруг Олю, Машу и Свету. Для этого она разделила конфеты поровну на три части, а остаток съела сама. Оля тоже решила угостить подруг и разделила свою долю на три части, а остаток съела сама. Затем также поступили по очереди Маша и Света. По скольку конфет съели каждая из подруг?
program sestry;
var a,o,m,s:integer;
procedure delez (var w,x,y,z:integer);
begin
x:=x+(w div 3);
y:=y+(w div 3);
z:=z+(w div 3);
w:=w mod 3
end;
begin
write ('Сколько конфет получила Анна? '); readln(a);
o:=0;m:=0;s:=0;
delez (a,o,m,s);
delez (o,a,m,s);
delez (m,a,o,s);
delez (s,a,o,m);
writeln (‘Анна съела ',a, ‘конфет’);
writeln ('Ольга съела ',o, ‘конфет’);
writeln ('Маша съела ',m, ‘конфет’);
writeln ('Света съела ',s, ‘конфет’);
end.
Операции со строками
Строка – последовательность символов кодовой таблицы. Длина строки – от 0 до 255.
Формат команд:
type <имя типа> = string [длина строки]
var <идентификатор, …> : <имя типа>.
Структура данных типа String [N] аналогична структуре данных типа Array [1..N]Of Char.
В отличие от массивов строки (а не только их отдельные элементы) могут быть параметрами в процедурах ввода и вывода.
К любому символу в строке можно обратиться точно также, как к элементу одномерного массива, указав имя строки и индекс. В системе Турбо-Паскаль для работы со строками предусмотрен ряд процедур и функции:
К строкам можно применять операцию “+” – сцепление (конкатенация), например:
st:= ‘a’ + ‘b’;
st:= st + ‘c’; {st содержит ‘abc’}
Copy(st, n, m) - функция типа String; копирует из строки st m символов, начиная с символа с номером n.
Delete(st, n, m) - процедура удаляет m символов в строке st, начиная с символа с номером n.
Insert(subst, st, n) - процедура; вставляет подстроку subst в строку st, начиная с символа с номером n.
Length(st) - функция типа Integer; возвращает длину строки st.
Pos(subst,st) - функция типа Integer; отыскивает в строке st первое вхождение подстроки subst и возвращает номер позиции, с которой она начинается; если подстрока не найдена, возвращается 0.
^ Str(x:[width[ : decimals] ], st) - процедура; преобразует число x вещественного или целого типов в строку символов st так, как это делает процедура Writeln перед выводом.
Val(st,x,code) - процедура; преобразует строку символов st во внутреннее представление целой или вещественной переменной x, которое определяется типом этой переменной; параметр code содержит ноль, если преобразование прошло успешно, и тогда в x помещается результат преобразования, в противном случае он содержит номер позиции в строке st, где обнаружен ошибочный символ, и в этом случае содержимое x не меняется; ведущие пробелы в строке st должны отсутствовать.
^ UpCase(Ch) – изменение регистра символа ch на противоположный.
Ord(C) – определяется код символа, где С - либо непосредственно указанный символ, либо переменная символьного типа, либо один символ строковой переменной.
Операции отношения =, <>, >, <, >=, <= выполняются над двумя строками посимвольно, слева направо с учетом внутренней кодировки символов.
Если значение переменной после присваивания превышает по длине максимально допустимую по описанию величину, то лишние справа символы отбрасываются.
Пример 4. Определить, является ли введенная строка "перевертышем".
Перевертышем называется такая строка, которая одинаково читается с начала и с конца. Например, "казак" и "потоп" - перевертыши, "канат" - не перевертыш".
Поступим следующим образом: из введенной строки сформируем другую строку из символов первой, записанных в обратном порядке, затем сравним первую строку со второй; если они окажутся равны, то ответ положительный, иначе - отрицательный. Естественно, предложенный способ решения не является единственно возможным.
^ Program Str4;
Var
S,B : String;
I : Byte;
Begin
Writeln('Введите строку');
Readln(S);
B:=''; {Переменной B присваиваем значение "пустая строка"}
For I:=1 to Length(S) do
B:=S[I]+B; {Конкатенация. Символы строки S пристыковываются к}
{переменной B слева. Самым левым окажется последний.}
^ If B=S Then Writeln('Перевертыш') Else Writeln('Не перевертыш')
End.
Директивы компилятора и управляющие символы
Текст программы может содержать директивы компилятора, которые используются программистом для управления режимами компиляции.
Примечание. Директива - - сообщение в повелительной форме (команда), вводимая оператором и содержащая указание о том, какие необходимо выполнить действия. Директива компилятора — - компонент программы, управляющий последующей компиляцией программы.
Директивы, как и комментарии, заключаются в фигурные скобки, но они имеют отличительный признак $, позволяющий компилятору интерпретировать их соответствующим образом.
^ Пример.
{$ R-}
{$ v+, K-, R-}
Директивы компилятора имеют большое значение как на стадии отладки, так и при выполнении программы. По умолчанию, директивы находятся в состоянии, гарантирующем минимальный объем объектного модуля и минимум времени компиляции.
В программе могут встречаться также управляющие символы "#" и "^". Знак "#" и следующее за ним целочисленное значение в диапазоне 0..255 обозначают символ кодовой таблицы ПК, имеющий соответствующее десятичное значение.
Пример.
#23 — символ, имеющий десятичный код 23
#$18 — символ, имеющий шестнадцатеричный код 18
Знак "^" и следующий за ним какой-либо другой символ трактуются компилятором как управляющий символ, т. е. "^" указывает, что далее следует один управляющий символ.
^ Управляющие символы могут группироваться в строке без разделителей между ними. Допустимо использование управляющих символов вместе со строковыми данными.
Пример.
^I#25^Y^D — группа управляющих символов
^ Writeln('Обнаружена ошибка в тексте!',^G,^G);
Write(#234, #235, #236);
Библиотечные модули пользователя
Понятие библиотечного модуля является одним из основных в языке Турбо Паскаль. Они служат средством создания библиотек подпрограмм (процедур и функций). Библиотечный модуль — это результат компиляции в режиме Compile с установленной директивой Destination = Disk одной или нескольких процедур и функций. Модуль имеет имя, при упоминании которого в разделе uses любой программы можно получить доступ к каждой из находящихся в нем процедур или функций.
Создание библиотечного модуля требует определенной организации с применением зарезервированных слов unit, interface, implementation, begin, end. Система сама определяет структуру компилируемого файла и создает соответственно .TPU-файл (при обнаружении unit и т.д.) или .ЕХЕ-файл (при отсутствии unit, implementation и т.д.). В первом случае формируется библиотечный модуль, во втором — готовый к выполнению по вызову из DOS загрузочный модуль.