- •Иркутский государственный университет путей сообщения кафедра “информатика” программирование на языке паскаль
- •Иркутск
- •Содержание
- •Программирование и алгоритмические языки в историческом аспекте
- •Введение в Паскаль
- •Алфавит Паскаля
- •Служебные (ключевые) слова
- •Константы
- •Запись чисел
- •Переменные
- •Типы данных
- •Стандартные функции
- •Выражения
- •Выражения целого типа
- •Выражения вещественного типа
- •3,61·109 X – 526,237 3.61e9 * X – 526.237 * Sqrt(0.2*y) Выражения логического типа
- •Операторы присваивания
- •Программа и этапы ее разработки. Структура программы
- •Var X, s : Word;
- •Комментарии
- •Ввод данных
- •Вывод данных
- •Бесформатный способ вывода
- •±D.DdddddddddE±dd
- •Форматный способ вывода
- •Структуры данных
- •Массивы
- •Var a : Array [1..2,1..3] Of Integer;
- •Error 201: Range check error
- •Var a : tMatrix;
- •Var Doska : Array [‘a’..’h’,1..8] Of Char;
- •Var Roma : Array [1..787] Of Word;
- •Var Roma : Array [-754..33] Of Word;
- •Var Ozenka : Array [1..2,1..3] Of Word;
- •Var Ozenka : Array [Fam, Predm] Of 2..5;
- •Var a: Array [1..3, 1..4, 1..5] Of Integer;
- •Var I, j: Byte;
- •Алгоритм и его свойства
- •Схемы алгоритмов
- •Базовые структуры
- •Цепочка
- •Ветвления
- •Альтернатива
- •If (условие)
- •Вариант 2 – с использованием операции конъюнкция
- •Часто встречающиеся ошибки программирования:
- •Var X, y, s_left, s_right, alfa, sin_alfa, segment : Real;
- •Переключатель
- •Var Month: 1..12;
- •Бесконечные циклы
- •Циклы с предусловием
- •Var I, s : Word;
- •Var I, s, n : Word;
- •Программа
- •Var n, min, max, s, count: Word;
- •Часто встречающиеся ошибки программирования:
- •Циклы с постусловием
- •Var I, s : Word;
- •Var I, s, n : Word;
- •Программа
- •Var n,min,max,s,count: Word;
- •Var k : Word;
- •X, y, s : Real;
- •Var Month: 1..12;
- •Var n, s : Word;
- •Var I, s : Word;
- •Примеры:
- •Var I, j, k : Word;
- •Var I, i_max, vector_max : Integer;
- •Vector : Array [1..N] Of Integer;
- •Var I, s : Integer;
- •Vector : Array [1..N] Of Integer;
- •Var I, k, m : Integer;
- •Vector : Array [1..N] Of Integer;
- •Var I, s, count : Integer;
- •Vector : Array [1..N] Of Integer;
- •Var I, k, min, max, i_min, i_max : Integer;
- •Vector : Array [1..N] Of Integer;
- •Var I, k, i_otr, i_pol : Integer;
- •Vector : Array [1..N] Of Integer;
- •Var I, k, posl : Integer;
- •Vector : Array [1..N] Of Integer;
- •Var I, j, t : Integer;
- •Vector : Array [1..K] Of Integer;
- •Var I, j, t : Integer;
- •Vector : Array [1..K] Of Integer;
- •Var I, j, k : Integer;
- •Var I, j, k, posl : Integer;
- •Var I, j, k, m : Integer;
- •Var I, j, k, i_max, j_min : Word;
- •Var I, j, t : Integer;
- •Vector : Array [1..K] Of Integer;
- •Var I, j, m, t : Integer;
- •Vector : Array [1..K] Of Integer;
- •Var I, j, b, c : Word;
- •Часто встречающиеся ошибки программирования:
- •Множества
- •Var r : tSymb;
- •Основные операции со множествами
- •Типизированные файлы
- •Var f_int : tFile_Int;
- •Var n : Integer;
- •Функции для работы с типизированными файлами
- •И процедуры:
- •Var n : Integer;
- •Текстовые файлы
- •Var f_text : tFile_text;
- •Программа:
- •Var stud_1 : tStudent;
- •Var student : tKadr;
- •Var coord : tCoord;
- •Ключ : ();
- •Подпрограммы
- •Подпрограммы-функции
- •Var p : Real;
- •Var s : Real;
- •Var I: Word;
- •Var a, b, c : Integer;
- •Var a, b, c : Integer;
- •Var a, b : Integer;
- •Var a, b, c: Integer;
- •Рекурсия
- •5 * 4 * Factorial(3)
- •5 * 4 * 3 * Factorial(2)
- •5 * 4 * 3 * 2 * Factorial(1)
- •Var k: Integer; Func_2
- •Var temp : Integer;
- •Особенности рекурсии:
- •Процедуры
- •Var I: Word;
- •Var I, i_min, i_max: Word;
- •Var I: Word;
- •Var I: Word;
- •Var I: Word;
- •Var I: Word;
- •Var I, j, k: Word;
- •Var I: Word;
- •Var I: Word;
- •Var I, j, k: Word;
- •Var I: Word;
- •Var I: Word;
- •Var I, j, k: Word;
- •Var I: Word;
- •Var I: Word;
- •Var I, j: Word;
- •Программные модули
- •Структура модуля
- •Interface
- •Implementation
- •Var f: Text;
- •Var p: Real;
- •Var temp: Real;
- •Компиляция модулей
- •Взаимное использование модулей
- •Ссылки и динамические переменные
- •Var a, b: tPntint;
- •X, y: tPntchar;
- •Динамические структуры данных
- •Связные списки
- •Inf: Integer;
- •Var head, q : tPoint;
- •Inf: Integer;
- •Var head, q : tPoint;
- •Добавление нового элемента в список
- •Var head, q, r: tPoint;
- •Inf: Integer;
- •Var head, q, r : tPoint;
- •Удаление элемента из списка
- •Inf: Integer;
- •Var head, q, r : tPoint;
- •Сортированные списки
- •Var head, q, r, V: tPoint;
- •Inf: Integer;
- •Var head, q, r, V : tPoint;
- •Бинарные деревья
- •Var root, q, V: tRebro;
- •Интерфейс:
- •Var root, q, V : tRebro;
- •Поиск заданного узла в дереве
- •Var root, q, V : tRebro;
- •Удаление узла из дерева
- •Var root, q, V, r : tRebro;
- •Объектно-ориентированное программирование
- •Var X, y, dx, dy: Word;
- •Var x0, y0, dx, dy: Word;
- •Var x0, y0, dx, dy, radius: Word;
- •Var x0, y0, dx, dy, radius: Word;
- •Основы алгебры логики
- •Логическая функция не (отрицание)
- •Логическая функция и (конъюнкция – логическое умножение)
- •Логическая функция или (дизъюнкция – логическое сложение)
- •Логическое следование (импликация)
- •Логическое совпадение(эквивалентность)
- •Закон исключенного третьего
- •Закон противоречия
- •Закон двойного отрицания
- •Закон контрапозиции
- •Закон расширенной контрапозиции
- •Закон перестановки посылок
- •Закон силлогизма
- •Закон де Моргана
- •Минимизация формул алгебры логики
- •Системы счисления
- •Двоичная система счисления
- •Восьмеричная система счисления
- •Шестнадцатеричная система счисления
- •Арифметические операции в двоичной системе счисления
- •1111 11 11 - Переносы
- •Арифметические операции в восьмеричной системе счисления
- •Арифметические операции в 16-ричной системе счисления
- •1. Ошибки при компиляции
- •2. Ошибки времени выполнения а) Ошибки системы ms-dos
- •Б)Ошибки ввода-вывода
- •В)Критические ошибки
- •Г)Фатальные ошибки
Множества
Множества – это структуры данных, наряду с переменными, массивами и строками.
Понятие множества является одним из основных понятий современной математики.
Под множествомпонимается неупорядоченная совокупность неповторяющихся объектов (элементов), обладающих некоторыми одинаковыми свойствами и находящихся в некоторых отношениях между собой и с элементами других множеств: множество учебных заведений, множество студентов в институте и т.д.
Под множествомв Паскале понимается неупорядоченный набор фиксированного количества (не более255) неповторяющихся однотипных элементов, имеющих общее имя – имя множества.
В отличие от массива – упорядоченной совокупности элементов, в которой каждый элемент однозначно определяется значением своего индекса (индексов), элементы множества таких индексов не имеют. Они размещаются во множестве неупорядоченно, поэтому значение отдельного элемента нельзя прочитать из множества, а можно только установить, входит или нет он в данное множество. Значит, множества используются в тех случаях, когда интерес представляет не конкретное значение отдельного элемента множества, а лишь факт его наличия или отсутствия в данном множестве однотипных элементов.
В Паскале допускаются только множества с заранее определенным числом элементов одного типа, который называется базовымтипом множества. Допускаются множества следующих типов:
целого (множество целых чисел, не более 255 чисел),
логического (множество, состоящее из двух логических констант: TRUEиFALSE),
символьного (множество символов таблицы ASCII),
перечисляемого,
интервального.
Таким образом, в Паскале не определено множество, состоящее из чисел с дробной частью (REAL).
Прежде чем использовать множество в программе, его необходимоописать– назвать его имя и указать базовый тип. Описание множества можно произвести следующими способами:
1.объявлением его имени и типа в разделе описания переменныхVar:
Var r : Set Of ‘a ’. . ’c’;
d : Set Of 1 . . 4;
Описано множество r символов алфавита от‘a’до‘c’и множествоd целых чисел1, 2, 3, 4.
Внимание! Между начальным и конечным значениями интервала ставятсядветочки!
2.объявлением типа множества в разделе определения типовTypeи его имени – в разделе описания переменныхVar:
Type TSymb = Set Of ‘a’ . . ‘c’;
TNumb = Set Of 1 . . 4;
Var r : tSymb;
d : TNumb;
3.заданием множества как типизированной константы:
Const r : Set Of ‘a ’. . ’c’ = [‘a’,’c’];
d : Set Of 1 . . 4 = [2,1,3];
Внимание! Элементы множества перечисляются вквадратныхскобках череззапятую.
Элементы множества можно задавать следующими способами:
a)перечислениемотдельных его значений:
[‘c’, ‘a’, ‘e’] [76, 102, 5, 12]
b) интерваломбазового типа:
[25..45, 3..10] [‘a’..’d’, ‘k’..’n’]
c) выражениямибазового типа:
[Ord(109),’s’] [Succ(3), Pred(9), Round(Sin(1.0))]
Множество может принимать значения любых наборов элементов, указанных в его описании. Например, описанное ранее множество r может принимать следующие значения:
[‘a’, ‘b’, ‘c’]
[‘a’, ‘b’]
[‘a’, ‘c’]
[ ‘b’, ‘c’]
[‘a’]
[ ‘b’]
[ ‘c’]
[] пустое множество
а множество d - следующие:
[1, 2, 3, 4]
[1, 2, 3]
[1, 3, 4]
[1, 2, 4]
[2, 3, 4]
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
[1]
[2]
[3]
[4]
[]
Таким образом, любое множество может принимать 2nзначений, гдеn– количество элементов в описании множества.
Порядок следования элементов во множестве не устанавливается, поэтому, например, значения множества [‘a’, ‘b’, ‘c’] и[‘b’, ‘c’, ‘a’] эквивалентны.
При работе со множествами в Паскале можно использовать следующие операции:
+ объединение(сумма) множеств,
* пересечение(произведение) множеств,
- разностьмножеств,
Inвхождениеэлемента во множество.
Пересечениемдвух множеств называется множество, состоящее из элементов, одновременно входящих в оба множества-сомножителя:
[3, 4, 5] * [1, 3, 5] = [3]
[3, 4, 5] * [3, 4, 5] = [3, 4, 5]
[2, 1, 0] * [] = []
[2, 9, 8] * [6, 7] = [] пустое множество
[‘a’, ‘b’, ‘c’] * [‘d’, ‘c’, ‘a’] = [‘a’, ‘c’]
Объединениемдвух множеств называется множество, состоящее из элементов, входящих хотя бы в одно из множеств-слагаемых:
[3, 4, 5] + [1, 3, 5] = [1, 3, 4, 5]
[2, 9, 8] + [] = [2, 9, 8]
[1, 2, 3] + [1, 2, 3] = [1, 2, 3]
[‘a’, ‘b’, ‘c’] + [‘d’, ‘c’, ‘a’] = [‘a’, ’b’, ‘c’, ‘d’]
Разностьюдвух множеств называется множество, состоящее из элементов множества-уменьшаемого без элементов множества-вычитаемого:
[3, 4, 5] – [1, 3, 5] = [4]
[2, 9, 5] – [3, 7] = [2, 9, 5]
[2, 4] – [5, 4, 2] = []
Эти операции используются для построения выражений, содержащих множества, причем в этих выражениях сначала выполняются операции пересечения, а затем – операции объединения и разности. Порядок выполнения операций может быть изменен с помощью скобок:
([3, 4, 5] + [1, 3, 6, 7]) * [5, 6, 7] – [6] = [5, 7]
Пример: в группе 12 студентов. Заданы множества номеров студентов:
множество спортсменов sport = [1, 2, 3, 4, 5]
множество отличников otl = [2, 3, 6, 7]
множество курящих smok = [7, 8]
Определить:
1.множество спортсменов-отличников:
sport * otl = [1, 2, 3, 4, 5] * [2, 3, 6, 7] = [2, 3]
2.множество спортсменовилиотличников:
sport + otl = [1, 2, 3, 4, 5] + [2, 3, 6, 7] = [1, 2, 3, 4, 5, 6, 7] = [1 . . 7]
3.множество курящих спортсменов:
sport * smok = [1, 2, 3, 4, 5] * [7, 8] = []- пустое множество –спортсмены не курят!
4.множество некурящих отличников:
otl – smok = [2, 3, 6, 7] – [7, 8] = [2, 3, 6]
Для проверки вхождения какой-либо константы или переменной в определенное множество используется операция In, результатом которой являетсяTRUE, если это значение входит во множество, иFALSE– если не входит:
5 In [1, 5, 7] = TRUE
‘b’ In [‘a’, ‘c’, ‘d’] = FALSE
Наряду с этими операциями, над множествами определены и операции сравнения, используемые для сравнения однотипных множеств. Пусть AиB-два однотипных множества, тогда:
A <= BравноTRUE, если все элементы множестваA входят во множествоB:
[5, 3, 2] <= [1, 2, 3, 4, 5] = True
A >= BравноTRUE, если все элементы множестваBвходят во множествоA:
[‘d’, ‘e’, ‘f’, ‘g’] >= [‘d’, ‘g’] = True
A = BравноTRUE, если элементы этих множеств полностью совпадают:
[1, 2, 3] = [3, 2, 1] = TRUE
A <> BравноTRUE, если эти множества различаются хотя бы одним элементом:
[1, 2, 3] <> [5, 2, 1] = TRUE
Выражения со множествами, построенные с помощью операций*, +и-, могут быть использованы в операторах присваивания вида:
V := S;
где V– переменная-множество,
S– выражение со множествами того же типа.
Внимание! Элементы множеств нельзя вводить и выводить операторамиReadиWrite, то есть имя множества не должно появляться в списках операторов ввода-вывода.