Основы программирования — Осенний семестр; Михалкович С.С.; 2008; VI — различия между версиями

Версия 19:40, 5 июня 2009

Массивы

Перечислимый и диапазонный типы. Стандартные функции Ord Pred Succ. Стандартные процедуры Inc Dec.

Использование перечислимого типа в for и case.

Понятие структурированного типа данных.

Определение массива.

Описание массивов. Тип массива. Тип индексов массива. Понятие порядкового типа.

Лекция 16

Обращение к элементам массивов.

Выход за границы диапазона. Контроль выхода в Delphi и PascalABC.NET.

Динамические массивы. Хранение в памяти.

Инициализация массивов.

Присваивание массивов. Сравнение массивов.

Присваивание a := nil для динамических массивов.

Цикл foreach.

Именная и структурная эквивалентность типов.

Лекция 17

Массивы как параметры подпрограмм

При передаче статического массива должна соблюдаться именная эквивалентность

  procedure xxx(a: array [1..100] of integer); // неверно
 
  type IArr = array [1..100] of integer;
  procedure yyy(a: IArr);

Передавать массив по значению крайне неэффективно (т.к.происходит копирование всех элементов на стек). Его следует передавать по ссылке: для этого есть специальное ключевое слово const, которое также запрещает изменять данные внутри п/п.

  procedure zzz(const a: IArr);
  procedure sss(var a: IArr);

Динамический массив можно передавать в виде array of integer, т.к. для него определена структурная эквивалентность типов.

  procedure ttt(a: array of integer);

Передавать массив по ссылке необходимо только если внутри п/п нужно изменить длину массива. Иначе можно передавать по значению, т.к. при вызове п/п на программный стек кладется только адрес участка памяти, хранящего значения элементов массива, а значит все изменения формального массива-параметра внутри п/п меняют соответствующий ему фактический параметр. Массивы как возвращаемые значения функции

Часто требуется использовать массив как возвращаемое значение функции, для этого удобно использовать динамический массив, который хранит свою длину.

Переменное число параметров подпрограмм

П/п можно создавать с переменным количеством параметров. Для этого исп. ключевое слово params. При этом такие параметры, перечисленные через запятую, на этапе выполнения упаковываются в динамический массив, и п/п внутри работает именно с ним. Пар-р params может быть только один и должен находиться последним в списке пар-ов.

Лекция 18

Шаблоны подпрограмм

Часто требуется выполнять одно и то же действие для разных типов данных. В этом случае неудобно использовать перегрузку, т.к. п/п отличаются только заголовками.

Выход - шаблоны.

Пример:

 procedure Print<T> (array of T);

В момент вызова п/п происходит:

• выведение типов шаблона по фактическим параметрам
• инстанцирование - подстановка конкретных типов шаблонов и генерация кода подпрограммы с этими конкретными типами.

Если для такого типа код уже инстанцировался, то повторно действие не выполняется.

Задачи на одномерные массивы

• инвертирование массива (шаблон)
• поиск элемента в массиве - найти и вернуть индекс (шаблон)

можно с for и break,

можно и другим способом - с while

• поиск с барьером (шаблон). Его преимущества
• минимальный элемент массива и его индекс
• слияние двух упорядоченных массивов в один упорядоченный (барьер)
• сдвиг элементов массива влево (шаблон)

знакомство со значением default(T), Т - тип

Лекция 19

Задачи на одномерные массивы

pas-файл с задачами

doc-файл

используется тип IArr = array [1..size] of integer

• сдвиг элементов массива вправо (ShiftRight)

[ два варианта определения граничных значений цикла (от n-1 до 1; от n до 2) ]

• циклический сдвиг элементов массива вправо (CycleShiftRight)
• удаление элемента по заданному индексу (Delete)
• вставка элемента по заданному индексу (Insert)

Задачи с процедурными переменными в качестве параметров

Определяется тип IUnPred = function (x: integer): boolean

• поиск элемента по заданному условию (Find)
• количество элементов, удовлетворяющих условию (Count)
• условный минимум (MinElem)
• удаление всех элементов, удовлетворяющих условию (DeleteAll)

Примечание. Для проверки выхода индекса за границы диапазона (внутри цикла) следует проверять граничные значения счетчика, подставляя их во все индексы

Лекция 20

Сортировки

• Выбором (нахождение минимального элемента в неупорядоченной части массива и перемещение его на первую после уже отсортированного участка позицию)

• Пузырьковая

Это самый компактный алгоритм сортировки. Его можно оптимизировать, проверяя случай "холостого" прохода по элементам массива. Т.е. если за проход ни один элемент не изменил позицию, значит массив уже отсортирован и проверять дальше нет смысла.

• Вставками (вставка элемента из еще не упорядоченного участка массива в "нужную" позицию отсортированного, для чего сдвиг части элементов вправо и вставка нового в освободившуюся позицию)

Замечание. Рассмотренные виды сортировки не являются самыми эффективными. Асимптотическая сложность алгоритмов

Определение. Число шагов алгоритма асимптотически равно Θ(f(n)) если, существуют такие N, с1, с2>0 (c1<c2), что для любых n ≥ N выполняется:

   c1*f(n) ≤ число шагов ≤ c2*f(n)

Замечание 1. Для рассмотренных алгоритмов сортировки асимптотическая сложность = Θ(n²).

Замечание 2. Существуют алгоритмы сортировки с асимптотической сложностью = Θ(n*logn) (они будут рассмотрены в следующем семестре).

Лекция 21

Алгоритм бинарного поиска в отсортированном массиве

Его асимптотическая сложность - Θ(logn). Двумерные массивы

Двумерный массив как матрица (соответствие индексов строкам и столбцам)

Элементы строки. Элементы столбца (рисунки)

Понятие замороженного индекса

Задачи на двумерные массивы

• Вывод матрицы
  • внешний цикл по строкам
  • если внешним сделать цикл по столбцам будет выведена транспонированная матрица

• Сумма элементов в j-том столбце

• Сумма элементов в каждом столбце
  • использование функции для нахождения суммы в j-ом столбце
• Минимальный элемент в каждой строке
  • в отличие от предыдущей задачи, для реализации не создается дополнительная п/п.

Замечание. Решать такие задачи можно и реализуя алгоритм полностью, и создавая для этого дополнительные п/п. Если задача несложная, то вполне можно пользоваться первым способом, однако если решение не очевидно, лучше выносить часть алгоритма в п/п, иначе код будет очень трудно читать.

• Квадратные матрицы и элементы выше-ниже главной (побочной) диагонали.

Лекция 22

• Поиск элемента в матрице

если для поиска используется функция, то при нахождении элемента выходить из циклов с помощью exit,

иначе удобно использовать goto КОНЕЦ_ВНЕШНЕГО_ЦИКЛА