Ничушкина Т.Н., Гуренко В.В. - Разработка алгоритмов простейших программ, страница 6

«Разработка алгоритмов простейших программ»41Рисунок 3.13 – Схема алгоритма слияния отсортированных массивов3.1.6. Поиск в массиве элемента, отвечающего заданному условиюКэтомуклассуотносятся,например,следующиезадачи:поискпервогоотрицательного, первого положительного и любого первого элемента, отвечающегонекоторому условию, поиск первого или единственного элемента, равного некоторомуконкретному значению, а также поиск всех элементов массива, отвечающих заданномуусловию. В рамках настоящего учебного пособия ограничимся задачей поиска первого илиединственного элемента, удовлетворяющего условию.ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»42Особенностью задачи является отсутствие необходимости просмотра всего массива:перебор элементов нужно закончить сразу, как только требуемый элемент будет найден.При этом может выполнять как поэлементный просмотр, так и выборочную обработкумассива.

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

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

на рисунке 3.14.ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»43Рисунок 3.14 – Схема алгоритма поиска пары одинаковых элементов в массивеПример 3.11. Среди элементов массива, стоящих на четных местах, найти первыйотрицательный элемент.Логика решения задачи ясна из схемы алгоритма, показанной на рисунке 3.15.Рисунок 3.15 – Схема алгоритма поиска в массиве первого отрицательного элемента на четном местеОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»443.2.

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

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

Кроме того, к этому классу могут быть отнесены и задачиввода-вывода матриц. Особенности программирования в данном случае, в основном, теже, что и для одномерных массивов (см. раздел 4.1.1).Рассмотрим некоторые типовые алгоритмы задач первого класса.Пример 3.12. Дана целочисленная квадратная матрица порядка n.

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

В остальном алгоритмрешения задачи (см. рисунок 3.16) схож с алгоритмом нахождения наибольшего элементаодномерного массива.ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»45Рисунок 3.16 – Схема алгоритма поиска наибольших элементов матрицыПример 3.13. Дана целочисленная матрица A(n, m). Вычислить сумму каждой строкии результат записать в массив B(n).Для нахождения суммы элементов строки с номером i необходимо организоватьцикл, перебирающий все ее элементы. Поэтому параметром этого цикла следует выбратьномер столбца j.

Перед циклом с параметром j необходимо задать начальное значениесуммы S=0. После окончания цикла результат присваивается элементу массива B(i). Дляобеспечения обхода всех строк матрицы параметром внешнего цикла назначаемпеременную i – индекс строки. Схема алгоритма показана на рисунке 3.17).ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»46Рисунок 3.17 – Схема алгоритма вычисления суммы элементов каждой строки матрицы3.2.2.

Изменение порядка следования элементов матрицыЗдесь, как и в задачах, рассмотренных в разделе 3.1.3, размер исходной матрицысохраняется, меняется лишь порядок следования ее элементов. В качестве примера задачданного класса рассмотрим задачу перемещения элементов матрицы.Пример 3.14. Дана действительная квадратная матрица порядка 2n. Получить новуюматрицу, переставляя ее блоки размера nn в соответствии с показанной схемой:Для решения данной задачи, как и других подобных задач, необходимопроанализировать, как будет происходить модификация индексов элементов матрицы всоответствии с поставленным условием изменения порядка их следования, и выработатьправило преобразования индексов.

Будем считать, что после преобразования исходнойматрицы А получается новая квадратная матрица В того же порядка 2n. ИзучивОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»47соответствиемеждуэлементамиматрицAиB,получаемследующийзаконпреобразования: A(i  n, j  n), A(i  n, j  n),B(i , j )   A(i  n, j  n), A(i  n, j  n),еслиi  n, j  n;еслиi  n, j  n;еслиi  n, j  n;еслиi  n, j  n.Схема алгоритма решения задачи представлена на рисунке 3.18.Рисунок 3.18 – Схема алгоритма перестановки элементов матрицыСледует отметить, что приведенные примеры не охватывают всего многообразиязадач на обработку матрицам.

Как было отмечено выше, в процессе алгоритмическогорешения многих из них используются приемы, применяемые при обработке одномерныхмассивов. Однако существуют и специфические приемы, относящиеся именно кматрицам. Они требуют отдельного, более детального рассмотрения, что выходит запределы задачи, которую ставили перед собой авторы настоящего учебного пособия.ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ»48Контрольные вопросы1. Что называют массивом? Каким образом определяется место каждого элемента в массиве?2.

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

Каковы особенности алгоритмизации задач, связанных с одновременной обработкойнескольких массивов?9. Какова особенность алгоритмического решения задач поиска в массиве элемента,отвечающего заданному условию? Какие типы циклов при этом чаще всего используются?10. В чем состоит специфика обработки матриц по сравнению с приемами обработкиодномерных массивов?11. В чем состоит особенность организации циклического процесса при последовательнойобработке всех элементов матрицы?12. Какую аналитическую работу необходимо выполнить перед составлением алгоритмарешения задачи, связанной с изменением порядка следования элементов в матрице?ОглавлениеНичушкина Т.Н., Гуренко В.В.

«Разработка алгоритмов простейших программ»49Литература1. Иванова Г.С. Программирование: учебник. – М.: КНОРУС, 2013. – 432 с. – (Бакалавриат).2. Демидович Б.П., Марон И.А. Основы вычислительной математики. М.: Изд-во «Лань»,2009. – 672 с.ОглавлениеНичушкина Т.Н., Гуренко В.В. «Разработка алгоритмов простейших программ».