9

1.Массивы

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

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

1. Однотипная обработка массивов

А) Поэлементная обработка .

Б) Выборочная обработка элементов массива

1. Переформирование массива

А) Без изменения исходных размеров массива

Б) С изменением размеров исходного массива.

1. Одновременная обработка нескольких массивов или подмассивов.

А) С синхронным изменением индексов.

Б) С произвольным изменением индексов

1. Поисковые задачи.

Выделение перечисленных классов обусловлено тем, что каждый из них имеет определенную методику обработки, получившую название приемов программирования данного класса задач. Как правило, в реальной жизни эти задачи в чистом виде встречаются довольно редко (в практикумах по программированию и в лабораторных работах). Однако, любая сложная задача может быть разбита методом пошаговой детализации на более простые задачи, для которых уже известны приемы программирования. Кроме того, специфика реализации всех классов задач зависит от количества индексов массивов.

1.1Основные приемы программирования обработки одномерных массивов.

Одномерными называются массивы, имеющие один тип индексов. Описание массива может быть выполнено в разделе описания переменных в разделе VAR:

VAR A,B:array [1..10] of real; {массив из 10 вещественных чисел}

C:array[BOOLEAN] of char; {массив символов из двух значений}

d:array [char] of integer; {массив целых чисел на 256 значений}

или с предварительным описанием типа в разделе TYPE:

TYPE Bmas=array[BOOLEAN] of char; { тип - массив символов из двух значений}

Cmas= array [char] of integer; {тип - массив целых чисел на 256 значений}

Rmas= array [1..10] of real; { тип - массив из 10 вещественных чисел}

VAR A,B:Rmas;

C:Bmas;

d:Cmas;

Рассмотрим наиболее распространенные приемы программирования обработки одномерных массивов.

1.1.1Первый класс задач

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

Рассмотрим некоторые типовые алгоритмы задач первого типа.

Пример1. Пусть необходимо ввести или вывести массив. Для этого нужно последовательно перебрать все элементы массива. Если количество вводимых элементов известно заранее, то для этой операции удобно использовать счетные циклы. При неизвестном количестве элементов лучше использовать циклы с пред или пост условиями.. При выводе количество элементов известно всегда. Алгоритм, при помощи которого осуществляется ввод и вывод одномерного массива A(n) представлен на рис. 4.1.

Рис. 4.1

Рис. 4.2

Пример 2. Часто возникает задача нахождения наибольшего или наименьшего элемента массива (например, при построении графика функции). Здесь, можно использовать следующий прием (см. рис. 4.2). Пусть нам нужно найти наибольший элемент массива. Вспомогательной переменной max присваивается значение первого элемента массива, затем последовательно все элементы массива сравниваются с переменной max, если max оказывается больше, чем очередной элемент, то max присваивается новое значение.

Пример 3. Пусть необходимо найти среднее арифметическое значение положительных элементов целочисленного массива, кратных трем. Для решения этой задачи необходимо двум вспомогательным переменным Sum и Kol, которые будут использоваться для накопления суммы требуемых элементов и их количества, присвоить нулевые значения. После этого осуществляется перебор всех элементов и, если очередной удовлетворяет условию, его значение добавляется к содержимому переменной Sum, а значение переменной Kol увеличивается на единицу. В конце просмотра всего массива среднее арифметическое может быть определено путем деления накопленной суммы на количество найденных элементов. Алгоритм решения задачи представлен на рис. 4.3.

Рис.4.3

1.1.2Второй класс задач.

Примерами подобной обработки служат: замена значений некоторых элементов на другие в соответствии с определенными условиями, сортировка массивов по убыванию, возрастанию, и по любому другому признаку, перестановки и сдвиги различного характера и др. Особенностью этого класса задач является то, что несмотря на постоянство количества элементов массива, для перестановки или замены элемента сначала его необходимо найти. Таким образом, чтобы преобразовать массив, требуется несколько раз его просмотреть. Поэтому даже для одномерного массива требуется применение нескольких вложенных циклов. Рассмотрим несколько типовых приемов.

Пример1. Пусть необходимо заменить все отрицательные элементы массива на нулевые

Пример 2. Переформировать массив таким образом, чтобы сначала шли все положительные элементы, затем отрицательные и в конце - нулевые.

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

1.1.2.1Сортировка массивов

Сортировка – это изменение положения элементов в массиве таким образом, что элементы становятся упорядоченными по некоторому закону. Для любого алгоритма оценивается вычислительная сложность, которая определяется зависимостью времени сортировки от количества сортируемых элементов. Чем меньше это время, тем более эффективен алгоритм. Кроме того, на практике интересны такие методы сортировки, которые позволяют экономно использовать оперативную память. Поэтому рассмотрим только такие алгоритмы, в которых не предполагается использование дополнительных массивов.

Сортировка с помощью выбора

Сортировка с помощью выбора представляет собой один из самых простых методов сортировки. Он основан на следующих принципах:

1. Выбирается наименьший элемент из всего массива.

2. Найденный наименьший элемент меняется местами с первым элементом.

1. Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый большой элемент массива.

Пример алгоритма с помощью выбора приведен на рисунке 5.1

Рис. 5.1

Сортировка с помощью обмена

Алгоритм прямого обмена основывается на сравнении и смене мест для пары соседних элементов. Сравнения продолжают до тех пор, пока не будут упорядочены все элементы. Такой метод широко известен под именем «пузырьковая сортировка», т.к. элементы массива можно рассматривать как пузырьки, которые поднимаются к началу массива.

Пусть, например, массив состоит из элементов (2, 5, 12, 1, 8, 4). Если сортировать массив по возрастанию, то после первого «прохода» по массиву мы получим следующий массив (2, 5, 1, 8, 4, 12). После второго «прохода» - (2, 1, 5, 4, 8, 12), после третьего – (1, 2, 4, 5, 8,12).

В своем простейшем виде алгоритм сортировки с помощью обмена представлен на рисунке 5.2.

Для улучшения алгоритма можно не только запоминать были ли перестановки в процессе некоторого прохода, но и место последнего обмена. Ясно, что все пары соседних элементов больше этого элемента уже находятся в желаемом порядке. Поэтому просмотры можно заканчивать на этом индексе.

Сортировка методом вставки

Алгоритм сортировки с помощью вставки можно описать следующим образом. При каждом шаге, начиная с i=2, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность на нужное место. В реальном процессе поиска подходящего места удобно сначала сравнивать извлеченный элемент с очередным элементом a_j, а затем либо a_j сдвигается вправо, либо a_i вставляется на освободившееся место. Процесс поиска может закончиться при выполнении одного из двух следующих условий: либо найден элемент a_j меньший, чем a_i, либо достигнут левый конец массива.

Такой типичный случай повторяющегося процесса с двумя условиями окончания позволяет нам воспользоваться хорошо известным приемом «барьера». Для этого необходимо расширить диапазон индекса в описании массива от 0 до n. Алгоритм сортировки приводится на рисунке 5.3.

Рис.5.2

Рис. 5.3

Метод Шелла

Метод состоит в том, что упорядочиваемый массив разделяется на группы таким образом, что в каждой группе находятся элементы, отстоящие друг от друга на расстоянии d. Каждая группа сортируется методом вставки, затем массив делится на новые группы с шагом d-1 и т.д. пока количество групп не станет равным единице. Обычно d выбирается таким образом, чтобы в каждой группе находилось два элемента, т.е. d=[n/2].

1.1.3Третий класс задач.

К задачам третьего типа относятся задачи по формулировке сходные с задачами первого и второго классов, но обработка ведется не надо всеми элементами массива, а только теми, которые имеют вполне определенное значение индексов. Поэтому, особенностью этого класса задач является наличие определенного закона изменения индексов рассматриваемых элементов. С целью уменьшения времени работы программы и увеличения ее эффективности, программисту следует найти этот закон и обеспечить его исполнение. В зависимости от закона изменения индексов могут использоваться все виды циклов, а также их сочетание.

Пример 1. Определить максимальный элемент, среди элементов целочисленного массива, стоящих на четных местах.

Пример 2. Заменить каждый третий элемент массива значением 0- если он четен и остатком от деления элемента на два, если он нечетен.

1.1.4Четвертый класс задач.

Примерами этого класса задач могут служить: вычеркивание и вставка элементов, отвечающих определенным условиям или обладающих заданными признаками и т. д. При этом, для удаления или добавления элемента может производиться как поэлементная, так и выборочная обработка элементов массива. Особенностью этого класса задач является изменение размеров исходного массива. Кроме того, вычеркивание или вставка элементов требуют сдвига всех элементов той части массива, которая расположена после удаляемого или вставляемого элемента. Реализация алгоритмов этого типа задач потребует вложенных циклов. При этом, внутренний цикл для сдвига можно выполнить, используя счетный цикл. Внешний цикл обхода содержит переменную верхнюю границу, поэтому лучше использовать циклы с пред или пост условием. Если на соответствие условию проверяются все элементы, то параметр внешнего цикла меняется на 1. Однако после сдвига на месте старого анализируемого элемента может оказаться элемент опять отвечающий требуемому условию. Поэтому для определения количества выполнения цикла сдвигов необходим цикл с пост условием, а не оператор ветвления (используется три вложенных друг в друга цикла). При выборочном анализе элементов массива параметр внешнего цикла меняется на разную величину, в зависимости от наличия или отсутствия сдвига и для определения выполнять сдвиг или нет можно использовать оператор условной передачи управления. При большом количестве удаляемых или вставляемых элементов вычислительная сложность таких алгоритмов достаточно велика.

Пример 1. Пусть необходимо вычеркнуть из массива целых чисел все те числа, которые кратны 5. Для решения задачи необходимо, обходя весь массив найти очередной удаляемый элемент, а затем путем циклического сдвига перенести все элементы, расположенные после него. Полученный массив окажется на 1 элемент меньше. Изменив размер массива следует продолжить перебор элементов.

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

1.1.5Пятый класс задач.

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

1.1.6Шестой класс задач.

Примерами подобного рода задач могут служить поиск первого отрицательного, первого положительного и любого первого элемента, отвечающего некоторому условию, поиск единственного элемента, равного некоторому конкретному значению. Особенность задач этого класса в том, что нет необходимости просматривать весь массив. Просмотр нужно закончить сразу, как только требуемый элемент будет найден. При этом может производиться как поэлементный просмотр, так и выборочная обработка массива. Однако, в худшем случае, для поиска элемента требуется просмотреть весь массив. Такой тип поиска называется линейным. Если массив не очень большой, затраты времени линейного поиска не столь заметны. Но при солидных объемах информации время поиска становится серьезным показателем. Поэтому существуют методы, позволяющие уменьшить время поиска: поиск с барьером и двоичный поиск. Чаще всего при программировании поисковых задач используются циклы с пред или пост условием, в которых условие выхода формируется из двух условий. Одно условие - пока элемент не найден, а второе - пока есть элементы массива. После выхода из цикла осуществляется проверка по какому из условий произошел выход.

Рассмотрим следующие примеры.