Алгоритмы обработки двумерных массивов
Двумерный массив– это структура однотипных элементов,
расположенных в виде таблицы значений. Такое
представление значений соответствует
математическому понятию двумерного массива.
Каждый элемент в двумерном массиве
идентифицируется номером строки и номером
столбца, на пересечении которых он расположен.
Например, в двумерном массиве А, изображенном на
рис. 24, элемент со значением 5 расположен на
пересечении третьей строки и второго столбца.
Этот элемент будет обозначаться как А(3, 2). А элемент А(1, 4) имеет значение, равное нулю. Такое представление набора значений позволяет выполнять обработку как отдельных значений в двумерном массиве, так и последовательности значений, расположенных в строках или столбцах.
В дальнейшем будем считать, что для двумерного массива A(N, М) в
обозначении элемента А(i, j) первое значение i соответствует номеру
строки и изменяется от 1 до N, а j – номеру столбца и изменяется от 1 до
М. В отличие от одномерного массива, в котором использовался только
один номер для определения местоположения элемента и требовался
только один цикл для ввода элементов, в двумерном массиве для
обработки элементов необходимы два вложенных друг в друга цикла.
Внешний цикл предназначен для изменения номера строки i, а второй,
внутренний, – для изменения номера столбца j в текущей строке i.
На рис. 25 представлен простой алгоритм ввода элементов, построенный в виде структуры из вложенных циклов. В дальнейшем при рассмотрении
алгоритмов обработки элементов двумерного массива в целях сокращения их размера фрагмент ввода элементов будем заменять отдельным блоком ввода.
Пример 13. Составить алгоритм поиска максимального значения в двумерном массиве.
Решение. Поиск максимального элемента в двумерном массиве осущест-вляется аналогично поиску в одномерном массиве. Отличие состоит в том, что для обработки двумерного массива используем два вложенных цикла. Обозначим максимальный элемент переменной МАХ. Значение этой переменной будет меняться на каждой итерации цикла, если очередное значение элемента массива окажется больше МАХ (рис. 26).
Пример 15. Составить алгоритм вычисления суммы элементов двумерного
массива А(1.. N, 1..М), расположенных выше главной диагонали.
Решение. Рассмотрим алгоритмическое решение, представленное на рис.28.
Для определения условия расположения элементов выше главной диагонали рассмотрим двумерный массив в обобщенном виде на рис. 29. Обратим внимание на диагональные элементы: номер строки и номер столбца совпадают. Значит для определения элементов на главной диагонали достаточно использовать условие I = J, где I – номер строки, J – номер столбца.
Для определения элементов выше главной диагонали достаточно использовать условие I<J, ниже главной диагонали – I>J. По условию задачи требуется найти сумму элементов двумерного массива А(1.. N, 1..М), расположенных выше главной диагонали, значит, применим условие I<J, связывающее такие параметры элемента массива как номер строки I и номер столбца J.
Теперь алгоритмическое решение задачи вычисления суммы элементов двумерного массива, расположенных выше главной диагонали, приведенное на рисунке 28, становится более понятным. Данный алгоритм содержит два вложенных цикла, каждый из которых относится к циклу с постусловием.
Задания для самостоятельного выполнения
Цель заданий. Приобрести умения в синтезе формальной и
алгоритмической моделей решения задач. Сформировать компетенции
анализа и синтеза при решении простых задач циклической обработки
значений двумерного массива.
Порядок выполнения. Составить формальное и алгоритмическое
решения следующих задач обработки значений двумерных массивов:
1. Ввести двумерный массив А(N, M). Составить визуальный алгоритм
замены всех нулевых элементов на минимальный элемент.
2. Ввести двумерный массив А(N, N). Составить визуальный алгоритм
подсчета среднего арифметического значений двумерного массива. Найти
отклонение от среднего у элементов первой строки.
3. Ввести двумерный массив А(N, N). Составить визуальный алгоритм
подсчета среднего арифметического значения двумерного массива.
Вычислить отклонение от среднего для всех элементов двумерного
массива.
4. Ввести двумерный массив А(N, N). Составить визуальный алгоритм
замены всех отрицательных элементов на среднее арифметическое
значение элементов двумерного массива.
5. Составить визуальный алгоритм нахождения числа строк двумерного
массива А(N, N), количество отрицательных элементов в которых
больше Р.
6. Ввести двумерный массив размером 7*4. Найти наибольший элемент
двумерного массива. Удалить строку с максимальным элементом.
7. Ввести двумерный массив размером 7*4. Поменять столбец с
максимальным элементом с первым столбцом двумерного массива.
8. Ввести двумерный массив размером 7*7. Найти максимальный элемент
двумерного массива, расположенный ниже побочной диагонали.
9. Ввести двумерный массив размером 7*4. Найти наименьший элемент
двумерного массива. Перенести строку, содержащую этот элемент в конец.
10. Ввести двумерный массив размером 7*4. Найти максимальный элемент двумерного массива. Поменять столбец, содержащий этот элемент с последним столбцом двумерного массива.
11. Ввести двумерный массив размером 6*4. Найти минимальный элемент
двумерного массива. Переставляя строки и столбцы, добиться того, чтобы
элемент оказался в правом нижнем углу.
Контрольные вопросы
1. Дайте определение массива.
2. Чем массив отличается от последовательности значений?
3. Что определяет номер элемента массива?
4. Сформулируйте свойства массива.
5. Какие типы алгоритмических структур применяются для обработки
массива?
6. Какие существуют способы обработки одномерного массива?
7. В чем заключается сортировка одномерного массива?
8. Опишите методы сортировки одномерного массива.
9. Приведите пример и алгоритм сортировки массива.
10. Опишите методы обработки упорядоченных массивов.
11. В чем заключается сущность метода двоичного поиска?
12. Чем двумерный массив отличается от одномерного?
13. Как осуществляется доступ к элементу двумерного массива?
14. Какие существуют способы обработки двумерного массива?