FIRST (Методичка С++), страница 3

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

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

Рисунок 3.1 – Ввод-вывод одномерного массива

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

Пример 3.2. Сравнительно часто встречается задача нахождения наибольшего или наименьшего элемента массива (например, при построении графика функции).

Вспомогательной переменной max присваивается значение первого элемента массива, затем последовательно все элементы массива сравниваются с переменной max, если значение max оказывается больше, чем очередной элемент, то max присваивается новое значение (см. рисунок 3.2).

Рисунок 3.2 – Схема алгоритма нахождения максимального элемента массива

Пример 3.3. Пусть необходимо найти среднее арифметическое значение положительных элементов целочисленного массива, кратных трем. Для решения этой задачи сначала необходимо двум вспомогательным переменным Sum и Kol, которые будут использоваться для накопления суммы требуемых элементов и их количества, присвоить нулевые значения (см. рисунок 3.3).

Рисунок 3.3 – Схема алгоритма нахождения среднего арифметического элементов, кратных 3

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

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

Несложно увидеть, что схема очень похожа на предыдущую, поскольку, как в предыдущем алгоритме, осуществляется последовательная проверка всех элементов массива.

Схема алгоритма решения задачи показана на рисунке 3.4.

Рисунок 3.4 – Схема алгоритма замены отрицательных элементов массива нулями

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

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

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

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

Рисунок 3.5 – Схема алгоритма поиска максимального элемента, записанного на четном месте

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

В этом случае нас интересует каждый третий элемент, поэтому количество просматриваемых элементов уменьшается втрое, а значение k в цикле увеличивается на три (см. рисунок 3.6).

Рисунок 3.6 – Схема алгоритма замены каждого третьего элемента массива

7.3Изменение порядка следования элементов без изменения размеров исходного массива. Сортировка массива

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

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

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

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

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

Окончательный вариант алгоритма приведен на рисунке 3.7.

Рисунок 3.7 – Схема алгоритма перестановки элементов массива

Однако наиболее распространенными задачами второго класса являются сортировки массивов.

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

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

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

• найденный наименьший элемент меняется местами с первым элементом;

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

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

Рисунок 3.8 – Схема алгоритма сортировки выбором

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

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

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

Рисунок 3.9 – Схема алгоритма обменной сортировки

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

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

Рисунок 3.10 – Схема алгоритма сортировки вставками

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

7.4Переформирование массива с изменением его размеров

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

Пример 3.7. Пусть необходимо вычеркнуть из массива целых чисел все числа, кратные 5.