Понятие алгоритма, его свойства, этапы разработки, способы представления алгоритмов
Содержание
Требования к отчету. 3
ТЕМА 1. Алгоритмизация задач. 4
1.1. Понятие алгоритма, его свойства, этапы разработки, способы представления алгоритмов. 4
1.2. Перечень, наименование, обозначение блоков и отображаемые ими функции. 5
ТЕМА 2. Интегрированная инструментальная оболочка PascalABC. Работа с главным меню системы PascalABC.. 7
2.1. Среда программирования Pascal ABC. 7
ТЕМА 3. Общая структура программ в Pascal. 11
3.1. Основные части программы. 11
ТЕМА 4. Оператор ввода-вывода в Pascal. Описание некоторых стандартных типов данных и встроенные операции и функции, применимые к ним.. 14
4.1. Операторы ввода/вывода данных. 14
4.2. Стандартные типы данных. 15
ТЕМА 5. Программирование линейных алгоритмов. 17
5.1. Понятие линейного алгоритма. Примеры написания программ. 17
ТЕМА 6. Программирование с помощью операторов условного и безусловного перехода. 19
6.1. Условный оператор If. 19
6.2. Оператор безусловного перехода GoTo. 20
ТЕМА 7. Оператор выбора Case. 22
ТЕМА 8. Циклические программы.. 24
8.1. Оператор For 24
8.2. Оператор Repeat 25
8.3. Оператор While. 26
ТЕМА 9. Массивы.. 27
9.1. Линейные массивы. Описание типа. 27
9.2. Многомерные массивы. Двухмерные массивы – матрицы. 27
ТЕМА 10. расчет отметок проектной линии на вертикальной выпуклой или вогнутой кривой. 30
10.1. Индивидуальные задания. 30
ТЕМА 11. Процедуры и функции, определенные пользователем. Параметры процедур и функций. 32
11.1. Глобальные и локальные переменные, параметры процедур и функций. 32
11.2. Процедуры пользователя. 33
11.3. Функции пользователя. 34
ТЕМА 12. Символьные массивы. Строки. 36
12.1. Символьный тип. 36
12.2. Символьные массивы.. 36
12.3. Строки. Объявление строчных типов и переменных. 36
12.4. Определения значения строковой переменной. 37
12.5. Длина строки. Операция конкатенации. 37
12.6. Функции для работы со строками. 37
12.7. Процедуры для работы со строками. 38
Требования к отчету
Отчет по работе должен содержать:
-название, цель работы;
-номер варианта для выполнения задания и условие своего варианта;
-блок-схему решения задачи;
-текст (листинг) программы;
-полученные при расчетах численные результаты;
-ответы на контрольные вопросы по указанию преподавателя.
ТЕМА 1. Алгоритмизация задач
Цель лабораторной работы: ознакомиться с понятием алгоритма и алгоритмизацией задач. Научиться составлять алгоритмы решения задач на компьютере в виде блок-схем.
Понятие алгоритма, его свойства, этапы разработки, способы представления алгоритмов.
Алгори́тм – это точный набор инструкций, описывающих последовательность и порядок действий исполнителя для достижения результата решения задачи за конечное время. Какие-то действия алгоритма должны быть выполнены только друг за другом, но какие-то могут быть и независимыми. Алгоритм – это конечная последовательность действий, приводящая к определенному результату.
1. массовость – алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, различающихся только исходными данными;
2. определенность алгоритма – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвольного толкования;
3. понятность – должен включать команды, которые входят в систему команд исполнителя;
4. дискретность – это свойство алгоритма, обеспечивающее возможность разбиения вычислительного процесса на отдельные самостоятельные этапы
5. результативность (конечность) – при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов.
6. эффективность – для решения задачи должны использоваться ограниченные ресурсы компьютера (процессорное время, объём оперативной памяти и т. д.).
Этапы разработки и решения задач на ЭВМ:
- постановка задачи;
- моделирование;
- алгоритмизация задачи;
- программирование;
- ввод программы и исходных данных в ЭВМ;
- тестирование и отладка программы;
- исполнение отлаженной программы и анализ результатов.
Способы представления алгоритмов:
2. структурированная схема алгоритма — графическое изображение алгоритма в виде схемы связанных между собой с помощью стрелок (линий перехода) блоков – графических символов, каждый из которых соответствует одному шагу алгоритма. Внутри блока дается описание соответствующего действия;
3. алгоритмический язык.
Представление алгоритмов в виде структурированных блок-схем.
Основные структуры алгоритмов:
1. линейные алгоритмы – это алгоритмы, в которых действия выполняются последовательно друг за другом.
2. условные алгоритмы – алгоритм, содержащий хотя бы одно условие, в результате проверки которого обеспечивается переход на один из двух возможных шагов.
3. алгоритмы с повторением (циклический алгоритм) – алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными. К циклическим алгоритмам сводится большинство методов вычислений, перебора вариантов.
Источник
Понятие алгоритма. Виды алгоритмов
Существует несколько определений понятия алгоритма. Приведем два самых распространенных.
Алгоритм – последовательность чётко определенных действий, выполнение которых ведёт к решению задачи. Алгоритм, записанный на языке машины, есть программа решения задачи.
Алгоритм – это совокупность действий, приводящих к достижению результата за конечное число шагов.
Вообще говоря, первое определение не передает полноты смысла понятия алгоритм. Используемое слово «последовательность» сужает данное понятие, т.к. действия не обязательно должны следовать друг за другом – они могут повторяться или содержать условие.
- Дискретность (от лат. discretus — разделенный, прерывистый) – это разбиение алгоритма на ряд отдельных законченных действий (шагов).
- Детерминированность (от лат. determinate — определенность, точность) — любое действие алгоритма должно быть строго и недвусмысленно определено в каждом случае. Например, алгоритм проезда к другу, если к остановке подходят автобусы разных маршрутов, то в алгоритме должен быть указан конкретный номер маршрута 5. Кроме того, необходимо указать точное количество остановок, которое надо проехать, скажем, три.
- Конечность – каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения.
- Массовость – один и тот же алгоритм можно использовать с разными исходными данными.
- Результативность – алгоритм должен приводить к достоверному решению.
Основная цель алгоритмизации – составление алгоритмов для ЭВМ с дальнейшим решением задачи на ЭВМ.
- Любой прибор, купленный в магазине, снабжается инструкцией по его использованию. Данная инструкция и является алгоритмом для правильной эксплуатации прибора.
- Каждый шофер должен знать правила дорожного движения. Правила дорожного движения однозначно регламентируют поведение каждого участника движения. Зная эти правила, шофер должен действовать по определенному алгоритму.
- Массовый выпуск автомобилей стал возможен только тогда, когда был придуман порядок сборки машины на конвейере. Определенный порядок сборки автомобилей – это набор действий, в результате которых получается автомобиль.
Существует несколько способов записи алгоритмов. На практике наиболее распространены следующие формы представления алгоритмов:
- словесная (запись на естественном языке);
- псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
- графическая (изображения из графических символов – блок-схема);
- программная (тексты на языках программирования – код программы).
Рассмотрим подробно каждый вариант записи алгоритмов на примере следующей задачи. Требуется найти частное двух чисел.
Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке. Ответ при этом получает человек, который выполняет команды согласно словесной записи.
Пример словесной записи:
- задать два числа, являющиеся делимым и делителем;
- проверить, равняется ли делитель нулю;
- если делитель не равен нулю, то найти частное, записать его в ответ;
- если делитель равен нулю, то в ответ записать «нет решения».
Словесный способ не имеет широкого распространения, так как такие описания: строго не формализуемы; страдают многословностью записей; допускают неоднозначность толкования отдельных предписаний.
Псевдокод занимает промежуточное место между естественным и формальным языками. С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой стороны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи. В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя. Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. Ответ при этом получает человек, который выполняет команды согласно псевдокоду.
Приведем основные управляющие структуры псевдокода в табл. 1.1.
Источник
Понятие алгоритма, свойства алгоритмов, способы записи алгоритма, основные алгоритмические структуры.
Понятие алгоритма, свойства алгоритмов, способы записи алгоритма, основные алгоритмические структуры.
Алгоритм – последовательность инструкций, правильное выполнение которых ведет к решению поставленной задачи.
Основными свойствами алгоритма являются:
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).
Концепция объектно-ориентированного программирования предполагает возможность определять новые классы посредством добавления полей, свойств и методов к уже существующим классам. Такой механизм получения новых классов называется порождением. При этом новый, порожденный класс (поток) наследует свойства и методы своего базового, родительского класса.
Полиморфизм – это возможность использовать одинаковые имена для методов, входящих в различные классы. Концепция полиморфизма обеспечивает в случае применения метода к объекту использования именно того метода, который соответствует классу объекта.
Понятие алгоритма, свойства алгоритмов, способы записи алгоритма, основные алгоритмические структуры.
Алгоритм – последовательность инструкций, правильное выполнение которых ведет к решению поставленной задачи.
Основными свойствами алгоритма являются:
1. Однозначность(предписания алгоритма должны быть сформулированы таким образом, чтобы не допускалось никакой двусмысленности в их толковании).
2. Дискретность(алгоритм должен быть разделен на ряд инструкций, шагов, каждый из которых представляет собой отдельное законченное действие).
3. Результативность(решение задачи, для которой разработан алгоритм должно быть достигнуто за конечное число шагов).
4. Массовость(правильно разработанный алгоритм может использоваться для решения целого класса сходных между собой задач, которые отличаются друг от друга только значениями исходных параметров).
5. Конечность(каждое действие и алгоритм в целом должны иметь возможность завершения).
Алгоритм может быть сформулирован тремя различными способами:
1) Словесная формулировка алгоритма;
2) Формулировка в виде графической схемы (блок-схема);
3) Запись алгоритма в виде программы, записанной на одном из языков программирования.
Основные алгоритмические структуры:
1) Линейный алгоритм – описание действий, которые выполняются однократно в заданном порядке. Исполнитель выполняет действия последовательно, одно за другим в том порядке, в котором они следуют.
2) Цикличный алгоритм – описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие.
Перечень повторяющихся действий называют телом цикла.
Циклические алгоритмы бывают двух типов:
· Циклы со счетчиком, в которых какие-то действия выполняются определенное число раз (используют, когда заранее известно какое число повторений тела цикла необходимо выполнить);
· Циклы с условием, в которых тело цикла выполняется, в зависимости от какого-либо условия. Различают циклы с предусловием и постусловием.
3) Разветвляющий алгоритм –алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.
Условие – это высказывание, которое может быть либо истинно, либо ложно.
Существует две формы ветвления – неполная (когда присутствует только одна ветвь, т.е. в зависимости от истинности условия либо выполняется, либо не выполняется действие) и полная (когда присутствуют две ветви, т.е. в зависимости от истинности условия выполняется либо одно, либо другое действие).
Источник
