Свойств алгоритмов способы представления алгоритма

Содержание

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

Основные свойства и способы представления алгоритма

Любой алгоритм должен обладать следующими свойствами:

• определенностью –за конечное число шагов либо должен быть получен результат, либо доказано его отсутствие;

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

• массовостью– возможностью получения результата при различных исходных данных для некоторого класса сходных задач;

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

• дискретностью— возможностью разбиения алгоритма на отдельные элементарные действия.

Существуют следующие формы представления алгоритма:

• словесная (вербальная) на неформальном языке;

• на языках программирования;

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

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

Алгоритм, записанный на языке программирования, называется программой.

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

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

Для записи алгоритма существует общая методика:

— каждый алгоритм должен иметь имя, которое раскрывает его смысл;

— необходимо обозначить начало и конец алгоритма;

— описать входные и выходные данные;

— указать команды, которые позволяют выполнять определенные действия над выделенными данными.

БЛОК-СХЕМЫ АЛГОРИТМОВ

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

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

Операторный блок – это прямоугольник, в который вписывается некоторое действие или выражение. Этот блок может иметь несколько входов и только один выход, что обеспечивает однозначность в определении последовательности выполняемых действий. Исключение составляют начальный и конечный блоки. Первый не имеет входов, второй – выхода.

Условный блок обозначается ромбом, в который вписывается некоторое условие. Поскольку результатом проверки условия может быть либо “да”, либо “нет” (“истина” или “ложь”, “0” или “1”), блок имеет два соответствующих этим ответам выхода.

Если операторный или условный блоки имеют более одного входа, то изображение входов совмещается. На связях, определяющих последовательность выполнения блоков, стрелки не обязательны, если их направление соответствует продвижению “сверху-вниз” и “слева-направо”. Ограничения на геометрические размеры блоков в этом случае не вводятся.

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

ОСНОВНЫЕ БЛОКИ БЛОК — СХЕМЫ

Рис.1. Основные блоки блок – схемы

Рис.1. — Основные блоки блок – схемы

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

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

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

Использование блок-схем дает возможность:

• наглядно отобразить базовые конструкции алгоритма;

• сосредоточить внимание на структуре алгоритма, а не на синтаксисе языка;

• анализировать логическую структуру алгоритма;

• преобразовывать алгоритм методом укрупнения (сведения к единому блоку) или детализации – разбиения на ряд блоков;

• использовать принцип блочности при коллективном решении сложной задачи;

• осуществить быструю проверку разработанного алгоритма (на уровне идеи);

• разобрать большее число учебных задач.

Составление блок-схемы алгоритма является важным и в большинстве случаев необходимым этапом решения сложной и большой задачи на ЭВМ, значительно облегчающим процесс составления программ.

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).

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

Источник

Информатика

Алгоритмы и способы их описания.

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

Примеры: правила сложения, умножения, решения алгебраических уравнений и т.п.

1.Универсальность (массовость) — применимость алгоритма к различным наборам исходных данных.

2.Дискретность — процесс решения задачи по алгоритму разбит на отдельные действия.

3.Конечность — каждое из действий и весь алгоритм в целом обязательно завершаются.

4.Результативность — по завершении выполнения алгоритма обязательно получается конечный результат.

5.Выполнимость (эффективность) — результата алгоритма достигается за конечное число шагов.

6.Детерминированность (определенность) — алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно. Т.е. одно и то же предписание после исполнения должно давать один и тот же результат.

7.Последовательность – порядок исполнения команд должен быть понятен исполнителю и не должен допускать неоднозначности.

1. вычислительные алгоритмы , работающие со сравнительно простыми видами данных, такими как числа и матрицы, хотя сам процесс вычисления может быть долгим и сложным;

2. информационные алгоритмы , представляющие собой набор сравнительно простых процедур, работающих с большими объемами информации (алгоритмы баз данных);

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

По типу передачи управления алгоритмы бывают: основные (главные выполняемые программы) и вспомогательные (подпрограммы).

Для задания алгоритма необходимо описать следующие его элементы:

1.набор объектов, составляющих совокупность возможных исходных данных, промежуточных и конечных результатов;

3.правило непосредственной переработки информации (описание последовательности действий);

5.правило извлечения результатов.

Способы описания алгоритмов.

Символьный, когда алгоритм описывается с помощью специального набора символов (специального языка).

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

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

Правила создания блок – схем:

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

2.Стрелка в конце линии может не ставиться, если линия направлена слева направо или сверху вниз.

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

4.Из блока (кроме логического) может выходить только одна линия.

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

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

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

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

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

1.«да» — условие выполнено.

2.«нет» — условие не выполнено.

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

Источник

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

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

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

Основными свойствами алгоритма являются:

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

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

3. Результативность(решение задачи, для которой разработан алгоритм должно быть достигнуто за конечное число шагов).

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

5. Конечность(каждое действие и алгоритм в целом должны иметь возможность завершения).

Алгоритм может быть сформулирован тремя различными способами:

1) Словесная формулировка алгоритма;

2) Формулировка в виде графической схемы (блок-схема);

3) Запись алгоритма в виде программы, записанной на одном из языков программирования.

Основные алгоритмические структуры:

1) Линейный алгоритм – описание действий, которые выполняются однократно в заданном порядке. Исполнитель выполняет действия последовательно, одно за другим в том порядке, в котором они следуют.

2) Цикличный алгоритм – описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие.

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

· Циклы со счетчиком, в которых какие-то действия выполняются определенное число раз (используют, когда заранее известно какое число повторений тела цикла необходимо выполнить);

· Циклы с условием, в которых тело цикла выполняется, в зависимости от какого-либо условия. Различают циклы с предусловием и постусловием.

3) Разветвляющий алгоритм –алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.

Условие – это высказывание, которое может быть либо истинно, либо ложно.
Существует две формы ветвления – неполная (когда присутствует только одна ветвь, т.е. в зависимости от истинности условия либо выполняется, либо не выполняется действие) и полная (когда присутствуют две ветви, т.е. в зависимости от истинности условия выполняется либо одно, либо другое действие).

Языки программирования, классификация языков программирования. Понятие о системе программирования.

Язык программирования – это фиксированная система обозначений для описания алгоритмов и структур данных.

Языки программирования – искусственные языки. От естественных они отличаются ограниченным числом «слов», значение которых понятно транслятору, и очень строгими правилами записи команд (операторов).

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

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

Интерпретатор (каждая инструкция, вводимая в ПК, сразу же преобразуется в машинный код и выполняется);

Компилятор (в машинный код переводится только вся программа в целом).

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

Язык машинных кодов и язык Ассемблера относятся к языкам низкого уровня, т.е. уровня приближенного к машинной логике.

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

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

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

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

Пример.

WriteLn(‘Введите через пробел два числа ‘);

WriteLn(‘Сумма чисел равна ‘,s);

Оператор присваивания. Выражение, приоритеты в выражениях.

Оператор присваивания – основной оператор любого языка программирования. Общая форма записи оператора:

имя величины := выражение

Например, V:=A; или V:=A+1;

переменная := выражение;

левая_часть := правая_часть;

Оператор работает справа налево, то есть сначала вычисляется то, что записано в правой части, а затем результат записывается «в левую часть».

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

Как только в программе встречается переменная, для неё в памяти отводится место. Оператор присваивания помещает значение переменной или значение выражения в отведённое место.

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

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

Тип переменной в левой части оператора присваивания обычно должен совпадать с типом значения выражения в правой части. Выражения являются составной частью операторов.

В Pascal выражения вычисляются в соответствии с приоритетами операций. Приоритеты выполнения операций следующие (в порядке убывания):

— операция NOT;

— операции типа умножения;

— операции типа сложения;

— операции сравнения (отношения).

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

Например, если в выражении … (X > 5) AND (Y > 10) … не поставить скобки, то будет синтаксическая ошибка, так как приоритет операции AND выше приоритета операций сравнения >.

операции типа умножения – это *, /, div, mod, and

операции типа сложения – это +, -, or, xor

операции сравнения – это <>, , =, in

Сравнение строк символов выполняется слева направо посимвольно. Более короткие строки дополняются пробелами справа.

Оператор цикла с заранее известным количеством повторений

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

В общем виде инструкция for записывается следующим образом:

for счетчик := нач_знач to кон_знач do

// здесь инструкции, которые надо выполнить несколько раз

Переменная счетчик, выражение нач_знач и кон_знач должны быть целого типа.

Если в инструкции for вместо слова to записать downto, то поле очередного выполнения инструкций тела цикла значение счетчика будет не увеличиваться, а уменьшаться.

Текстовые.

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

var Имя_переменной: text;

Имя_переменной – имя переменной, которая впоследствии будет связана с файлом;

text — соответствующий тип переменной.

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

Типизированные.

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

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

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

которого стирается после выхода из системы программирования, типизированный файл может длительное время сохраняться на жестком диске компьютера или на другом носителе. К каждому элементу такого

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

его нельзя просматривать и редактировать с помощью обычного текстового редактора.

Для того, чтобы в типизированный файл можно было производить

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

процедуры assign с файловой переменной подобно тому, как мы это уже

делали с текстовыми файлами. Например, так:

В общем виде описание файловой переменной для типизированного файла выглядит следующим образом:

var Имя_переменной: file of Тип;

Имя_переменной – имя переменной, связанной с типизированным

file – служебное слово;

Тип – тип элементов, из которых состоит данный файл.

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

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

read (Имя_переменной1, Имя_переменной2);

Имя_переменной1 –имя файловой переменной;

Имя_переменной2 – имя обычной переменной, относящейся к тому же типу, что и элементы типизированного файла.

Запись в файл производится оператором:

write (Имя_переменной1, Имя_переменной2);

Операторы writeln и readln для записи и чтения в типизированном файле использовать нельзя, так как данный тип не содержит строк.

Процедура seek (Имя_переменной, п);

seek – служебное слово, которое в переводе с англ. «искать»;

Имя_переменной – имя файловой переменной;

n – порядковый номер элемента в файле (нумерация начинается с нуля).

Если в ходе работы программы необходимо установить, какой элемент

файла является текущим, то для этого используется функция filepos.

Общий вид описания данной функции:

Аргументом данной функции является имя файловой переменной, а

значением – порядковый номер текущего элемента в файле.

Нетипизированные.

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

Описание нетипизированной файловой переменной имеет следующий общий вид:

var Имя_переменной: file;

Имя_переменной – имя связываемой с нетипизированным файлом файловой переменной.

Связывание файловой переменной с файлом производится так же, как и

для других файлов с помощью процедуры assign. Открытие файла для чтения и для записи производится, соответственно, процедурами reset и

rewrite. Формат этих процедур также аналогичен формату других видов

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

Для непосредственной записи информации в нетипизированный файл используется оператор blockwrite.

Общий вид данного оператора следующий:

blockwrite (Имя_переменной1, Имя_переменной,n);

Имя_переменной1 – имя файловой переменной;

Имя_переменной2 – имя вспомогательной переменной, из которой данные передаются в файл;

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

Чтение информации из файла производится оператором blockread.

Общий вид данного оператора:

blockread (Имя_переменной1, Имя_переменной2,n);

Имя_переменной1 – имя файловой переменной;

Имя_переменной2 – имя вспомогательной переменной, в которую передаются данные из файла;

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

Стандартные модули Паскаля.

В Турбо Паскале имеется 8 стандартных модулей, в которых содержится множество различных типов, констант, процедур и функций. Этими модулями являются SYSTEM, DOS, CRT, GRAPH, OVERLAY, TURBO3, GRAPH3. Модули Паскаля GRAPH, TURBO 3, GRAPH 3 выделены в отдельные TPU -файлы, а остальные входят в состав библиотечного файла TURBO.TPL. Лишь один модуль Паскаля SYSTEM подключается к любой программе автоматически, все остальные становятся доступны только после указания их имен в списке подключаемых модулей.

Модуль Паскаля SYSTEM. В него входят все процедуры и функции стандартного Паскаля, а также встроенные процедуры и функции, которые не вошли в другие стандартные модули (например, INC , DEC , GETDIR и т.п.). Модуль Паскаля SYSTEM подключается к любой программе независимо от того, объявлен ли он в предложении USES или нет, поэтому его глобальные константы, переменные, процедуры и функции считаются встроенными в Турбо Паскаль.

Модуль Паскаля PRINTER делает доступным вывод текстов на матричный принтер. В нем определяется файловая переменная LST типа TEXT , которая связывается с логическим устройством PRN.

Модуль Паскаля CRT.В нем сосредоточены процедуры и функции, обеспечивающие управление текстовым режимом работы экрана. С его помощью можно перемещать курсор в любую точку экрана, менять цвет выводимых символов и фона, создавать окна. Кроме того, в данный модуль включены также процедуры «слепого» чтения клавиатуры и управления звуком.

Модуль Паскаля GRAPH. Содержит набор типов, констант, процедур и функций для управления графическим режимом работы экрана. Этот модуль позволяет создавать различные графические изображения и выводить на экран надписи стандартными или созданными программистом шрифтами.

Модуль Паскаля DOS. В модуле собраны процедуры и функции, открывающие доступ к средствам дисковой операционной системы MS — DOS .

Модуль Паскаля OVERLAY. Данный модуль необходим при разработке громоздких программ с перекрытиями. Турбо Паскаль обеспечивает создание программ, длина которых ограничивается лишь основной оперативной памятью. Операционная система MS — DOS оставляет программе около 580 Кбайт основной памяти. Память такого размера достаточна для большинства исполняемых программ, тем не менее, использование программ с перекрытиями снимает это ограничение.

Модули Паскаля TURBO 3 и GRAPH 3 введены для обеспечения совместимости с ранней версией системы Турбо Паскаль.

Структура модулей Паскаля:

Unit ;
interface ;
implementation ;
begin
;
end.

Здесь UNIT – зарезервированное слово (единица); начинает заголовок модуля;

· — имя модуля (правильный идентификатор);

· INTERFACE – зарезервированное слово (интерфейс); начинает интерфейсную часть модуля;

· IMPLEMENTATION – зарезервированное слово (выполнение); начинает исполняемую часть модуля;

· BEGIN – зарезервированное слово; начинает инициирующую часть модуля; причем конструкция begin необязательна;

· END – зарезервированное слово – признак конца модуля.

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

Компиляция модулей Паскаля.

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

При компиляции модуля или основной программы в режиме COMPILE все, упоминаемые в предложении USES модули, должны быть предварительно откомпилированы, и результаты компиляции должны быть помещены в одноименные файлы с расширением TPU (от англ. Turbo Pascal Unit). Файл с расширением TPU создается автоматически при компиляции модуля Паскаля.

В режиме MAKE компилятор проверяет наличие TPU -файлов для каждого объявленного модуля. Если какой-либо файл не найден, система ищет одноименный файл с расширением PAS , т.е. файл с исходным текстом модуля Паскаля. Если таковой файл найден, система приступает к его компиляции. Кроме того, в этом режиме система следит за возможными изменениями исходного текста любого используемого модуля. Если в PAS -файл внесены изменения, то независимо от того, есть ли в каталоге соответствующий TPU -файл или нет, система откомпилирует его перед компиляцией основной программы. Более того, если изменения внесены в интерфейсную часть, то будут откомпилированы все другие модули, обращающиеся к нему. Режим MAKE существенно облегчает процесс разработки крупных программ с множеством модулей Паскаля: программист избавляется от необходимости следить за соответствием TPU -файлов их исходному тексту, т.к. система делает это автоматически.

В режиме BUILD существующие TPU -файлы игнорируются, система пытается отыскать и откомпилировать соответствующие PAS — файлы для каждого модуля Паскаля. После компиляции можно быть уверенным, что учтены все сделанные в текстах модулей Паскаля исправления и изменения.

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

Метод бинарного поиска

В случае, если массив упорядочен, то применяется метод бинарного поиска.

Метод (алгоритм) бинарного поиска реализуется следующим образом:

1. Сначала образец сравнивается со средним (по номеру) элементом массива;

· Если образец равен среднему элементу, то задача решена.

· Если образец больше среднего элемента, то это значит, что искомый элемент расположен ниже среднего элемента (между элементами с номерами sred+1 и niz) и за новое значение verh принимается sred+1, а значение niz не меняется.

· Если образец меньше среднего элемента, то это значит, что искомый элемент расположен выше среднего элемента (между элементами с номерами verh и sred-1) и за новое значение niz принимается sred-1, а значение verh не меняется.

2. После того как определена часть массива, в которой может находиться искомый элемент, по формуле (niz – verh)/2+verh вычисляется новое значение sred и поиск продолжается.

Алгоритм бинарного поиска заканчивает свою работу, если искомый элемент найден, или если перед выполнением очередного цикла поиска обнаруживается, что значение verh больше, чем niz.

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

Под сортировкой массива подразумевается процесс перестановки элементов массива, целью которого является размещение элементов массива в определенном порядке.

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

Сортировка методом обмена

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

Типизированные указатели

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

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

В общем виде объявление типизированного указателя выглядит след образом:

Имя_указателя: ^Тип;

Имя_указателя – имя переменноц-указателя;

Тип – тип переменной, на которую указывает переменная-указатель;

Значок ^ показывает, что объявляемая переменная является указателем.

Нетипизированные указатели

Чтобы хранить указатели, вам требуется переменная-указатель, а для создания переменной-указателя вам необходим ссылочный тип (или тип «указатель»). Простейшим ссылочным типом является стандартный тип с именем Pointer. Переменная типа Pointer — это общий (нетипизированный) указатель, то есть, просто адрес. Он не содержит информации о том, на что он указывает.

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

Списки

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

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

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

Упорядоченный список

Как правило, списки упорядочены. Порядок следования элементов в списке определяется содержимым одного из полей.

Удаление элемента из списка

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

Поскольку узел является динамической переменной, то после исключения узла из списка занимаемая им память должна быть освобождена. Освобождение динамической памяти, или, как иногда говорят, «уничтожение переменной», выполняется вызовом процедуры dispose (Delphi).

Очереди.

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

Например, пусть у нас есть очередь из трех элементов А,В,С, в которую первым был помещен элемент А, затем — элемент В, а последним — элемент С. После удаления элемента А первым элементом очереди будет элемент В. При этом элемент А остался в массиве на своем месте, но его уже нет в очереди, так как указатель начала очереди указывает на элемент В, т. е. следующий элемент массива. Если мы добавим в очередь новый элемент D, то он будет помещен в конец очереди, определяемый указателем конца. Очередь, в которой нет ни одного элемента, называется пустой. В этом случае оба указателя показывают на одно и то же место. Операции над очередями: Init — создает пустую очередь; Empty — возвращает значение true, если очередь пуста, и false в противном случае; Insert — добавляет элемент в конец очереди; Remove — удаляет элемент из начала очереди.

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

Бинарное дерево должно реализовывать следующие операции:

Инициализация бинарного дерева: текущий указатель устанавливается неопределенным (или нулевым, nil), а количество узлов нулевым.

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

Получение значения текущего элемента

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

Удаление узла из дерева

Уничтожение бинарного дерева

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

Объектно-ориентированное программирование (ООП) – это методика разработки программ, в основе которой лежит понятие объекта, как некоторой структуры, описывающей объект реального мира, его поведение.

Язык Object Pascal, поддерживая концепцию объектно-ориентированного программирования, дает возможность определять классы.

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

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

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

В Object Pascal ограничение доступа к полям объекта реализуется при помощи свойств объекта. Свойство объекта характеризуется полем, сохраняющим значение свойства, и двумя методами, обеспечивающими доступ к полю свойства. Метод установки значения свойства называется методом записи свойства (write), а метод получения значения свойства – методом чтения свойства (read).

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

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

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

Основными свойствами алгоритма являются:

5. Конечность(каждое действие и алгоритм в целом должны иметь возможность завершения).

Алгоритм может быть сформулирован тремя различными способами:

1) Словесная формулировка алгоритма;

2) Формулировка в виде графической схемы (блок-схема);

3) Запись алгоритма в виде программы, записанной на одном из языков программирования.

Основные алгоритмические структуры:

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

Источник