Алгоритмы и алфавит языка Турбо Паскаль. Основные типы данных. Операторы присваивания, перехода и выбора. Понятие массива в Паскале. Особенности работы со строками в программе. Использование линейного поиска и поиска с барьером. Основные виды сортировок.
Первая версия языка Паскаль была разработана швейцарским ученым Никлаусом Виртом в 1968 году. Первоначально язык предназначался для целей обучения, поскольку он является достаточно детерминированным, т.е. все подчиняется определенным правилам, исключений из которых не так много. Основные характеристики: относительно небольшое количество базовых понятий, простой синтаксис, быстрый компилятор для перевода исходных текстов в машинный код.
В 1992 г. фирма Borland International выпустила два пакета, основанных на языке Паскаль: Borland Pascal 7.0 и Turbo Pascal 7.0. Первый может работать в трех режимах - обычном и защищенном режимах MS DOS и в системе Windows. Для него необходимо порядка 30 Мбайт на жестком диске и около 2 Мбайт оперативной памяти. Турбо Паскаль 7.0 работает только в обычном режиме MS DOS и менее требователен к характеристикам компьютера. Поскольку основные компоненты, которые мы будем рассматривать в нашем курсе, совпадают в обоих продуктах, в дальнейшем будет использоваться название Турбо Паскаль.
Пакет включает в себя алгоритмический язык программирования высокого уровня, встроенный редактор и среду, предназначенную для отладки и запуска программ. Кроме того, пакет содержит большой объем справочной информации (англоязычной). Как известно, языки программирования делятся на два типа: интерпретаторы и компиляторы. Турбо Паскаль относится к компиляторным языкам.
ОСНОВЫ ЯЗЫКА
АЛГОРИТМЫ
Алгоритмом называют описание последовательности действий, необходимых для решения определенной задачи. Основными характеристиками алгоритма являются вычислительная сложность и емкостная сложность. Вычислительная или, иначе, временная сложность алгоритма - это количество элементарных операций в процессе его выполнения. Различают вычислительную сложность в среднем и в худшем случае. Емкостная сложность алгоритма - это объем используемых данных, а также объем кода самой программы. При создании алгоритма целью является сокращение как его вычислительной, так и емкостной сложности.
Алгоритмы могут записываться различными способами, например, в виде блок-схем или в виде программ. Программа это набор указаний исполнителю, т.е. в нашем случае - компьютеру.
АЛФАВИТ ЯЗЫКА
Под алфавитом языка понимают совокупность допустимых символов. В языке Турбо Паскаль используются символы ASCII (американский стандартный код обмена информацией). Можно выделить четыре основные группы символов: символы, используемые в идентификаторах, разделители, специальные символы и неиспользуемые символы.
Идентификатор - это имя любого объекта языка. Он может состоять из латинских букв (a...z), цифр (0...9) и знака подчеркивания и не должен начинаться с цифры. Прописные и строчные буквы в идентификаторах и зарезервированных словах считаются идентичными, они различаются лишь в строковых константах. Длина идентификатора не ограничена, но значимыми являются лишь первые 63 символа.
Разделители используются для отделения друг от друга идентификаторов, чисел и зарезервированных слов. К разделителям относятся, например, пробел и комментарий. В любом месте программы, где разрешается один пробел, их можно вставить любое количество.
Комментарии заключаются либо в фигурные скобки { комментарий 1 }, либо в символы (* комментарий 2 *) и могут занимать любое количество строк. Последовательность из трех символов (*) начинает комментарий до конца строки. Текст комментария игнорируется при компиляции, если это не директивы компилятора, которые имеют вид {$ }.
ПРИМЕР : (*Допустимый {{{в (* программе} комментарий*).
(*Недопустимый {{{в (* программе*) комментарий*).
К специальным знакам относятся знаки пунктуации (. () [] .. : ;), знаки операций и зарезервированные слова. Знаки операций могут быть как символьные ( ,-,*,/ и т.д.), так и буквенными (mod, div, not). Зарезервированные слова являются служебными и не могут быть переопределены пользователем, т.е. их нельзя использовать как имена пользовательских объектов. Неиспользуемые символы - это коды ASCII, которые используются только в комментариях и символьных строках, но не в языке. К ним относятся все русские буквы, а также символы %, &, ! и т.п.
СТРУКТУРА ПРОГРАММЫ
В программе, написанной на Турбо Паскале, могут быть следующие разделы: Program ... ; { Заголовок программы }
Uses ... ; { Подключение модулей }
Label ... ; { Раздел объявления меток }
Const ... ; { Раздел объявления констант }
Type ... ; { Раздел объявления новых типов }
Var ... ; { Раздел объявления переменных }
Procedure ... ; { Описание своих процедур }
Function ... ; { Описание своих функций }
Begin { начало основной программы }
...;
{ Операторы }
...;
End.
Обязательной частью является лишь тело программы, которое начинается словом begin, а заканчивается словом end с точкой. Операторы в Паскале разделяются точкой запятой.
План
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ОСНОВЫ ЯЗЫКА
АЛГОРИТМЫ
АЛФАВИТ ЯЗЫКА
СТРУКТУРА ПРОГРАММЫ
ТИПЫ ДАННЫХ
Целые типы
Вещественные типы
Логический тип
Символьный тип
ВЫРАЖЕНИЯ
СОВМЕСТИМОСТЬ ТИПОВ ДАННЫХ
ЛИНЕЙНЫЕ АЛГОРИТМЫ
ПУСТОЙ И СОСТАВНОЙ ОПЕРАТОРЫ
ОПЕРАТОР ПРИСВАИВАНИЯ
ПРОСТЕЙШИЙ ВВОД И ВЫВОД
РАЗВЕТВЛЯЮЩИЕСЯ АЛГОРИТМЫ
ОПЕРАТОР ПЕРЕХОДА
УСЛОВНЫЙ ОПЕРАТОР
ОПЕРАТОР ВЫБОРА
ЦИКЛИЧЕСКИЕ АЛГОРИТМЫ
ЦИКЛЫ С ПАРАМЕТРОМ.
ЦИКЛЫ С УСЛОВИЕМ.
ПОЛЬЗОВАТЕЛЬСКИЕ ТИПЫ ДАННЫХ
ПЕРЕЧИСЛЯЕМЫЙ ТИП
ТИП-ДИАПАЗОН
МАССИВЫ
ЗАПИСИ
РАБОТА СО СТРОКАМИ
ПРОЦЕДУРЫ И ФУНКЦИИ
Параметры-значения
Параметры-переменные
Параметры-константы
ОТКРЫТЫЕ ПАРАМЕТРЫ-МАССИВЫ
БЕСТИПОВЫЕ ПАРАМЕТРЫ
ПРОЦЕДУРНЫЕ ТИПЫ
РЕКУРСИЯ
ТИПИЗИРОВАННЫЕ КОНСТАНТЫ
МОДУЛИ
АЛГОРИТМЫ ПОИСКА
ЛИНЕЙНЫЙ ПОИСК
ПОИСК С БАРЬЕРОМ
ДВОИЧНЫЙ (БИНАРНЫЙ) ПОИСК
АЛГОРИТМЫ СОРТИРОВКИ
СОРТИРОВКА ВЫБОРОМ
СОРТИРОВКА ОБМЕНОМ (методом "пузырька")
ШЕЙКЕРНАЯ СОРТИРОВКА
СОРТИРОВКА ВКЛЮЧЕНИЕМ
СОРТИРОВКА ХОАРА
СОРТИРОВКА С ИСПОЛЬЗОВАНИЕМ ВЕКТОРА ИНДЕКСОВ
МОДУЛЬ CRT (основные возможности)
ЛИТЕРАТУРА
ВВЕДЕНИЕ
Список литературы
1. Абрамов А.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. М., Наука, 1988.
2. Абрамов С.А., Гнездилова Г.Г., Капустина Е.Н., Селюн М.И. Задачи по программированию. М., Наука, 1988.
3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М., Мир, 1979.
4. Вирт Н. Алгоритмы и структуры данных. М., Мир, 1989.
5. Епанешников А., Епанешников В. Программирование в среде Turbo Pascal 7.0. М., Диалог-Мифи, 1993.
6. Зуев Е.А. Система программирования Turbo Pascal. М., Радио и связь, 1992.
7. Зуев Е.А. Программирование на языке Турбо-Паскаль 6.0,7.0. М. Радио и связь. Веста. 1993.
8. Йодан Э. Структурное программирование и конструирование программ. М.: Мир, 1979.
9. Кенин А.М., Печенкина Н.С. Работа на IBM PC. М., АО "Книга и бизнес", 1992.
10. Кнут Д. Искусство программирования на ЭВМ. М.: МИР, т.1, 1976; т.2, 1977; т.3, 1978.
11. Липский В. Комбинаторика для программистов. М., Мир, 1988.
12. Майерс Г. Искусство тестирование программ. М.: Финансы и статистика, 1982. Гласс Р., Нуазо Р. Сопровождение программного обеспечения, М.: Мир, 1983.
13. Пильщиков В.Н. Сборник упражнений по языку Паскаль. М., Наука, 1989.
14. Поляков Д.Б., Круглов И.Ю. Программирование в среде Турбо Паскаль (версия 5.5). Изд-во МАИ, 1992.
15. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. М., Мир, 1980.
