- •Средства разработки программ на Паскале
- •Структура Паскаль-программы
- •Комментарии
- •Директивы компилятора
- •Идентификаторы
- •Переменные и типы данных
- •Константы
- •Неименованные константы
- •Нетипизированные константы
- •Типизированные константы
- •Простейшие операторы
- •Метки и безусловный переход
- •Ввод и вывод: консоль
- •Ввод с консоли
- •Вывод на консоль
- •Форматный вывод
- •Пример простейшей программы на языке Pascal
- •Типы данных
- •Порядковые типы данных
- •Стандартные подпрограммы, обрабатывающие порядковые типы данных
- •Типы данных, относящиеся к порядковым
- •Вещественные типы данных
- •Конструируемые типы данных
- •Операции и выражения
- •Совместимость типов данных
- •Приведение типов данных
- •Ветвления, массивы, циклы
- •Массивы
- •Операторы циклов
- •Сортировки массивов
- •Быстрая сортировка
- •Символы и строки
- •Неименованные константы
- •Нетипизированные константы
- •Типизированные константы
- •Операции
- •Стандартные функции
- •Стандартные функции и процедуры обработки строк
- •Операции со строками Сравнения
- •Обращение к компонентам строки
- •Конкатенация
- •Множества
- •Описание множеств
- •Множество-константа Неименованная константа
- •Нетипизированная константа
- •Типизированная константа
- •Операции с множествами
- •Представление множеств массивами
- •Представление множеств линейными массивами
- •Представление множеств битовыми массивами
- •Примеры использования символов, строк и множеств
- •Что такое файл
- •Когда нужно использовать файлы
- •Разновидности файлов
- •Описание файлов
- •Текстовые файлы Назначение файла
- •Открытие файла
- •Закрытие файла
- •Считывание из файла
- •Запись в файл
- •Пробельные символы
- •Пример использования файлов
- •Решение
- •Реализация
- •Изменение реакции на ошибку
- •Описание записей
- •Задание записей константой
- •Доступ к полям
- •Оперирование несколькими полями
- •Вложенные операторы with
- •Запись с вариантной частью
- •Описание записи с вариантной частью
- •Механизм использования записи с вариантной частью
- •Бинарные файлы
- •Типизированные файлы
- •Описание типизированных файлов
- •Назначение типизированного файла
- •Открытие и закрытие типизированного файла
- •Считывание из типизированного файла
- •Поиск в типизированном файле
- •Запись в типизированный файл
- •Поиск в нетипизированном файле
- •Запись и чтение
- •Подпрограммы обработки директорий
- •Применимость подпрограмм обработки файлов
- •Процедуры и функции Подпрограммы
- •Список параметров
- •Возвращаемые значения
- •Вызов подпрограмм
- •Способы подстановки аргументов
- •Параметр-значение Описание
- •Механизм передачи значения
- •Параметр-переменная Описание
- •Механизм передачи значения
- •Параметр-константа Описание
- •Механизм передачи значения
- •Области действия имен Разграничение контекстов
- •Побочный эффект
- •Совпадение имен
- •Нетипизированные параметры
- •Явное преобразование типа
- •Совмещение в памяти
- •Открытые параметры
- •Открытые массивы
- •Рекурсивные подпрограммы Динамические структуры данных
- •Операции
- •Очередь
- •Операции
- •Рекурсия
- •Рекурсивные подпрограммы
- •Пример рекурсивного алгоритма
- •Алгоритм решения
- •Стековая организация рекурсии
- •Ограничение глубины рекурсии
- •Замена рекурсивных алгоритмов итеративными
- •Пример сравнения рекурсивного и нерекурсивного алгоритма
- •Рекурсивный алгоритм
- •Реализация рекурсивного алгоритма
- •Полный перебор с отсечением
- •Нерекурсивный алгоритм
- •Реализация нерекурсивного алгоритма
- •Иллюстрация
- •Эффективность
- •Быстрая сортировка2
- •Алгоритм Быстр
- •Реализация алгоритма Быстр
- •Эффективность алгоритма Быстр
- •Адреса и указатели. Списочные структуры данных Статически выделяемая память
- •Разыменование
- •Присваивания
- •Сравнения
- •Динамически распределяемая память
- •Динамическое выделение памяти Типизированные указатели
- •Нетипизированные указатели
- •Динамическое освобождение памяти Типизированные указатели
- •Нетипизированные указатели
- •Списочные структуры
- •Структура списков
- •Описание списков
- •Оперирование элементами списка Хранение списка
- •Обращение к элементам списка
- •Создание списков
- •Просмотр элементов списка
- •Удаление элементов списка
- •Перестройка списков
- •Примеры перестройки линейных списков
- •Реализация
- •Создание дружественного интерфейса
- •Заставка
- •Ввод информации
- •Приглашения
- •Вывод информации
- •Технология программирования и отладка Советы по технологии написания быстро отлаживаемых программ
- •Имена, имена, имена...
- •Кусочки, куски и кусищи...
- •Спасение утопающих - дело рук самих утопающих
- •Отладка и тестирование
- •Поиск и исправление ошибок
- •Правила составления тестов
- •Оптимизация программ
- •Учебники к курсу
Эффективность
В отличие от рекурсивного алгоритма, верхним пределом для которого можно смело считать наборы длиной в 50 предметов, итеративный алгоритм способен обработать до 5 000 различных весов (общее количество предметов может быть гораздо больше).
Другие примеры сравнения рекурсивных и нерекурсивных алгоритмов, решающих одну и ту же задачу, будут приведены в лекции 12.
Быстрая сортировка2
Возвратимся теперь к методам сортировки массивов, которым была посвящена лекция 4. Наиболее эффективный способ сортировки остался тогда не рассмотренным по причине того, что самая удобная его реализация подразумевает рекурсию.
Алгоритм Быстр
Возьмем в сортируемом массиве срединный элемент: x:=a[(1+N)div 2];
Будем производить следующие действия:
начав с левого конца массива, будем перебирать его компоненты до тех пор, пока не встретим элемент a[i], больший х;
начав с правого конца массива, будем перебирать его компоненты до тех пор, пока не встретим элемент a[j], меньший х;
поменяем местами элементы a[i] и a[j];
до тех пор, пока не произойдет "рандеву". В результате массив будет разделен на две части. В левой части окажутся все компоненты, меньшие х, а в правой - большие х.
Теперь применим эти же действия к левой и к правой части массива - рекурсивно.
Реализация алгоритма Быстр
type index = 1..N;
var a: array[index] of integer;
procedure quicksort(l,r:index);
var i,j: index;
x,z: integer;
begin
i:= l;
j:= r;
x:= a[(l+r)div 2];
repeat
while a[i]< x do inc(i);
while a[j]> x do dec(j);
if i <= j
then begin
z:= a[i];
a[i]:= a[j];
a[j]:= z;
inc(i);
dec(j);
end;
until i>j;
if l<j then quicksort(l,j);
if i<r then quicksort(i,r);
end;
begin {тело программы}
...
quicksort(1,n);
...
end.
Эффективность алгоритма Быстр
Алгоритм Быстрой сортировки имеет в среднем1) сложность N*log N и, следовательно, относится к улучшенным методам сортировки массивов (см. лекцию 4). Кроме того, даже среди улучшенных методов упорядочения Быстрая сортировка дает наилучшие результаты по времени (для относительно больших входных последовательностей - начиная с N = 100).
Конечно же, существует и итеративный вариант алгоритма Быстрой сортировки, который еще более эффективен. Мы предлагаем читателям построить его самостоятельно.
Адреса и указатели. Списочные структуры данных Статически выделяемая память
Для того, чтобы лучше понять специфику динамически выделяемой памяти, рассмотрим сначала ее "антипод" - память, распределяемую статически.
Такое выделение памяти используется всякий раз при объявлении "обычных" переменных в разделе var. Каждая переменная обладает двумя атрибутами: именем и описанием.
var a: integer;
Описание переменной нужно для того, чтобы компилятор знал, сколько ячеек памяти необходимо выделить для ее хранения. Память под статическую переменную выделяется один раз (до начала работы программы), и затем до конца работы выделенная область памяти считается "занятой" - никакая другая информация не может быть записана в эту ячейку.
Имя переменной позволяет обращаться в процессе работы программы к той ячейке памяти, которая была выделена под эту переменную на этапе компиляции.
Адреса
Имя переменной является ее своеобразным (буквенным) адресом. Однако у любой переменной есть также и обычный (цифровой или физический) адрес: номер ячейки, выделенной под эту переменную.
При страничной организации памяти адреса являются составными и состоят из номера сегмента памяти и смещения ячейки относительно начала этого сегмента.
Лучшая иллюстрация страничной организации памяти компьютера - это страничная организация любой печатной книги. Для того чтобы найти нужную строчку, нет необходимости задавать ее номер, считая от начала текста. Вместо этого можно задать сначала номер страницы (= сегмент) и только затем номер строки, считая от начала этой страницы (= смещение).
Для обращения к статически заданной переменной можно использовать как ее имя, объявленное в разделе var, так и ее физический адрес.
Например, "адрес" одной и той же географической точки можно записать по-разному: "49°47' северной широты и 86°36' восточной долготы" или просто "вершина пика Белуха Восточная1)".
Указатели
Для того чтобы хранить (цифровые) адреса, нужны особые переменные. Их называют указателями и относят к специальному типу данных.
Описание указателей
При описании типизированного указателя необходимо сообщить компилятору, адреса переменных какого типа он может хранить:
var <имя_указателя>: ^<тип_адресуемой_переменной>;
Например:
var p: ^integer;
q: ^real;
s: ^array[1..10] of byte;
Кроме того, существуют универсальные нетипизированные указатели, которые могут хранить адрес переменной любого типа:
var <имя_указателя>: pointer;
Операции с указателями
Определение адреса
Физический адрес любой переменной можно узнать при помощи стандартной функции addr(<имя_переменной>):<указатель> или унарной операции @<имя_переменной>.
В зависимости от значения директивы компилятора {$T}, результатом операции @ будет либо типизированный указатель (если установлено {$T+}), тип которого будет определен в соответствии с типом использованной переменной, либо нетипизированный указатель pointer (если установлено {$T-}).
Результат функции addr() совместим с указателями любых типов:
p:= addr(x); {x: real; p: ^byte)