4.Алгоритмы ветвления
Форма организации действий ,при которой в зависимости от выполнения некоторого условия совершается одна или другая последовательность шагов,называется ветвлением.
Алгоритм,содержащий одно или несколько условий и соответственно две и более ветви,называется алгоритмом с ветвлениями.
Одна ветвь указывает действия ,которые будут совершаться, если условие выполняется(ветвь-да),а вторая ветвь указывает действия ,которые будут совершаться,если условие не выполняется(ветвь-нет).
Он имеет следующий формат:
полная форма
if <Логическое условие (выражение)> then <Оператор 1> else <Оператор 2>
соращенная (неполная) форма
if <Логическое условие (выражение)> then < Оператор 1>
Здесь if <Логическое условие (выражение)> — логическое условие или выражение, которое может быть записано в операторе явно или вычислено в программе и присвоено логической переменной;
<Оператор 1>, <Оператор 2> — простые или составные операторы. В случае составного оператора (группы операторов) следует применять операторные скобки begin и end.
5.Интерацианные цикл(алгоритм)
Итерационный цикл
Итак, любой цикл как процесс можно охарактеризовать четырьмя составляющими:
начальное состояние;
ограничение цикла (условие продолжения или завершения):
переход к следующему шагу:
повторяющееся действие – тело цикла.
Если же поведение программы на некотором шаге цикла может зависеть от результатов выполнения тела цикла на предыдуших шагах, либо число повторений цикла зависит от результатов выполнения шага, такие циклы и программируемые ими процессы называются итерационными. Наиболее широко они применяются в вычислительной математике, когда для получения численного результата используется итерационный цикл последовательных приближений к нему.
В итерационных циклах производится проверка некоторого условия, и в зависимости от результата этой проверки происходит либо выход из цикла, либо повторение выполнения тела цикла. Если проверка условия производится перед выполнением блока операторов, то такой итерационный цикл называется циклом с предусловием (цикл "пока"), а если проверка производится после выполнения тела цикла, то это цикл с постусловием (цикл "до").
Особенность этих циклов заключается в том, что тело цикла с постусловием всегда выполняется хотя бы один раз, а тело цикла с предусловием может ни разу не выполниться. В зависимости от решаемой задачи необходимо использовать тот или иной вид итерационных циклов.
6.Сложные(вложенные) алгоритмы
Составной оператор - объединение нескольких операторов в одну группу. Группа операторов внутри составного оператора заключается в операторные скобки (begin-end)
7.Алгоритм обработки одномерных массивов(ввод,вывод,мин,макс)
часто для работы с множеством однотипных данных (целочисленными значениями, строками, датами и т.п.) оказывается удобным использовать массивы. Например, можно создать массив для хранения списка студентов, обучающихся в одной группе. Вместо создания переменных для каждого студента, например Студент1, Студент2 и т.д., достаточно создать один массив, где каждой фамилии из списка будет присвоен порядковый номер. Таким образом, можно дать следующее определение.
Массив - структурированный тип данных, состоящий из фиксированного числа элементов одного типа.
При вводе массива необходимо последовательно вводить 1-й, 2-й, 3-й и т.д. элементы массива, аналогичным образом поступить и при выводе. Следовательно, необходимо организовать цикл.
Блок-схемы алгоритмов ввода элементов массива изображены на рис. 3.3-3.4.
|
|
Рис 3.3 Алгоритм ввода массива с использованием цикла с предусловием |
Рис. 3.4. Алгоритм ввода массива с использованием безусловного цикла |
Как видно, безусловный цикл удобно использовать для обработки всего массива, и в дальнейшем при выполнении таких операций будем применять именно его. Вывод массива организуется аналогично вводу.
Максимальный(минимальный элемент)
max:=a[1]; min:=a[1];
for i:=1 to n do
begin
if a[i] > max then max:=a[i];
if a[i] < min then min:=a[i];
end;
вывод в строку
for i:=1 to n do write (a[i]);
8.Алгоритм обработки двумерных массивов(ввод,вывод,итоги по строкам и столбцам)
Матрица- это двумерный массив, каждый элемент которого имеет два индекса: номер строки - i; номер столбца - j. Поэтому для работы с элементами матрицы необходимо использовать два цикла. Если значениями параметра первого цикла будут номера строк матрицы, то значениями параметра второго - столбцы (или наоборот). Обработка матрицы заключается в том, что вначале поочередно рассматриваются элементы первой строки (столбца), затем второй и т.д. до последней. Рассмотрим основные операции, выполняемые над матрицами при решении задач.
Алгоритм ввода-вывода матриц
Матрицы, как и массивы, нужно вводить (выводить) поэлементно. Блок-схема ввода элементов матрицы изображена на рис. 4.1. Вывод матрицы организуется аналогично вводу.
|
|
Рис. 4.1. Ввод элементов матрицы |
Рис. 4.2. Свойства элементов матрицы |
Рассмотрим несколько задач обработки матриц. некоторые свойства матриц (рис. 4.2):
если номер строки элемента совпадает с номером столбца (i = j), это означает что элемент лежит на главной диагонали матрицы;
если номер строки превышает номер столбца (i > j), то элемент находится ниже главной диагонали;
если номер столбца больше номера строки (i<j), то элемент находится выше главной диагонали.
элемент лежит на побочной диагонали, если его индексы удовлетворяют равенству i+j-1 = n;
неравенство i+j-1 < n характерно для элемента находящегося выше побочной диагонали;
соответственно, элементу лежащему ниже побочной диагонали соответствует выражение i+j-1 > n.
Сумма элементов строки
for i:=1 to n do
s[i]:=0;
for i:=1 to n do
for j:=1 to m do
s[i]:=s[i]+x[i,j];
for i:=1 to n do
write (s[i]);
сумма элементов столбца
for j:=1 to m do
s[j]:=0;
for j:=1 to m do
for i:=1 to n do
s[j]:=s[j]+x[i,j];
for j:=1 to m do
write (s[j]);
9.Множества.Операции над множествами.Пример.
Множество – это структурированный тип данных, представляющий собой набор взаимосвязанных по какому-либо признаку или группе признаков объектов, которые можно рассматривать как единое целое. Каждый объект в множестве называется элементом множества. Все элементы множества должны принадлежать одному из скалярных типов, кроме вещественного. Этот тип называется базовым типом множества. Базовый тип задается диапазоном или перечислением. Область значений типа «множество» – набор всевозможных подмножеств, составленных из элементов базового типа. В выражениях на языке Pascal значения элементов множества указываются в квадратных скобках: [1,2,3,4], ['a','b','c'], ['a'..'z']. Если множество не имеет элементов, оно называется пустым и обозначается как [ ]. Количество элементов множества называется его мощностью.
Для описания множественного типа используется словосочетание set of (множество из...).
Формат записи множественных типов:
type <имя типа> = set of <элемент 1 .. элемент n>; var <идентификатор> : <имя типа>;
Можно задать множественный тип и без предварительного описания:
var <идентификатор> : set of <элемент1, .. .>;
Операции над множествами.
При работе с множествами допускается использование операций отношения =, <>, >=, <=, объединения, пересечения, разности множеств и операции in. Результатом выражений с применением этих операций является значение True или False.
Операция «не равно» (<>). Два множества А и В считаются неравными, если они отличаются по мощности или по значению хотя бы одного элемента.
Операция «равно» (=). Два множества А и В считаются равными, если они состоят из одних и тех же элементов. Порядок следования элементов в сравниваемых множествах значения не имеет.
Операция «не равно» (<>). Два множества А и В считаются неравными, если они отличаются по мощности или по значению хотя бы одного элемента.
Операция «больше или равно» (>=). Эта операция используется для определения принадлежности множеств. Результат операции А >= В равен True, если все элементы множества В содержатся в множестве А. В противном случае результат равен False.
Операция in. Эта операция используется для проверки принадлежности какого-либо значения указанному множеству. Обычно применяется в условных операторах.
При использовании операции in проверяемое на принадлежность значение и множество в квадратных скобках не обязательно предварительно описывать в разделе описаний. Операция in позволяет эффективно и наглядно производить сложные проверки условий, заменяя иногда десятки других операций.
Например, выражение if (a=l) or (a=2) or (a=3) or (a=4) or (a=5) or (а=б) then... можно заменить более коротким выражением if a in [1..6] then... .
Часто операцию in пытаются записать с отрицанием: X NOT in M. Такая запись является ошибочной, так как две операции следуют подряд; правильная инструкция имеет вид NOT (X in M).
1. Объединение двух множеств А и В (запись А+В) есть новое множество С состоящее из элементов множества А или В или того и другого одновременно С:=А+В. [‘A’, ‘C’]+ [‘A’, ‘B’]= [‘A’, ‘B’, ‘C’].
2. Пересечение двух множеств А и В (запись А*В) есть новое множество С состоящее из элементов одновременно входящих и в А и в В С:=А*В. [‘A’, ‘C’]+ [‘A’, ‘B’]= [‘A’].
3. Разность двух множеств А и В (запись А-В) есть новое множество С состоящее из элементов множества А отсутствующих в В С:=А-В. [1, 2, 5, 8]-[1, 3, 5]=[2, 8].
4. Сравнение: а) тождественно A=B истина, если A и B имеют одинаковые элементы [1, 5]=[ 5, 1]=True. [1, 2, 5]=[ 5, 1]=False. б) не тождественно A<>B истина, если одно множество содержит хотя бы один элемент не входящий в другое [‘A’, ‘C’] <> [‘A’, ‘B’]= > True.
5. Проверка на включение: а) содержится в Выражение A <=B истина, если все элементы A содержатся в B [‘A’] <= [‘A’, ‘B’]= > True. б) содержит (>=) Выражение A => B истина, если все элементы B являются элементами A [1, 2, 5, 8] >=-[1, 5, 8].
6. Проверка на принадлежность элемента множеству E IN A. ‘C’ IN [‘A’, ‘C’, ‘B’, ‘F’]=> True.
Использование в программе данных типа set дает ряд преимуществ: значительно упрощаются сложные операторы if, увеличивается степень наглядности программы и понимания алгоритма решения задачи, экономятся память, время компиляции и выполнения. Имеются и отрицательные моменты, основной из них – отсутствие в языке Pascal средств ввода-вывода элементов множества, поэтому программист сам должен писать соответствующие процедуры.
10.Стандартные средства обработки файлов
При работе с файлами необходимо:
Связать файловую переменную (внутренне имя файла) с именем файла на носителе (настоящее имя);
Открыть перед началом работы переменную с файлом с помощью специального оператора;
В конце работы закрыть файл.
Файловый тип данных или файл определяет упорядоченную совокупность произвольного числа однотипных компонент.
Общее свойство массива, множества и записи заключается в том, что количество их компонент определено на этапе написания программы, тогда как количество компонент файла в тексте программы не определяется и может быть произвольным.
TURBO PASCAL поддерживает три файловых типа: текстовые файлы, компонентные файлы, бестиповые файлы.
Описание файловых переменных текстового типа производится с помощью служебного слова Text, например:
var tStory: Text;
Бестиповые файлы описываются с помощью служебного слова File:
var f: File;
Файловые переменные, которые описаны в программе, называют логическими файлами. Все основные процедуры и функции, обеспечивающие ввод - вывод данных, работают только с логическими файлами. Физический файл должен быть связан с логическим до выполнения процедур открытия файлов.
TURBO PASCAL вводит ряд процедур и функций, применимых для любых типов файлов: Assign, Reset, Rewrite, Close, Rename, Erase, Eof, IOResult.
Процедура Assign( var f; FileName: String ) связывает логический файл f с физическим файлом, полное имя которого задано в строке FileName.
Процедура Reset( var f ) открывает логический файл f для последующего чтения данных или, как говорят, открывает входной файл. После успешного выполнения процедуры Reset файл готов к чтению из него первого элемента.
Процедура Rewrite( var f ) открывает логический файл f для последующей записи данных (открывает выходной файл). После успешного выполнения этой процедуры файл готов к записи в него первого элемента.
Процедура Close( var f ) закрывает открытый до этого логический файл. Вызов процедуры Close необходим при завершении работы с файлом. Если по какой-то причине процедура Close не будет выполнена, файл все-же будет создан на внешнем устройстве, но содержимое последнего буфера в него не будет перенесено. Для входных файлов использование оператора закрытия файла необязательно.
Логическая функция EOF( var f ): Boolean возвращает значение TRUE, когда при чтении достигнут конец файла. Это означает, что уже прочитан последний элемент в файле или файл после открытия оказался пуст.
Процедура Rename( var f; NewName: String ) позволяет переименовать физический файл на диске, связанный с логическим файлом f. Переименование возможно после закрытия файла.
Процедура Erase( var f ) уничтожает физический файл на диске, который был связан с файловой переменной f. Файл к моменту вызова процедуры Erase должен быть закрыт.
11.Фактические и формальные параметры процедур
Формальные параметры – данные, с которыми работает подпрограмма (ПП). Это внутренние данные для ПП. Они перечисляются в заголовке ПП и связаны с фактическими параметрами.
Фактические параметры – данные, передаваемые в ПП и возвращаемые из нее. Это внешние для ПП данные, с которыми имеет дело вызывающая часть программы. В ПП им соответствуют формальные параметры. Указываются в списке фактических параметров при обращении к ПП. Синонимы:
Параметры = формальные параметры.
Аргументы = фактические параметры.
Для формальных и фактических параметров необходимо соблюдать соответствия:
одинаковое количество,
одинаковый порядок следования,
совместимость типов по присвоению
12.Локальные и глобальные переменные
Использование процедур и функций тесно связано с некоторыми особенностями работы с идентификаторами (именами) в программе. В частности, не все имена всегда доступны для использования. Доступ к идентификатору в конкретный момент времени определяется тем, в каком блоке он описан.
Имена, описанные в заголовке или разделе описаний процедуры или функции называют локальными для этого блока. Имена, описанные в блоке, соответствующем всей программе, называют глобальными. Следует помнить, что формальные параметры процедур и функций всегда являются локальными переменными для соответствующих блоков.
Основные правила работы с глобальными и локальными именами можно сформулировать так:
Локальные имена доступны (считаются известными, "видимыми") только внутри того блока, где они описаны. Сам этот блок, и все другие, вложенные в него, называют областью видимости для этих локальных имен.
Имена, описанные в одном блоке, могут совпадать с именами из других, как содержащих данный блок, так и вложенных в него. Это объясняется тем, что переменные, описанные в разных блоках (даже если они имеют одинаковые имена), хранятся в разных областях оперативной памяти.
Глобальные имена хранятся в области памяти, называемой сегментом данных (статическим сегментом) программы. Они создаются на этапе компиляции и действительны на все время работы программы.
В отличие от них, локальные переменные хранятся в специальной области памяти, которая называется стек. Они являются временными, так как создаются в момент входа в подпрограмму и уничтожаются при выходе из нее.
Имя, описанное в блоке, "закрывает" совпадающие с ним имена из блоков, содержащие данный. Это означает, что если в двух блоках, один из которых содержится внутри другого, есть переменные с одинаковыми именами, то после входа во вложенный блок работа будет идти с локальной для данного блока переменной. Переменная с тем же именем, описанная в объемлющем блоке, становится временно недоступной и это продолжается до момента выхода из вложенного блока.
Рекомендуется все имена, которые имеют в подпрограммах чисто внутреннее, вспомогательное назначение, делать локальными. Это предохраняет от изменений глобальные объекты с такими же именами