ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
КАФЕДРА С А П Р
И Г О Ш И Н А Л. В.
М Е Т О Д И Ч Е С К О Е П О С О Б И Е
по курсу "Алгоритмические языки и программирование"
Часть 1
Пенза 1999
Содержание
1. Алфавит языка Паскаль
2. Данные в языке Паскаль
2.1 Порядковые типы данных
2.1.1 Целые типы данных
2.1.2 Логический тип данных
2.1.3 Символьный тип данных
2.1.4 Перечислимый тип данных
2.1.5 Ограниченный тип данных
2.2 Вещественные типы данных
3. Структура программы на языке Паскаль
3.1 Описание меток
3.2 Описание переменных
3.3 Описание типов
3.4 Описание простых и типизированных констант
4. Арифметические выражения
5. Логические выражения
6. Составной оператор
7. Оператор присваивания
8. Процедуры ввода и вывода данных
Лабораторная работа № 1
9. Операторы условной и безусловной передачи управления
Лабораторная работа № 2
10. Оператор варианта
11. Операторы циклов
11.1 Оператор цикла с предусловием
11.2 Оператор цикла с постусловием
11.3 Оператор цикла с параметром
Лабораторная работа № 3
Лабораторная работа № 4
12. Массивы и их описание
12.1 Работа с одномерными массивами
Лабораторная работа № 5
12.2 Работа с двумерными массивами
Лабораторная работа № 6
13. Строковый тип данных. Операции над строками
14. Множества в Паскале, их описание. Операции над множествами
15. Тип данных - записи, их описание и использование. Оператор
присоединения
15.1 Работа с массивом из записей
Лабораторная работа № 7
16. Подпрограммы
16.1 Процедуры. Описание процедур. Область действия имён
Локальные и глобальные параметры
Лабораторная работа №8
16.2 Подпрограммы типа FUNCTION, их описание
Лабораторная работа №9
17. Задача сортировки: алгоритмы и программы
17.1 Сортировка выбором
17.2 Обменная сортировка
17.3 Сортировка слиянием
Лабораторная работа №10
18. Задача поиска: алгоритмы и программы
18.1 Линейный поиск
18.2 Двоичный поиск
Лабораторная работа №11
Алфавит языка Паскаль
Алгоритмический язык Pascal (Паскаль) был разработан Никлаусом Виртом в 1969-71гг. Современный вариант - язык Turbo Pascal - расширение американского стандарта ANSI Pascal.
Система Turbo Pascal (TP) является интегрированной средой, включающей:
- универсальный текстовый редактор;
- компилятор входного языка;
- редактор связей;
- встроенный символический отладчик.
Текст программы на языке ТР представляет собой последовательность
строк, состоящих из символов, образующих алфавит языка.
Строки программы завершаются специальными управляющими символами, не входящими в алфавит (CR - возврат каретки - клавиша Enter и LF - новая линия). Максимальная длина строки составляет 126 символов.
В алфавит языка входят:
1. Буквы латинского алфавита от a до z и от A до Z, а также знак подчеркивания "_", который приравнивается к буквам. (В ТР нет различия между прописными и строчными буквами алфавита, кроме случаев, когда они входят в символьные и строковые выражения).
2. Арабские цифры от 0 до 9.
3. Специальные символы, их 23:
+ - * / =.,:; ' < > () { } [ ] $ @ # ^ и пробел.
Символы из языка используются для построения базовых элементов -
лексем. В ТР определены следующие классы лексем:
1) Служебные (ключевые или зарезервированные) слова: Begin, End, Var,
Type, Label, Const, If, Then, Else, For, Do, While, Repeat и другие.
Служебные слова нельзя использовать не по назначению. Они не могут
использоваться в качестве идентификаторов.
2) Имена (или идентификаторы) вводятся программистом для обозначения (в программе) переменных, констант, типов, меток, процедур, функций, объектов, моделей, полей в записях и т.п. Они формируются только из букв и цифр, причем первой должна быть буква. Длина имени может быть произвольной, но компилятор воспринимает только первые 63 символа. Идентификаторы вводятся в программу посредством описаний.
3) Изображения - группа лексем, обозначающих числа, символьные строки и некоторые другие значения.
4) Знаки операций, которые формируются из одного или нескольких специальных символов или служебных слов:
а) арифметические операции: + (сложение), - (вычитание), * (умножение), / (деление вещественных чисел), mod (деление целых чисел), div (остаток от деления двух целых чисел);
б) операции отношения: < - (меньше), > - (больше), <= - (не больше), >= - (не меньше), = - (равно), <> - (не равно);
в) логические операции: and - логическое И, or - логическое ИЛИ, not - логическое НЕ, xor - исключительное ИЛИ;
г) операции над множествами: * - пересечение множеств, + - объединение множеств, - - вычитание множеств, IN - принадлежность множеству.
5) Разделители, которые формируются из специальных символов.
6) Комментарии - произвольная последовательность символов, в том числе и русских букв, заключенных в фигурные скобки {…} или (* … *), предназначенная для пояснений в программе. Комментарии могут находиться между любыми двумя лексемами программы.
7) Пробел, не имеющий графического изображения, используется для отделения лексем друг от друга.
Данные в языке Паскаль
В языке Паскаль любая переменная характеризуется своим типом.
Под типом, в данном случае, понимается множество значений, которые
может принимать переменная, а также множество операций, допустимых над данной переменной. Тип определяет формат внутреннего представления данных в памяти компьютера.
Тип переменной определяется при ее описании, и он не может быть
изменен в процессе выполнения программы. Переменная может участвовать только в операциях, допустимых ее типом.
Паскаль имеет развитую систему типов. Классификация типов данных,
приведенная на рисунке 1, взята из книги [1] и не является единственной. В языке предусмотрен механизм создания новых типов данных на основе базовых. Поэтому общее число типов, используемых в программе, может быть сколь угодно большим.
Рассмотрим сначала так называемые простые или базовые типы, являющиеся основой для построения других типов. Их иногда называют также стандартными типами данных.
 |
Рисунок 1
Порядковые типы данных
Порядковые типы характеризуются тем, что каждый из них имеет конечное число возможных значений и с каждым из них можно сопоставить некоторое целое число - порядковый номер значения. К порядковым типам относятся:
- целый тип;
- логический (или булевой) тип;
- символьный тип;
- перечислимый (или перечисляемый) тип;
- ограниченный (или интервальный) тип, который также называют тип-диапазон.
К любому из них применима стандартная функция ORD(Х), результатом которой является порядковый номер значения Х. К порядковым типам можно также применять функции:
PRED(X) - возвращает предыдущее значение порядкового типа;
SUCC(X) - возвращает следующее значение порядкового типа.
Целые типы данных
Эта группа типов обозначает множество целых чисел в различных диапазонах. Диапазон возможных значений целых типов зависит от их внутреннего представления, которое может занимать один, два или четыре байта.
В таблице 1 приведены имена (или названия) всех возможных целых типов (их всего 5), а также длина их внутреннего представления в байтах и диапазоны возможных значений каждого из типов.
Таблица 1
| Целые типы | ||
| Название | Длина, байт | Диапазон значений |
| Byte | 0…255 | |
| ShortInt | -128…+127 | |
| Word | 0…65535 | |
| Integer | -32768…+32767 | |
| LongInt | -2147483648…+2147483647 |
Значения целых типов могут изображаться в программе двумя способами: в десятичном виде (в виде последовательности цифр от 0 до 9) и в шестнадцатеричном виде (в виде последовательности цифр от 0 до 9 и букв от A до F, перед которыми ставится знак $).
Над целыми значениями допустимы следующие арифметические операции: + - сложение, - - вычитание, * - умножение, / - деление и две дополнительные операции "типа деление", а именно, Div - деление нацело, с отбрасыванием дробной части и Mod - взятие остатка от целочисленного деления.
При применении к целым значениям всех этих операций, кроме / - деления получается результат целого типа, а деление (/) всегда дает вещественный результат.
К значениям целых типов могут быть применены стандартные процедуры и функции, некоторые из них приведены в таблицах 2 и 3.
При действиях с целочисленными значениями тип результата будет соответствовать типу операндов, а если операнды относятся к различным целым типам, - типу того операнда, который имеет максимальный диапазон значений. Возможное переполнение результата никак не контролируется, что может привести к непредсказуемым результатам.
Таблица 2
| Стандартные функции, применимые к целым типам | |||
| Обращение | Тип аргумента | Тип результата | Действие |
| Hi(X) | Integer Word | Byte Byte | Возвращает старший байт аргумента |
| Lo(X) | Integer Word | Byte Word | Возвращает младший байт аргумента |
| Odd(X) | LongInt | Boolean | Возвращает значение True, если Х - если Х - нечетное |
| Swap(X) | Integer Word | Integer Word | Меняет местами байты в слове |
Таблица 3
| Стандартные процедуры, применимые к целым типам | ||
| Описание процедуры | Тип параметров | Назначение |
| Randomize | Без параметров | Гарантирует несовпадение последо- вательностей случайных чисел, выдаваемых функцией Random |
| Inc(X) | X - целое | Увеличивает значение Х на 1 |
| Dec(X) | X - целое | Уменьшает значение Х на 1 |
| Inc(X,N) | Dec(X,N) | Увеличивает значение Х на N |
| Dec(X,N) | Dec(X,N) | Уменьшает значение Х на N |
Логический тип данных
Логический тип (Boolean) состоит из 2-х значений: False (Ложь) и True (Истина).
Над значениями этого типа допустимы операции сравнения, причем False < True.
Для них справедливы правила:
ORD(False) = True;
ORD(True) = False;
SUCC(False) = True;
PRED(True) = False.
Значения логического типа занимают 1 байт. С логическим типом связаны логические операции: AND (И), OR (ИЛИ), NOT (НЕ).
Символьный тип данных
Значениями символьного типа (Char) являются символы из множества ASCII (American Code for Information Interchange - Американский стандартный код для обмена информацией). Это множество состоит из 256 различных символов, упорядоченных определенным образом. Оно содержит символы строчных и прописных букв, цифр и других символов, включая специальные управляющие символы. Каждому символу приписывается целое число в диапазоне от 0 до 255. Это число служит кодом внутреннего представления символа, его возвращает функция ORD.
Если символьное значение имеет графическое изображение, то оно изображается в программе соответствующим знаком, заключенным в апострофы (одинарные кавычки): 'A', 'B', …, 'a', 'b', …, '1', '2', …, '*', '+' и т. д.
Если символ не имеет графического изображения, то используют другую форму записи: #K, где К - целочисленный код символа.
Например: #13 - Enter; #27 - Esc; #8 - Backspace.
Так как символы упорядочены, то к типу Char применимы операции сравнения, например: 'A' < 'M'; 'A' < 'a' и т. п., а также стандартные функции:
CHR(b) - преобразует выражение b типа byte в символ и возвращает его своим значением.
Например: Chr(90) возвращает в качестве результата символ 'Z'.
ORD(S) - возвращает в качестве результата код символа S в таблице символов ASCII.
Например: Ord('Z') возвращает код, равный 90.
UPCASE(CH) - возвращает прописную латинскую букву, если CH - строчная латинская буква, в противном случае возвращает сам символ CH.
Например: Upcase('z') возвращает символ 'Z'.
PRED(S) - возвращает символ, предшествующий символу S.
SUCC(S) - возвращает символ, следующий за символом S.
Перечислимый тип данных
Перечислимый (или перечисляемый) тип данных задается списком значений (объектов), которые могут принимать переменные этого типа. При этом каждый объект имеет имя. Соответствие между значениями перечисляемого типа и порядковыми номерами этих значений устанавливается порядком перечисления: первое значение в списке получает порядковый номер 0, второе - 1 и т.д. Максимальное число объектов в перечисляемом типе равно 65366 значений. К значениям перечислимого типа применимы стандартные функции Ord, Pred, Succ, а также операции отношений.
Переменные этого типа повышают наглядность программы и позволяют автоматически контролировать допустимость значений переменных.
Рассмотрим примеры порядковых типов.
1. Описание дней недели:
TypeDays=(Monday,Tuesday,Wednsday,Thday,Friday,Sutterday,Sunday).
2. Описание месяцев года:
TypeYear=(jan,feb,mar,apr,may,jun,jul,aug,sep,oct,nov,dec).
Ограниченный тип данных
На основе четырех рассмотренных порядковых типов можно определить новые, порядковые типы: например, можно сузить диапазон значений любого из 4-х порядковых типов. Такие типы называют ограниченными (или интервальными) типами. Другое их название - диапазоны. Такие типы задаются границами своих значений внутри базового типа:
<минимальное значение>.. <максимальное значение>
Примеры определения типов - диапазонов:
Typedate=1..31; TypeMonth=1..12; TypeSim='A'..'Z'
Можно сразу определить переменную типа - диапазон:
Day:1..31; Month:1..12; Sim:'A'..'Z' и т.п.
Необходимо помнить, что левая граница диапазона не должна превышать правой.
К значениям этого типа могут быть применены стандартные функции:
HIGH(X) - возвращает максимальное значение типа - диапазона, к которому принадлежит переменная Х;
LOW(X) - возвращает минимальное значение типа - диапазона, к которому принадлежит переменная Х.
Вещественные типы данных
Эта группа типов представляет множества значений в различных диапазонах. ТР поддерживает пять различных вещественных типа (табл. 4).
Таблица 4
| Название | Длина, байт | Число цифр мантиссы | Диапазон значений |
| Real | 11-12 | 2.9 E-39…1.7 E +38 | |
| Single | 7-8 | 1.5 E-45…3.4 E+38 | |
| Double | 15-16 | 5.0 E-324…1.7 E+308 | |
| Extended | 19-20 | 3.4E-4951…1.1E+4932 | |
| Comp | -2 E+63… +2 E+63 -1 |
Все вещественные типы, кроме Real, используются если в ПК есть арифметический сопроцессор.
Данные вещественного типа могут быть представлены в двух видах: с фиксированной точкой и с плавающей точкой.
Значения с фиксированной точкой изображаются десятичным числом с дробной частью, которой может быть нулевой, например:
0.5, 5.25, 5.0, -16. 055 и т.п.
Значения с плавающей точкой изображаются следующим образом: m E p,
где m - мантисса вещественного числа, Е - признак порядка (число 10), р - порядок числа; m - целое или вещественное число с фиксированной точкой, положительное или отрицательное; р - только целое, положительное или отрицательное, например:
4 Е -5 (
), 0.62 Е 4 (
), -1.6 Е 22 
.
Над значениями вещественных типов допустимы четыре арифметических операции: *, /, +, -.
Целые и вещественные числа именуются как "число без знака".
В таблице 5 приведены некоторые стандартные математические функции и функции преобразования типов, которые используются при работе с целыми и вещественными значениями.
Таблица 5
| Вызов Функции | Тип аргумента | Тип результата | Назначение функции |
| Abs(X) | Целый Вещественный | Целый Вещественный | Вычисление абсолютного значения Х |
| Sin(X) | Вещественный | Вещественный | Синус Х радиан |
| Cos(X) | Вещественный | Вещественный | Косинус Х радиан |
| ArcTan(X) | Вещественный | Вещественный | Арктангенс Х радиан |
| Sqrt(X) | Целый Вещественный | Вещественный Вещественный | Квадратный корень из Х, (Х>0) |
| Sqr(X) | Целый Вещественный | Целый Вещественный | Значение Х, возведенное в квадрат |
| Exp(X) | Вещественный | Вещественный | Значение е в степени Х |
| Ln(X) | Вещественный | Вещественный | Натуральный логарифм Х, (Х>0) |
| Pi | Нет аргумента | Вещественный | Значение числа p |
| Trunc(X) | Вещественный | Longint | Целая часть числа Х |
| Frac(X) | Вещественный | Вещественный | Дробная часть числа Х |
| Int(X) | Вещественный | Вещественный | Целая часть числа Х |
| Round(X) | Вещественный | Longint | Округление Х до ближайшего целого |
| Random | Нет аргумента | Вещественный | Случайное число из диапазона (0...1) |
| Random(X) | Word | Word | Случайное число из диапазона (0...Х) |
| Odd(X) | Целый | Логический | Возвращает значение True, если Х - если Х - нечетное |
Замечания к таблице 5:
1. Под целым типом понимается один из типов языка (Byte, ShortInt, Word, Integer, LongInt);
2. Под вещественным типом понимается тип Real или иной тип с плавающей точкой. Математические функции очень чувствительны к диапазону своих аргументов. Кроме того, возвращаемые значения целых типов должны в них умещаться, иначе возможны фатальные последствия.
3. Функция ArcTan(X) возвращает главное значение арктангенса (в диапазоне от - p /2 до + p/2).
4. Функции Trunc и Int отличаются только типом возвращаемого значения.
Структура программ на языке TurboPascal
Любая программа на языке TurboPascal(ТР) состоит из двух основных разделов: раздела описаний данных и раздела операторов, и заканчивается всегда символом «.».
|
Begin
|
End.
Раздел описаний может включать в себя подразделы описания меток, констант, типов, переменных, а также подпрограмм, реализуемых в виде процедур или функций. Если в программе используются стандартные или библиотечные модули (Unit), то первой должна стоять директива Uses, в которой перечисляются используемые модули. Рекомендуется всегда включать в программу директиву:
Uses CRT;
Она подсоединяет стандартный модуль CRT, содержащий описание процедур, функций, констант, типов и переменных, позволяющих работать с цветом, звуком, экраном и ускорить операции ввода-вывода данных.
Кроме двух основных разделов в программу можно и нужно включать комментарии: пояснения к программе, данные о разработчиках и т.п.
Раздел описаний может содержать следующие подразделы:
1. Список имен, используемых модулей.
2. Объявление меток.
3. Объявление констант.
4. Объявление типов.
5. Объявление переменных.
6. Описание процедур и функций.
Не все подразделы обязательны.
Каждый из подразделов раздела описаний начинается своим ключевым словом.
Список имен модулей начинается с ключевого слова USES.
Раздел меток начинается с ключевого слова LABEL, раздел констант - CONST, раздел типов - TYPE, раздел переменных - VAR.
Раздел операторов следует за разделом описаний и всегда заключается в операторные скобки, определяемые ключевыми словами
Begin... End.
Операторы отделяются друг от друга символом ";". Запись операторов в строке может начинаться с любой позиции. В одной строке можно записать несколько операторов. Один оператор может быть записан в нескольких строках.
Описание меток
Метка представляет собой правильный идентификатор или любое
целое без знака от 1 до 9999. Метки должны быть описаны в подразделе Label. Каждая метка описывается только один раз в каждой программной единице (основной программе или подпрограммах).
Label метка; или Label метка1, метка2, …, меткаN;
В программе метка ставится перед оператором, на который передается управление и отделяется от него символом ":".
Метка: выполняемый оператор;
Примеры описания меток:
Label m1, m2, met1, l1, lab, 125;
Описание переменных
Любая переменная, используемая в программе (и подпрограммах) должна быть определена (описана) в подразделе Var раздела описаний, причем каждая переменная описывается только один раз в каждой программной единице.
Определение переменной должно содержать имя переменной и ее тип, разделенные двоеточием.
VAR имя переменной: тип;
Примеры:
Var x:real; i: byte;
S: char; b: boolean;
Days: 1..31;
Переменные одного типа записываются друг за другом через запятые:
Var a, b, c: real;
I,j,k:byte;
m, months:1..12;
Для переменных, описанных в каждой программной единице, отводится определенный объем памяти.
Переменные, описанные в основной (главной) программе, называют глобальными переменными. Общий объем памяти, отведенный под глобальные переменные, не должен превышать 64 Кбайта.
Переменные, описываемые в подпрограммах, называются локальными переменными.
Описание типов
В простейших случаях тип переменных указывается явно, при их описании в разделе Var:
Var Имя переменной: тип;
Можно сопоставить типу некоторое имя и описать его в разделе Type:
Type Имя типа = Тип;
Например:
Type Diapason = 1..1000;
T_days = 1..31;
T_symbol = 'a'..'z';
T_Month = (j,f,mr,ap,may,jn,jl,ag,s,o,n,d);
Это дает возможность программисту определять и использовать свои собственные типы, а не стандартные.
Далее можно имена типов, введенные в подразделе Type использовать в подразделе Var:
Var
i,i,n:Diapason;
Day:T_days;
Sim,ch:T_symbol;
Mes:T_Month;
