СОДЕРЖАНИЕ 2
ВВЕДЕНИЕ
ОСНОВЫЯЗЫКА. АЛГОРИТМЫ
АЛФАВИТ ЯЗЫКА
СТРУКТУРА ПРОГРАММЫ
ТИПЫДАННЫХ
Целые типы
Вещественные типы
Логический тип
Символьный тип
ВЫРАЖЕНИЯ
СОВМЕСТИМОСТЬ ТИПОВ ДАННЫХ
ЛИНЕЙНЫЕ АЛГОРИТМЫ
ПУСТОЙ И СОСТАВНОЙ ОПЕРАТОРЫ
ОПЕРАТОР ПРИСВАИВАНИЯ
ПРОСТЕЙШИЙ ВВОД И ВЫВОД
РАЗВЕТВЛЯЮЩИЕСЯ АЛГОРИТМЫ
ОПЕРАТОР ПЕРЕХОДА
УСЛОВНЫЙ ОПЕРАТОР
ОПЕРАТОР ВЫБОРА
ЦИКЛИЧЕСКИЕ АЛГОРИТМЫ
ЦИКЛЫС ПАРАМЕТРОМ
ЦИКЛЫС УСЛОВИЕМ
ПОЛЬЗОВАТЕЛЬСКИЕ ТИПЫДАННЫХ
ПЕРЕЧИСЛЯЕМЫЙ ТИП
ТИП-ДИАПАЗОН
МАССИВЫ
ЗАПИСИ
РАБОТА СО СТРОКАМИ
ПРОЦЕДУРЫИ ФУНКЦИИ
Параметры-значения
Параметры-переменные
Параметры-константы
ОТКРЫТЫЕ ПАРАМЕТРЫ-МАССИВЫ
БЕСТИПОВЫЕ ПАРАМЕТРЫ
ПРОЦЕДУРНЫЕ ТИПЫ
РЕКУРСИЯ
ТИПИЗИРОВАННЫЕ КОНСТАНТЫ
МОДУЛИ
АЛГОРИТМЫПОИСКА
ЛИНЕЙНЫЙ ПОИСК
ПОИСК С БАРЬЕРОМ
ДВОИЧНЫЙ (БИНАРНЫЙ) ПОИСК
АЛГОРИТМЫСОРТИРОВКИ
СОРТИРОВКА ВЫБОРОМ
СОРТИРОВКА ОБМЕНОМ (МЕТОДОМ "ПУЗЫРЬКА")
ШЕЙКЕРНАЯ СОРТИРОВКА
СОРТИРОВКА ВКЛЮЧЕНИЕМ
СОРТИРОВКА ХОАРА
СОРТИРОВКА С ИСПОЛЬЗОВАНИЕМ ВЕКТОРА ИНДЕКСОВ
МОДУЛЬ 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 и т.п.
Вещественные числа хранятся неточно. Каждый из имеющихся вещественных типов гарантирует правильное хранение только определенного количества значащих цифр, их называют верными цифрами. С математической точки зрения, из за особенностей внутреннего представления речь идет об относительной погрешности.
Неточности в хранении вещественных чисел могут привести к тому, что при вычитании близких чисел может произойти потеря значимости. Это же объясняет, почему следует избегать сравнения вещественных величин на точное равенство.
ПРИМЕР: тип Single - хранится 7-8 знаков после десятичной точки, тип Double - 15-16, тип Extended - 19-20.
program sravnenie;
var x: single; y: double; z: extended;
begin
x:= 1/3; y:= 1/3;
z:= abs(x-y);
writeln('z=',z);
end.
Эта программа выдаст в результате число z=9.93410748106882E-0009. Обычно принято считать, что a=b, если выполняется условие abs(a-b)<eps. Число eps можно определять следующим образом: min(abs(a),abs(b))*10^(-m), где m - необходимое число совпадающих десятичных разрядов.
Логический тип
Переменные логического типа Boolean занимают в памяти один байт и могут принимать одно из двух значений False - ложное или True - истинное. Этот тип является порядковым (Ord(False) = 0, Ord(True) = 1) и, следовательно, упорядоченным. Результат любых операций сравнения имеет логический тип и может быть присвоен логической переменной. Для операндов типа boolean определены следующие логические операции: NOT - отрицание (превращает false в true, а true в false), AND - логическое умножение "и", OR – логическое сложение "или", XOR - исключающее или (true если операнды разные). Принцип действия этих операций можно проиллюстрировать такими схемами:
AND | false | true |
false | false | false |
true | false | true |
OR | false | true |
false | false | true |
true | true | true |
XOR | false | true |
false | false | true |
true | true | false |
Символьный тип
Символьный тип Char также называют литерным. Он позволяет работать с символами, которые записываются двумя способами: в одинарных кавычках или по их коду, например 'a', 'B', '*' или, что то же самое, #97, #130, #42. В отличие от текста программы на паскале, символы, соответствующие строчным и заглавным буквам различаются. Множество значений типа Char представляет собой полный набор ASCII - символов (американская стандартная кодировка). В компьютере хранятся шестнадцатеричные коды символов (1 байт), которые и используются в операциях отношения (сравнения). Функция Ord выдает код соответствующего символа, который может быть от 0 до 255. Обратной функцией, которая по коду выдает соответствующий символ, является функция Chr.
ВЫРАЖЕНИЯ
Выражение - это единица языка, которая определяет способ вычисления некоторого значения. Выражения формируются из констант, переменных, функций, знаков операций и круглых скобок по определенным синтаксическим правилам.
Константами называются параметры программы, значения которых не меняются в процессе ее выполнения. Они встречаются либо непосредственно в виде значения, либо в виде идентификатора константы, описанного в разделе, начинающемся со слова Const. Для каждой константы в разделе указывается конструкция вида:
идентификатор константы = значение;
Целые константы содержат лишь цифры и знак: -214, 23, вещественные могут содержать также десятичную точку, показатель степени и символ e, который заменяет основание 10 в записи числа: -0.5, -1e-5, 7.2e+15. Логические константы - это значения False или True. Символьная константа представляет собой символ ASCII, заключенный в апострофы. Если символ не имеет физического изображения, то пишется знак # и рядом ASCII-код символа без апострофов.
Переменными называются параметры программы, которые могут менять свое значение в процессе ее выполнения. Все без исключения переменные должны быть описаны в разделе программы, начинающемся со слова VAR. Затем следуют конструкции вида:
список идентификаторов переменных: тип1;
список идентификаторов переменных: тип2;
В списке имена переменных перечисляются через запятую. Кроме базовых типов Турбо Паскаля здесь можно использовать свои типы (описанные ранее в разделе Type). В Турбо Паскале имеется большое количество встроенных функций для работы с данными каждого типа. Имена (указатели) этих функций с аргументом в круглых скобках могут также встречаться в выражениях. Знаки операций зависят от типа используемых в выражении операндов и рассмотрены выше.
Круглые скобки используются для изменения порядка вычисления частей выражения. Выражения без скобок вычисляются в порядке, соответствующем приоритету операций. Приоритеты расставлены таким образом:
вычисления в круглых скобках;
вычисление значений функций;
унарные операции (not,+,-);
операции типа умножения (*,/,div,mod,and);
операции типа сложения (+,-, or, xor);
операции отношения (=, <>, <, >, <=, >=).
В логическом выражении 2<=4 and 5>3 Паскаль выдаст ошибку, поскольку операция and будет выполнена раньше операций сравнения. Верная запись - (2<=4) and (5>3).
СОВМЕСТИМОСТЬ ТИПОВ ДАННЫХ
Когда в операциях или операторах вашей программы присутствуют данные разных типов, то встает вопрос об их совместимости. В языке Турбо Паскаль этому вопросу уделяется очень большое внимание, разработаны строгие правила, определяющие идентичность, совместимость в общем случае и совместимость по присваиванию различных типов.
Нам в начале курса достаточно помнить следующее. Переменные или выражения одного типа являются полностью совместимыми. Другим понятием является совместимость по присваиванию. Присваивание переменной одного типа выражения другого типа допустимо в том случае, когда множество значений второго типа является подмножеством значений первого. Например, результат сложения двух целых переменных типа integer и word может присваиваться в целую переменную, тип которой только longint, поскольку только этот целый тип содержит в себе весь возможный диапазон значений как для типа integer, так и для типа word. Также, можно присваивать целое выражение в вещественную переменную или символьное выражение в строку.
ЛИНЕЙНЫЕ АЛГОРИТМЫ
Алгоритмические действия над исходными данными и рабочими объектами языка, необходимые для решения поставленной задачи описываются при помощи операторов Турбо Паскаля. Операторы разделяются точкой с запятой, их последовательность и составляет тело программы. Наиболее простой случай представляют собой линейные алгоритмы. При выполнении линейных участков алгоритма операторы выполняются последовательно друг за другом в том порядке, в котором они перечислены в программе. При этом могут использоваться операторы присваивания, операции ввода и вывода.