Для решения задачи можно предложить два алгоритма:

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

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

Рисунок 3.11 – Схемы алгоритма решения задачи:

а – с двумя циклами; б – с одним циклом

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

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

Пример 3.8. Предположим, нам необходимо переформировать массив вещественных чисел, добавив в него нулевые элементы после положительных элементов, стоящих на четных местах.

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

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

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

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

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

Пример 3.9. Даны два массива, отсортированные по возрастанию. Объединить их в третий массив, сохраняя сортировку.

В алгоритме (см. рисунок 3.13) для каждого массива используется свой индекс и своя граница индекса.

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

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

7.6Поиск в массиве единственного элемента, отвечающего некоторому условию

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

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

Пример 3.10. Задан целочисленный массив из n элементов. Присвоить переменной k значение true, если в массиве существуют два одинаковых элемента, стоящих рядом, и false в противном случае.

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

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

Пример 3.11. Необходимо определить среди элементов, стоящих на четных местах первый отрицательный элемент.

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

8Приемы обработки матриц

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

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

8.1Последовательная обработка элементов матрицы

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

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

Пример 3.12. Задана квадратная целочисленная матрица размера nn. Найти наибольший элемент матрицы и количество таких элементов.

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

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

Пример 3.13. Задана целочисленная матрица A(m,n). Вычислить сумму каждой стоки и результат записать в массив B(n).

Для вычисления суммы элементов некоторой строки с номером i необходимо организовать цикл для перебора всех элементов данной строки. Поэтому параметром этого цикла следует выбрать номер столбца j. Перед циклом с параметром j необходимо задать начальное значение суммы S=0. После окончания цикла результат присваивается соответствующему элементу массива b. Для обеспечения обхода всех строк матрицы параметром внешнего цикла следует выбрать номер строки i (см. рисунок 3.17).

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

8.2Изменение порядка следования элементов без изменения размеров исходной матрицы.

В качестве примеров задач данного типа для матриц рассмотрим задачу перемещения элементов.

Пример 3.14. Дана действительная квадратная матрица порядка 2n. Получить новую матрицу, переставляя ее блоки размера nn в соответствии с рисунком.

Для решения этой задачи нужно определить правило, по которому будут преобразовываться индексы матрицы. Будем считать, что после преобразования получается новая квадратная матрица размерности 2n. Тогда внимательно изучив соответствие между элементами матрицы A и матрицы B, получаем следующий закон преобразования:

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

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

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

Литература

1. Г.С. Иванова. Основы программирования. Учебник для ВУЗов. – М.: Из-во МГТУ им. Н.Э. Баумана, 2007.