- •Иркутский государственный университет путей сообщения кафедра “информатика” конспект лекций по дисциплине “программирование на алгоритмическом языке высокого уровня”
- •Иркутск
- •Программирование и алгоритмические языки в историческом аспекте
- •Введение в Паскаль
- •Алфавит Паскаля
- •Служебные (ключевые) слова
- •Константы
- •Запись чисел
- •Переменные
- •Типы данных
- •Стандартные функции
- •Выражения
- •Выражения целого типа
- •Выражения вещественного типа
- •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;
- •V : Array [1..K] Of Integer;
- •Var I, j, m, t : Integer;
- •V : 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
- •Б)Ошибки ввода-вывода
- •В)Критические ошибки
- •Г)Фатальные ошибки
Базовые структуры
Преимущество компьютеров и в то же время трудность их использования состоит в том, что они без труда выполняют операции, которые весьма трудоемки или практически невыполнимы людьми, и наоборот, действия, которые нам кажутся столь очевидными, что мы и не пытаемся их анализировать, зачастую становятся проблемой, когда предпринимается попытка их запрограммировать. Внешне заманчивая возможность, предписав одним росчерком пера выполнение тысяч элементарных действий, ставит трудную задачу понимания сложности, проблему, для решения которой необходимо вооружить себя определенными средствами. Такие средства алгоритмизации и программирования носят название базовых(управляющих) структур.
Как всякое автоматическое устройство, компьютер способен выполнять некоторое число элементарных операций: сложение, вычитание, сравнение, запись и чтение данных. Причем он обладает способностью самостоятельно управлять выполнением этих операций во времени. Если попытаться явно выразить возможности этого управления, то можно выделить три основные (базовые) управляющие структуры : цепочка (следование), ветвление, цикл. Эти комбинируемые по желанию структуры дают нам конструктор, позволяющий описать процесс вычислений произвольной сложности и полностью контролировать действия, предписываемые программой.
Практика разработки алгоритмов показывает, что в отдельных случаях одна и та же задача может быть успешно решена по алгоритмам, имеющим различную структуру. Главное требование к алгоритму заключается в том, чтобы он правильно решал поставленную задачу. Для удовлетворения этого требования алгоритм должен быть легким для понимания, простым для доказательства его правильности и удобным для модификации.
Опыт практической алгоритмизации привел к формированию особой методики организации алгоритмов, использование которой уменьшает вероятность ошибок в процессе их разработки и записи, упрощает их понимание и модификацию. Эту методику алгоритмизации называют структурнымпрограммированием.
При структурном программировании алгоритм как бы собирается из трех базовых структур, каждая из которых имеет один вход и один выход – цепочек, ветвлений и циклов. С помощью этих структур можно построить алгоритмы любой сложности, подсоединяя одну структуру к другой и развивая алгоритм не только вширь, но и вглубь. Конструируемые по этой методике алгоритмы четки и понятны, легко поддаются проверке, так как состоят из ограниченного числа одинаково устроенных блоков.
Для использования методики структурного программирования при словесной записи алгоритмов необходимо, чтобы такая запись располагала специальными средствами, адекватно реализующими базовые структуры. Если таких средств в том или ином алгоритмическом языке нет, то для облегчения последующей работы по переводу алгоритма в программу (кодирования) необходимо отработать языковые шаблоны, эквивалентно представляющие базовые структуры.
Таким образом, в соответствии с принципами структурного программирования любой алгоритм можно представить, используя только три базовые структуры – цепочку, ветвление, цикл.