Языки и технология программирования

Министерство общего и профессионального образования

Российской Федерации

Уральский государственный университет

им. А.М. Горького

Лахтин А.С., Искакова Л.Ю.

Языки и технология программирования.

Начальный курс.

Учебное пособие

Екатеринбург

1998

Лахтин А.С., Искакова Л.Ю. Языки и технология программирования. Начальный курс. Учеб. пособие. Екатеринбург, 1998.

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

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

Пособие предназначено для студентов дистантной формы обучения специальности "Информационные системы", а также может быть использовано для студентов дневной формы обучения по этой специальности.

А.С. Лахтин, Л.Ю. Искакова, 1998.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ОСНОВЫ ЯЗЫКА

АЛГОРИТМЫ

АЛФАВИТ ЯЗЫКА

СТРУКТУРА ПРОГРАММЫ

ТИПЫ ДАННЫХ

Целые типы

Вещественные типы

Логический тип

Символьный тип

ВЫРАЖЕНИЯ

СОВМЕСТИМОСТЬ ТИПОВ ДАННЫХ

ЛИНЕЙНЫЕ АЛГОРИТМЫ

ПУСТОЙ И СОСТАВНОЙ ОПЕРАТОРЫ

ОПЕРАТОР ПРИСВАИВАНИЯ

ПРОСТЕЙШИЙ ВВОД И ВЫВОД

РАЗВЕТВЛЯЮЩИЕСЯ АЛГОРИТМЫ

ОПЕРАТОР ПЕРЕХОДА

УСЛОВНЫЙ ОПЕРАТОР

ОПЕРАТОР ВЫБОРА

ЦИКЛИЧЕСКИЕ АЛГОРИТМЫ

ЦИКЛЫ С ПАРАМЕТРОМ.

ЦИКЛЫ С УСЛОВИЕМ.

ПОЛЬЗОВАТЕЛЬСКИЕ ТИПЫ ДАННЫХ

ПЕРЕЧИСЛЯЕМЫЙ ТИП

ТИП-ДИАПАЗОН

МАССИВЫ

ЗАПИСИ

РАБОТА СО СТРОКАМИ

ПРОЦЕДУРЫ И ФУНКЦИИ

Параметры-значения

Параметры-переменные

Параметры-константы

ОТКРЫТЫЕ ПАРАМЕТРЫ-МАССИВЫ

БЕСТИПОВЫЕ ПАРАМЕТРЫ

ПРОЦЕДУРНЫЕ ТИПЫ

РЕКУРСИЯ

ТИПИЗИРОВАННЫЕ КОНСТАНТЫ

МОДУЛИ

АЛГОРИТМЫ ПОИСКА

ЛИНЕЙНЫЙ ПОИСК

ПОИСК С БАРЬЕРОМ

ДВОИЧНЫЙ (БИНАРНЫЙ) ПОИСК

АЛГОРИТМЫ СОРТИРОВКИ

СОРТИРОВКА ВЫБОРОМ

СОРТИРОВКА ОБМЕНОМ (методом "пузырька")

ШЕЙКЕРНАЯ СОРТИРОВКА

СОРТИРОВКА ВКЛЮЧЕНИЕМ

СОРТИРОВКА ХОАРА

СОРТИРОВКА С ИСПОЛЬЗОВАНИЕМ ВЕКТОРА ИНДЕКСОВ

МОДУЛЬ CRT (основные возможности)

ЛИТЕРАТУРА

ВВЕДЕНИЕ

Первая версия языка Паскаль была разработана швейцарским ученым Никлаусом Виртом в 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 с точкой. Операторы в Паскале разделяются точкой запятой. Заголовок программы является хотя и необязательным, но желательным элементом и состоит из зарезервированного слова program и идентификатора - имени программы, за котором следует точка с запятой. Порядок объявлений и описаний не регламентируется.

ПРИМЕР : Простейшая программа.

program prim_1; { демонстрация структуры программы}

{эта программа не требует никаких объявлений и описаний}

begin

write('Привет! Вот мы и начали.') (* эта строка текста появится на экране *)

end.

ТИПЫ ДАННЫХ

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

идентификатор типа = определение типа;

Рассмотрим сначала простые типы данных, каждый из которых определяет упорядоченное множество значений: целые типы, логический тип, символьный тип, вещественные типы. Все эти типы, кроме вещественных являются порядковыми. Каждому значению порядкового типа функция Ord ставит в соответствие натуральное число - порядковый номер данного значения в множестве допустимых значений. К любым порядковым типам также можно применять функции Pred - возвращает предыдущее значение и Succ - следующее значение. Тип относится к упорядоченным если для переменных и выражений этого типа определены операции отношения или сравнения: =, <>, <, >, <=, >=. Любой порядковый тип является упорядоченным, но не наоборот. Так вещественные типы и тип string упорядоченные, но не порядковые.

Целые типы

В языке Турбо Паскаль определено 5 целых типов:

Shortint (-128 ... 127, 1 байт),

Integer (-32767 ... 32768, 2 байта),

Longint (-2147483648 ... 2147483647, 4 байта),

Byte (0 ... 255, 1 байт),

Word (0 ... 65535, 2 байта).

Для целых чисел определены такие операции. Унарные: +,-. Бинарные: сложение, вычитание, умножение, получение частного (div) и остатка (mod) при целочисленном делении и некоторые другие. Также с целыми числами можно производить операции, результаты которых не целые числа. Это обычное деление и операции отношения. Кроме того, имеется большое количество встроенных функций для работы с целыми числами: abs, sqr, sqrt, sin, cos, exp, ln и др.

Вещественные типы

В Турбо Паскале имеется 5 вещественных типов.

Real (занимает 6 байт, диапазон от 2.9E-39 до 1.7E+38 по модулю, точность 11-12 значащих цифр)

Single (занимает 4 байта, диапазон от 1.5E-45 до 3.4E+38 по модулю, точность 7-8 значащих цифр)

Double (занимает 8 байт, диапазон от 5.0Е-324 до 1.7Е+308 по модулю, точность 15-16 значащих цифр)

Extended (занимает 10 байт, диапазон от 3.4E-4932 до 1.1E+4932 по модулю, точность19-20 значащих цифр).

Comp (занимает 8 байт, диапазон от -9.2E-18 до 9.2E+18, хранятся точно, поскольку это целые числа)

Вещественные типы являются упорядоченными, но не порядковыми. Операции над вещественными числами: сложение ,вычитание, умножение, деление и операции отношения. Кроме того, имеется большое количество встроенных функций для работы с числами: abs, sqr, sqrt, sin, cos и т.п.

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

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

Страницы: 1, 2, 3, 4, 5, 6, 7