Основные сведения об алгоритмах
Содержание
Введение. 4
Общие положения. 4
Основные сведения об алгоритмах. 5
Язык Паскаль и интегрированные среды разработки программ. 11
Отладка и выполнение программы.. 18
Порядок выполнения лабораторных работ. 28
Лабораторная работа № 1. Программирование формул. 30
Таблица 4.1. Варианты заданий. 32
Лабораторная работа № 2. Ветвящиеся алгоритмы.. 35
Таблица 4.2. Варианты заданий. 37
Лабораторная работа № 3. Циклы с известным числом повторений 42
Таблица 4.3. Варианты заданий. 46
Лабораторная работа № 4. Циклы с заранее неизвестным числом повторений. 48
Таблица 4.4. Варианты заданий. 50
Лабораторная работа № 5. Средства вывода. Таблицы.. 53
Таблица 4.5. Варианты заданий. 56
Лабораторная работа № 6. Двойные и кратные циклы.. 58
Таблица 4.6. Варианты заданий. 59
Лабораторная работа № 7. Сортировка массивов. 62
Таблица 4.7. Варианты заданий. 67
Лабораторная работа № 8. Подпрограммы – функции. 69
Таблица 4.8. Варианты заданий. 71
Лабораторная работа № 9. Подпрограммы – процедуры.. 74
Таблица 4.9. Варианты заданий. 76
Лабораторная работа № 10. Работа с файлами и строками. 79
Таблица 4.10. Варианты заданий. 82
Лабораторная работа № 11. Динамические переменные. Списки 86
Таблица 4.11. Варианты заданий. 87
Лабораторная работа № 12. Графический режим монитора. Построение графиков. 89
Таблица 4.12. Варианты заданий. 92
Приложение А. Основные стандартные функции. 94
Таблица А.1. Стандартные функции ИСР Турбо-Паскаль, Free Pascal и Pascal ABC. 94
Приложение Б. Отличия языка ИСР PascalABC.NET от Delphi 99
Введение
Общие положения
Решение задачи на ЭВМ с составлением программы состоит из четырех этапов:
1. Постановка задачи.
2. Составление алгоритма.
3. Составление программы.
4. Ввод и отладка программы.
То есть, прежде чем приступать к непосредственному составлению программы или написанию последовательности операторов языка, необходимо отчетливо представить себе ход процесса вычислений, ту последовательность действий, которую должна реализовать программа. Первый этап не поддается строгой формализации и может быть достаточно сложным для больших задач, но в лабораторных работах постановка задачи приводится в самом задании.
Строгое представление последовательности действий, то есть алгоритм, наиболее удобно изображать графически с помощью блок-схем или граф-схем, хотя его можно представлять и другими способами, например словесно. На этапе обучения программированию использование детализированных блок-схем является обязательным.
Составление программы выполняется на каком-либо языке программирования. В данном курсе используется язык высокого уровня Паскаль. При составлении программы необходимо строго придерживаться правил записи программы, которые изложены в литературе, например, приведенной в списке в конце методических указаний.
Для ввода и отладки программы используется система программирования Турбо Паскаль, или Free Pascal, или Pascal ABC: краткие сведения о первой из них приводятся далее. Этот этап включает и тестирование программы, то есть проверку ее работоспособности при самых разнообразных условиях эксплуатации и вводимых данных.
При профессиональном программировании существует и пятый этап – сопровождение программы. Он заключается в исправлении замеченных в ходе работы с программой ошибок и изменениях по улучшению эксплуатационных свойств программы. Для больших программных комплексов (например, операционных систем) это один из самых трудоемких этапов, наряду с тестированием программы.
Язык Паскаль и интегрированные среды разработки программ
Хотя язык Паскаль является относительно старым языком программирования, созданным Никлаусом Виртом в 1968-69 годах специально для обучения студентов программированию, но с появлением персональных компьютеров он получил широкое распространение не только в образовательной сфере, но и при решении различных прикладных задач.
В 1986 году фирма Apple разработала объектное расширение языка Паскаль, получив в результате Object Pascal. Он был разработан группой Ларри Теслера, который консультировался с Никлаусом Виртом.
Турбо-Паскаль
В 1983 году появилась первая реализация инструментальной среды Турбо Паскаль, предназначенная для IBM-совместимых компьютеров. Она включала в себя оболочку (интерфейс, с помощью которого происходило общение человека с компьютером: набор и запуск программ, считывание результатов и т.д.), текстовый редактор, транслятор и отладчик. С тех пор система программирования Турбо Паскаль непрерывно совершенствовалась фирмой Borland International. Появилась развитая система подсказки, система сборки всей программы из отдельных модулей (линковщик), богатые библиотеки подпрограмм и многое другое. Комплекс программных средств, используемый программистами для разработки программного обеспечения, стали называть интегрированной инструментальной средой разработки программ (Integrated Development Environment, IDE, иногда именуемая ИСР),или просто средой программирования.
В 1992 году была представлена ИСР уже с использованием языка Object Pascal – Турбо-Паскаль 7.0. На этом развитие Турбо Паскаля закончилось. Окно ИСР Турбо-Паскаль представлено на рис.2.1.
Рис. 2.1. Создание нового окна программы в Турбо-Паскале
Free Pascal
Свободно распространяемые компиляторы системы программирования Free Pascal реализованы во многих дистрибутивах Linux, есть свободные компиляторы и для ОС Windows XP/7/10. На основе Free Pascal создана свободная мультиплатформенная среда Lazarus, аналогичная среде Delphi. Free Pascal внешне очень похож на Турбо Паскаль, хотя и является мультиплатформенным.
Начальная заставка этой ИСР приведена на рис.2.2.
Так как Free Pascal – свободно распространяемое ПО, то его можно скачать с сайта http://freepascal.org/ и бесплатно установить. На этом же сайте и находится вся документация по Free Pascal.
Рис.2.2. Начальная заставка Free Pascal.
Pascal АВС.NET
Эта ИСР наиболее приближена к профессиональной системе Delphi, то есть разработана без оглядки на старую ОС MS DOS. Как следствие, здесь присутствует панель инструментов, закладки для оперативного переключения между программами, 2 окна: ввода и вывода результатов. Учебная система программирования Pascal ABC.NET (автор – С.С. Михалкович) представляет собой диалект стандартного языка Паскаль. Она призвана осуществить постепенный переход от простейших программ к объектно-ориентированному программированию сложных программных продуктов уже на базе Delphi.
Начало работы в этой ИСР представлено на рис.2.3.
Хотя и считается, что интегрированная среда разработки Pascal АВС.NET полностью совместима с языком программирования Object Pascal, но это не так. В Pascal АВС.NET достаточно много изменений, указанных в приложении Б, взятых из языков Basic, C, а главное, с платформы .NET. Поэтому, хотя поначалу кажется, что язык, используемый в Pascal АВС.NET, такой же, что и Object Pascal, но это не так.
Конечно, в некоторых случаях проще написать короткую (учебную) программу в среде Pascal АВС.NET, но все-таки лучше использовать стандартный язык программирования.
В любом случае это так же свободно распространяемое ПО, находящееся на сайте http://pascalabc.net/.
Рис.2.3. Начало работы в Pascal АВС.
Delphi
Delphi является профессиональной средой программирования, хотя в его основе лежит всё тот же язык программирования Object Pascal. ИСР Delphi прошла долгий путь развития, начиная с Borland Delphi (1995 г.) для ОС Windows 3.1, затем для Windows 95 (еще 16-разрядных). Существовали версии Delphi с 2.0 до 8.0 (1996-2003 годы), Delphi 2005-2010 с соответствующими годами выпуска. Начиная с 2010 года стала выпускаются ИСР Delphi ХЕ, затем Delphi ХЕ2 (2011 год) и так далее.
Во введении будет кратко рассмотрена работа со средой Free Pascal. Работа с остальными ИСР очень похожа.
После того, как программа составлена, ее необходимо ввести в компьютер. Здесь мы и сталкиваемся с инструментальными пакетами программ Free Pascal или Pascal АВС. Free Pascal пакет содержит не только транслятор с языка Object Pascal, но и редактор текста, инструментальную оболочку, отладчик, описание ИСР, обширные библиотеки программ и многое другое, например, программы примеров объектно-ориентированного программирования.
Для связи основных из этих программ в единое целое, создания удобного и наглядного интерфейса и предназначена интегрированная инструментальная среда разработки программ, кратко ИСР.
Вызов ИСР осуществляется посредством запуска либо с рабочего стола, либо с помощью кнопки меню «Пуск» файла fp.exe. После запуска файла fp.exe появляется основной экран ИСР, состоящий из трех частей: строки меню, рабочей зоны и строки состояния в соответствии с рис.2.2.
При начальном запуске ИСР в рабочей зоне открыто одно окно с номером 1 в правом верхнем углу и с заголовком noname01.pas. В дальнейшем, после записи программы на диск, стандартный заголовок заменится на имя программы, данное ей при записи. Если рабочая зона пустая, то создается новое окно командой File > New, как представлено на рис. 2.4.
Рис. 2.4. Вид окна ИСР после запуска файла fp.exe в оконном режиме
Мигающий курсор указывает то место на экране, в котором будет появляться очередной символ текста. Ввод каждой новой строки заканчивается нажатием клавиши Enter. Компилятор не различает прописные и строчные буквы, поэтому все равно, в каком регистре набираются латинские буквы. Так, следующие строки будут эквивалентными:
Program A;
PROGRAM a;
PrOgRaM a;
Набирая текст, особое внимание необходимо обращать на точное воспроизведение всех знаков: точек, точек с запятой, апострофов, пробелов, так как компилятор очень чувствителен к мелочам подобного рода.
Строка меню активизируется клавишей F10 (если управление осуществляется с клавиатуры) и состоит из 10 пунктов, которые, в свою очередь, разворачиваются в спускающиеся подменю:
File– позволяет выполнять все основные операции с файлами: создавать новые, загружать имеющиеся, сохранять созданные и отредактированные файлы, выводить на принтер содержимое этих файлов, заканчивать сеанс с ИСР и так далее.
Edit– дает возможность выполнять основные операции редактирования текста.
Search– позволяет осуществлять поиск фрагментов текста и при необходимости производить замену найденного фрагмента новым.
Run– позволяет запускать программу, находящуюся в рабочей зоне, а так же при необходимости пошагово выполнять данную программу или ее часть. Если были внесены изменения в программу, то при запуске она автоматически заново компилируется.
Compile– возможно осуществить компиляцию программы, которая находится в рабочей зоне, без ее выполнения, чтобы проверить на наличие ошибок.
Debug– содержит команды, облегчающие процесс поиска ошибок в программе: расстановка точек остановки, визуализация окна отладки, окна регистров, окна выходных результатов и так далее.
Tools– дает возможность выполнять некоторые программы, не выходя из ИСР.
Options– здесь находятся команды, позволяющие установить необходимые для работы параметры компилятора и ИСР.
Window– позволяет выполнять все основные операции с окнами (хотя их гораздо удобнее выполнять с помощью мыши): открывать, закрывать, перемещать, изменять размер.
Help – позволяет получить имеющуюся в системе справочную информацию.
Система меню позволяет выполнять практически все команды ИСР и интегрированных программ, и выполнена в соответствии со стандартом SAA (Turbo Vision).
Строка состояния, находящаяся в нижней части экрана, в режиме редактирования демонстрирует некоторые из часто используемых операций ИСР и комбинации клавиш для их быстрого вызова, которые позволяют выполнить соответствующие операции, минуя стандартную процедуру их вызова через меню. В некоторых режимах здесь выводятся подсказки или другая справочная информация.
Предусмотрены в этой среде и всплывающие подсказки, например, на рис.2.5 (в рамке серого (зеленого) цвета подсказка служебного слова Program).
Рис. 2.5. Всплывающие подсказки в Free Pascal.
Требования к лабораторным работам.
1. Не забывайте, что в языке Паскаль используются только латинские буквы: нет ни кириллицы (кроме строк вывода и комментариев), ни греческого алфавита.
2. Не надо дополнительно преобразовывать выражения. То есть все вычисления надо выполнять именно по тем формулам, которые приведены.
3. Числа должны быть выведены с фиксированной точкой, и количеством цифр после точки 3-6, в зависимости от размера числа или от заданной точности, с кратким пояснением выводимого числа, например:
c= 1.2345
Альфа = 0.012345
Варианты задания приведены в табл. 4.1.
Таблица 4.1. Варианты заданий
| № вар. | Вычислить выражение | При заданных значениях |
 |  | |
 |  | |
 |    | |
 |  | |
 |  | |
 |  | |
 |  | |
 |  | |
 |  | |
 |  | |
 |  | |
 |  | |
| № вар. | Вычислить выражение | При заданных значениях |
 |  | |
 |  | |
 |  | |
 |  | |
 |  | |
 |  | |
 |  | |
 |  | |
 |  | |
 |   | |
 |  | |
| № вар. | Вычислить выражение | При заданных значениях |
 |   | |
 |    | |
 |   | |
 |  | |
 |  | |
 |  | |
  |    |
Таблица 5.1. Варианты заданий.
1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10. 
11. 
12. 
13. 
14. 
15. 
16. 
17. 
18. 
19. 
20. 
21. 
22. 
23. 
24. 
25. 
26. 
27. 
28. 
29. 
30. 
Лабораторная работа № 3.
Циклы с известным числом повторений
Целью работы является освоение программирования алгоритмов с циклической структурой, когда какой-либо участок программы выполняется определенное количество раз.
Типичный пример циклического процесса – вычисление конечных сумм. При определении сумм многократно вычисляется выражение, стоящее под знаком суммы и складывается с предыдущей частичной суммой. Вычисления производятся до тех пор, пока не будут сложены выражения под знаком суммы для всех значений изменяющейся переменной.
Пример: составить программу, вычисляющую значение суммы:
Прежде чем вычислять выражение под знаком суммы и очередную частичную сумму, необходимо определить начальное значение параметра цикла (в данном случае i, которое изменяется от 1 до 10 с шагом 1, то есть i будет принимать последовательно значения 1, 2, 3, 4, ..., 9, 10), и начальную частичную сумму S. Так как вычисления еще не производились, то S = 0.
Затем вычисляется выражение под знаком суммы для i = 1, затем i = 2, 3, ... до 10 и каждый раз складывается с предыдущей частичной суммой S i-1. При этом получается новая частичная сумма S i. После этого i увеличивается на единицу и проверяется, не стало ли i > 10. Если еще меньше или равно 10, то вычисляется новая частичная сумма, в противном случае вычисление суммы будет закончено, и это значение выводится на печать.
Воспользуемся стандартной схемой циклического процесса, представленной на рис.6.1.
Блок 1 – блок подготовки к вычислению суммы, в котором задаются начальные значения параметра цикла и частичной суммы.
В блоке 2 производится вычисление выражения, стоящего под знаком суммы и сложение с предыдущей частичной суммой S i-1. В итоге получается новая частичная сумма S i.
В блоке 3 происходит изменение параметра цикла (увеличение i на 1). Это блок подготовки к новому циклу.
Блок 4 – блок проверки окончания цикла. Необходимо проверить, стало ли i больше 10. Если стало, то цикл закончен, следующим должен выполняться блок печати. Если нет, то вычисление частичной суммы продолжается дальше, то есть выполняются блоки 2 и 3.
Проверка может осуществляться условным оператором IF, но для организации циклов в языке Паскаль специально предусмотрены три оператора цикла. Если количество повторений заранее известно, и параметр является целым числом, то целесообразно использовать оператор FOR, включающий в себя блоки 1, 3, 4. В этом случае в алгоритме можно применить блок «Модификация».
Алгоритм для примера с использованием оператора FOR приведен на рис.6.2. Варианты заданий – в табл.6.1.
Рис. 6.1. Блок-схема алгоритма циклического процесса
Рис. 6.2. Блок-схема алгоритма примера.
Таблица 6.1. Варианты заданий
| № вар. | Вычислить сумму | № вар. | Вычислить сумму |
 |  | ||
 |  | ||
 |  | ||
 |  | ||
 |  | ||
 |  | ||
 |  | ||
 |  | ||
 |  | ||
 |  | ||
 |  | ||
| № вар. | Вычислить сумму | № вар. | Вычислить сумму |
 |  | ||
 |  | ||
 |  | ||
 |  |
Лабораторная работа № 4.
Циклы с заранее неизвестным числом повторений
Целью работы является освоение программирования алгоритмов с циклической структурой и выхода из цикла по условию, не зависящему от количества циклов. Примером такой задачи является вычисление суммы с бесконечным верхним пределом.
Проверка цикла осуществляется следующим образом. Так как выражение под знаком суммы постепенно убывает с ростом слагаемых в сумме (условие сходимости), то наступает момент, когда очередное слагаемое станет меньше наперед заданного числа e (грубо говоря, точности вычисления сумм), и остальные слагаемые будут мало влиять на конечный результат. Поэтому, когда выражение под знаком суммы | f (i) | будет меньше e, то вычисления прекращаются и предполагается, что сумма найдена с заданной точностью.
Так как количество слагаемых заранее неизвестно, то циклом FOR пользоваться нельзя. Для этих целей предназначаются циклические операторы WHILE и REPEAT. Необходимо помнить, что у этих операторов параметр цикла автоматически не изменяется, и его надо менять принудительно. Поэтому при составлении блок-схемы алгоритма блок «Модификация» не используется.
При вычислении суммы должен вычисляться факториал по формуле:
Где П – знак произведения (аналогично знаку суммы), то есть 5! = 1· 2· 3· 4· 5 = 120. Факториал можно вычислить отдельным циклом, а можно и в цикле вычисления суммы. Для этого вводится дополнительная переменная, например f = j !, и затем в цикле умножается на текущее значение j.
Кроме значения суммы на печать полезно вывести значение счетчика циклов, то есть узнать, из скольких слагаемых состоит сумма.
Варианты заданий приведены в табл.7.1.
Примечание. В языке Турбо Паскаль под переменные типа INTEGER выделяется два байта, и допустимые для них значения находятся в диапазоне только от -32768 до 32767. Поэтому число 10!, реально равное 3628800, в этом случае будет представлено как 24320. Таким образом, выражение под знаком суммы может никогда и не стать меньше заданной точности. Для работы с большими целыми числами рекомендуется использовать вещественный тип REAL с диапазоном представления от 2.9·10-39 до 1.7·1038, или, в крайнем случае, целый тип LongInt с диапазоном от ‑2.147.483.648 до 2.147.483.647.
Таблица 7.1. Варианты заданий
| № вар. | Вычислить | При х, равном | Точность вычислений e |
 | 0,149 | 10 -5 | |
 | 5,99 | 10 -3 | |
 | 3,1 | 10 -4 | |
 | 1,91 | 10 -5 | |
 | 1,42 | 10 -3 | |
 | 0,99 | 10 -4 | |
 | 1,51 | 10 -5 | |
 | 3,48 | 10 -3 | |
 | 7,55 | 10 -4 | |
 | 2,15 | 10 -5 | |
 | 0,81 | 10 -3 | |
| № вар. | Вычислить | При х, равном | Точность вычислений e |
 | 0,77 | 10 -4 | |
 | 3,95 | 10 -5 | |
 | 1,62 | 10 -3 | |
 | 4,14 | 10 -4 | |
 | 1,24 | 10 -5 | |
 | 3,3 | 10 -3 | |
 | 2,8 | 10 -4 | |
 | 0,95 | 10 -5 | |
 | 4,5 | 10 -3 | |
 | 0,85 | 10 -4 | |
 | 2,4 | 10 -5 | |
 | 1,7 | 10 -3 | |
| № вар. | Вычислить | При Х, равном | Точность вычислений e |
 | 4,2 | 10 -4 | |
 | 2,2 | 10 -5 | |
 | 3,1 | 10 -3 | |
 | 10 -4 | ||
 | 8,5 | 10 -5 | |
 | 0,15 | 10 -3 | |
 | 2,9 | 10 -4 |
Лабораторная работа № 5.
Средства вывода. Таблицы
При выводе больших объемов информации для удобства чтения ее необходимо оформлять в виде таблиц или графиков. Целью работы является изучение операторов ввода-вывода, вывод чисел в заданном виде и с определенной точностью, вывод последовательности чисел, оформленных в виде таблиц.
Таблица состоит из заголовка, в котором указано, что, в каком столбце расположено, и непосредственно таблицы набора значений выводимых переменных. При выводе заголовка таблицы используется текстовая информация. Поэтому, чтобы правильно напечаталась таблица, необходимо сделать ее макет.
Макет таблицы рисуется на бумаге в клетку, и каждая клетка принимается за одну позицию. При этом учитывается, где расположена таблица, то есть, сколько позиций надо отступить от левого края листа, каким образом проводятся вертикальные и горизонтальные линии (обычно вертикальные – набор знаков I или !, горизонтальные – знаки минус или подчеркивание). Определяется ширина таблицы, которая зависит от количества выводимых значений и точности, с какой эти значения выводятся (длина числа зависит от количества цифр в числе). После этого, символ за символом, в операторы вывода заносится с макета информация о том, как должен выглядеть заголовок таблицы.
Далее следует обычный циклический процесс с выводом в каждом цикле строки таблицы с рассчитанными значениями величин. Здесь оператор вывода наряду с текстовой информацией (вертикальная черта и пробелы), будет содержать и числовые значения.
После вывода таблицы ее необходимо подчеркнуть, то есть вывести заключительную горизонтальную линию, состоящую, например, из набора знаков минус.
Все кодовые таблицы символов имеют и символы псевдографики. Это такие символы, как вертикальная черта, прямой угол, перекрестье и т.д., например: │, └, ┘, ║, ╬, ╙. Если знать сочетания клавиш для символов псевдографики, то изображение таблиц получается лучше. Но это требуется не всегда, например, для данной лабораторной работы достаточно знаков, таких, как латинское «I» большое или восклицательный знак «!», и тире «–» или символ подчеркивания «_».
Пример. Вывести таблицу значений функции 
с точностью 7 знаков после запятой, причем х изменяется от 2 до 9 с шагом 1.
Блок-схема алгоритма представлена на рис. 8.3, полученный результат на рис. 8.1, вариант результата – на рис. 8.2.
-------------------
I X I SQRT(X) I
-------------------
I 2 I 1.4142132 I
I 3 I 1.7320509 I
I 4 I 2.0000000 I
I 5 I 2.2360678 I
I 6 I 2.4494896 I
I 7 I 2.6457510 I
I 8 I 2.8284273 I
I 9 I 3.0000000 I
-------------------
Рис.8.1.Распечатка результата счета по программе для вывода таблиц.
┌─────┬───────────┐
│ Х │ SQRT(X) │
├─────┼───────────┤
│ 2 │ 1.4142132 │
│ 3 │ 1.7320509 │
│ 4 │ 2.0000000 │
│ 5 │ 2.2360678 │
│ 6 │ 2.4494896 │
│ 7 │ 2.6457510 │
│ 8 │ 2.8284273 │
│ 9 │ 3.0000000 │
└─────┴───────────┘
Рис 8.2. Вывод таблиц с использованием символов псевдографики.
Рис.8.3. Блок-схема алгоритма для примера.
Таблица 8.1. Варианты заданий
| № вар. | Функции | Начальное значение х | Конечное значение х | Шаг изменения х |
 | 0,2 | 1,7 | 0,1 | |
 | ||||
 | 0,05 | |||
 | ||||
 | 0,05 | |||
 | 0,5 | |||
 | 0,5 | |||
 | 0,1 | 0,1 | ||
 | 0,2 | |||
 | 0,1 | 0,05 | ||
 | 0,1 | 0,1 | ||
 | 0,05 | 0,05 | ||
 | 0,05 | 0,05 | ||
 | 0,05 | |||
 | 0,5 | |||
 | 0,05 | |||
 | -1 | 0,1 | ||
 | -2 | 0,2 | ||
 | ||||
| № вар. | Функции | Начальное значение х | Конечное значение х | Шаг изменения х |
 | 0,2 | |||
 | 0,05 | |||
 | 0,05 | |||
 | 0,1 | 0,05 | ||
 | 0,1 | |||
 | 0,1 | |||
 | 0,1 | 1,5 | 0,1 | |
| |