В. Ю. Наумов Введение в информатику
 Скачать 2.05 Mb.
|
|
j). Блок-схема алгоритма представлена на рис. 5.6. 145 Программа будет выглядеть следующим образом: i=0; i k ++ S = S + A[ I ][ j ] k ≠ 0 SrA = S/k вывод SrA ‘В массиве нет четных элементов’ Ввод A[ I ][ j ] i=0; i Начало Конец J=0; j 146 #include { int n,m,a[10][15]; cout<<”\nInput count of rows”; cin< } int s=0, k=0; for (int i=0; i } if (k!=0) { float sra=float(s)/float(k); cout<<”\nsra=”< } Поэлементная обработка массива с анализом может быть представлена некоторыми классическими алгоритмами. Наиболее известные и часто встречающиеся – алгоритмы поиска экстремальных по значению (максимум и минимум). Итак, для примера рассмотрим поиск максимума в двумерном массиве. Алгоритм точно такой же, как и для одномерного массива. Стоит только не забывать, что при просмотре меняются как строки, так и столбцы. Кроме того, необходима пара индексов для выяснения точного местоположения элемента с максимальным значением. За координаты отвечают переменные IMax, JMax, а за сам максимум переменная Max (рис. 5.7): 147 int imax=0, jmax=0, max=a[0][0]; for (int i=0; i { max=a[i][j]; imax=i; jmax=j; } Очевидно, что для поиска минимального элемента потребуется изменить знак в условии с «>» на «<», а имена переменных, в которых будут храниться искомые значения, следует заменить на IMin, JMin и Min. i=0; i j=0; j Max = A[i][j] IMax = i JMax = 0 IMax = 0 JMax = j 148 Алгоритмы поиска элементов не всегда могут быть такими простыми. В качестве примера рассмотрим еще одну задачу, которая решалась для одномерного массива. ПРИМЕР Найти наименьший среди нечетных элементов двумерного массива. Составим тестовый пример: вход: 8 1 3 1 5 0 7 6 2 1 9 4 A выход: Min = –5; IMin = 1; JMin = 0; Здесь при решении есть некоторые особенности, связанные с тем, что обрабатываемый массив двумерный. А в целом алгоритм практически такой же, как и в предыдущей задаче, и распадается на две части: поиск первого нечетного элемента и поиск минимума, при условии нечетности, начиная с найденного. Тут тоже воспользуемся для первой части задачи циклом с предусловием. Теперь нужно производить инкрементацию не только индекса столбца JMin, но и следить за своевременной инкрементацией индекса столбца IMin (рис. 5.8): 149 j=0; j && A[i, j]%2!=0 IMin = i A[IMin, JMin]%2==0 && Imin IMin = 0 JMin = 0 i=imin; i Jmin==M JMin = 0 IMin ++ Imin IMin, JMin ‘В массиве все элементы четные’ Рис. 5.7. Поиск минимального среди нечетных 150 int im in=0, jmin=0 while (A[imin,jmin]%2==0 && imin { jmin=0; imin++; } } for (int i=0; i } if (imin Flag, аналогично тому как это делалось для одномерного массива. Здесь будет все аналогично, за исключением добавления цикла по строкам и включения как индексов строк, так и столбцов (алгоритм рассматривать не будем). Вот еще одна типовая задача на максимумы и минимумы для двумерных массивов. ПРИМЕР В двумерном массиве поменять местами максимальный и минимальный элементы. Тут все просто. Ищем индексы максимума и минимума, а далее производим обмен в три действия (рис. 5.9). 151 #include { int n,m,a[10][15]; cout<<”\nInput count of rows”; cin< Конец i=0; i i=0; i i=0; i imin=0; jmin=0; j=0; j imax=i; jmax=j; A[i][j] jmin=j; buf = A[imax][jmax] A[imax][jmax]= A[imin][jmin] A[imin][jmin] = buf 2 1 1 2 Ввод n,m Рис. 5.8. Обмен максимума и минимума в двумерном массиве 152 cin>>a[i][j]; } int imax=0, jmax=0, imin=0, jmin=0; for (int i=0; i { imax=i; jmax=j; } if (a[i][j] < a[imin][jmin]) { imin=i; jmin=j; } } int buf=a[imax][jmax]; a[imax][jmax]=a[imin][jmin]; a[imin][jmin]=buf; for (int i=0; i } ПРИМЕР Далее можно рассмотреть задачу формирования из заданного массива нового. Из матрицы A получить новые одномерные массивы C и D. В C содержатся положительные компоненты матрицы A, а в D – отрицательные. Длины получившихся массивов сохраняются в переменных Nc и Nd соответственно. Тестовый пример может выглядеть так: вход: 1 5 4 2 3 3 0 6 7 0 8 0 A выход: 1 4 2 3 6 7 8 5 3 B D Листинг программы для блок-схемы (рис. 5.10): int nc=0, nd=0,c[15],d[15]; for (int i=0; i 153 if (a[i][j]>0) { c[nc]=a[i][j]; nc++; } else { d[nd]=a[i][j]; nd++; } 5.3. Обработка отдельных строк или столбцов матрицы Важным классом алгоритмов обработки двумерных массивов является построчная или постолбцовая обработка. Если вспомнить одно из A[i][j] > 0 j=0; j nd=0; nc++ A[i][j] < 0 D[nd] = A[i][j] nd++ i=0; i Рис. 5.9. Формирование из двумерного массива пары одномерных 154 определений двумерного массива, которое говорит, что это «массив одномерных массивов», то подход к поставленной задаче упрощается. Для решения таких задач можно воспользоваться алгоритмами показанными на рис. 5.11. Суть их сводится к тому, что внутри внешнего цикла помещаются действия, которые можно представить в виде алгоритма на одномерном массиве, если положить неизменным индекс строки i при построчном, или индекс j при постолбцовом проходе. В качестве примера можно решить, скажем, такую задачу: ПРИМЕР Найти сумму положительных элементов в каждой строке матрицы. Алгоритм решения состоит в следующем. Во внешнем цикле меняем индекс строки (рис. 5.12, а), а во внутреннем – решаем задачу поиска суммы элементов одномерного массива с последующим выводом результатов на экран (рис. 5.12, б). Индекс строки i фиксируем во внутреннем цикле. Поиск суммы обычный, по рекуррентной формуле: «сумма текущего равна накопленной сумме на предыдущем, плюс текущее». На каждом новом проходе (при изменении индекса строки i) происходит обнуление переменной, хранящей текущее значение суммы S. Для иллюстрации задачи предоставим тестовый пример: i=0; i б) Рис. 5.10. Построчная (а) и постолбцовая (б) обработка двумерного массива 155 вход: 1 4 8 0 2 1 0 4 5 3 2 7 1 0 8 A выход: 1 2 3 0 8 10 S S S Программная часть на языке C++ следующая: for (int i=0; i А теперь рассмотрим пример с обработкой элементов по столбцам. ПРИМЕР Переписать максимальные элементы каждого столбца двумерного массива A в одномерный массив B. Тестовый пример выглядит так: i=0; i б) j=0; j S= S + A[i][j] S= 0 Вывод S 1 2 шаг 1-2 Рис. 5.11. Поиск суммы положительных элементов в каждой строке 156 вход: 1 4 8 0 2 1 0 4 5 3 2 7 1 0 8 A выход: 2 0 4 0 8 B , Текст программы: int b[m]; for (int j=0; j } Можно рассмотреть еще одну подобную задачу, а именно: ПРИМЕР Отсортировать по возрастанию каждую строку матрицы, то есть: j=0; j а) б) i=0; i Max = A[i][j] Max = A[0][j] 1 2 шаг 1-2 B[ j ] = Max Рис. 5.12. Поиск максимума в каждом столбце 157 вход: 1 4 8 0 2 1 0 4 5 3 2 7 1 0 8 A выход: 8 4 2 1 0 5 0 1 3 4 7 1 0 2 8 A Для решения нужно вспомнить, как происходила сортировка одномерного массива. Ведь каждая строка в матрице, по сути,– одномерный массив. Потому, если опять воспользоваться разбивкой алгоритма на детали, то решение достаточно простое. Во внешнем цикле меняется индекс строки (рис. 5.14, а), а во внутреннем – происходит сортировка строки по индексу столбца j. В качестве метода сортировки возьмем пузырьковый. Видно, что алгоритм практически точно повторяет тот, который мы использовали для одномерного массива (рис. 5.14, б). Стоит обратить внимание на тот факт, что при решении данной задачи возникают циклы k=m-1; k>1; k-- j=0; j buf = A[i][j] A[i][j]= A[i][j+1] A[i][j+1] = buf i=0; i б) 1 2 шаг 1-2 Рис. 5.13. Сортировка каждой строки матрицы 158 двойной степени вложенности, т. е. задача решается в три цикла. Вот текст алгоритма на C++: for (int i=0; i { int buf = a[i][j]; a[i][j] = a[i][j+1]; a[i][j+1] = buf; } Для обработки элементов двумерного массива, на строки которого накладываются некоторые условия, нужно при просмотре этого массива внутрь циклов ставить условие не на элемент, а на индекс строки или столбца (в зависимости от условия задачи). ПРИМЕР Заполнить единицами каждый второй столбец матрицы, то есть вход: 1 4 8 0 2 1 0 4 5 3 2 7 1 0 8 A выход: 4 1 0 1 2 0 1 5 1 3 7 1 0 1 8 A Вот алгоритм с условием на индекс столбца (рис. 5.15, а): for (int j=0; j 159 Вообще, там, где происходит заведомо меньшее число проходов чем строк или столбцов в матрице, нет необходимости проводить полный перебор. Гораздо логичнее будет использовать или цикл с предусловием с нужным шагом по строкам/столбцам, или цикл for с меньшим числом проходов и с формулой прямого вычисления нужного индекса. ПРИМЕР Переставить местами соседние столбцы матрицы. Это означает следующее: вход: 1 4 8 0 2 1 0 4 5 3 2 7 1 0 8 A выход: 4 1 0 8 2 0 1 5 4 3 7 2 0 1 8 A Последний столбец остался без изменения, поскольку для него не нашлось пары. Очевидно, что число парных перестановок столбцов в два раза меньше, чем их количество в матрице. Алгоритм решения при помощи цикла for следующий (рис. 5.16, а): j=0; j i=0; i j % 2 == 0 j=0; j i=0; i Рис. 5.14. Обработка четных столбцов матрицы: при помощи цикла for а – с шагом 1; б – с шагом 2 160 for (int j=0; j } А если воспользоваться циклом while, то выглядеть это будет так (рис. 5.16, б): int j=0; while (j j = 0 а) б) i=0; i A[i][j*2-1] = A[i][j*2] buf = A[i][j*2-1] A[i][j] = buf A[i][ j+1] = A[i][j] buf = A[i][j+1] Рис. 5.15. Перестановка столбцов в матрице: при помощи цикла for (а); при помощи цикла while (б) 161 a[i][j+1] = a[i][j]; a[i][j] = buf; } j=j+2; } 5.4. Квадратные матрицы Достаточно интересным и важным классом двумерных массивов являются квадратные. Квадратные матрицы – это такие матрицы, у которых число элементов в строке равно числу элементов в столбце, т. е. M=N. В квадратных матрицах выделяют некоторые особенные групп-пы элементов. Это, прежде всего, главная и побочная диагонали. Особенностью элементов на главной диагонали является тот факт, что для каждого из них индекс строки равен индексу столбца, т. е. i==j. Если внимательно посмотреть на рис. 5.17, то можно вывести правило принадлежности элемента к побочной диагонали. Это правило можно выразить формулой для индексов j == N – i - 1. Для матрицы, изображенной на рис. 5.17, это действительно так. Покажем это: N = 4 => A[0,3](i=0, j=3) j=4-0-1=3 A[1,2](i=1, j=2) j=4-1-1=2 A[2,1](i=2, j=1) j=4-2-1=1 A[3,0](i=3, j=0) j=4-3-1=0 Если смотреть на элементы диагоналей, то видно что они похожи на одномерные массивы, расположившиеся вдоль диагоналей. Потому для их обработки достаточно одного цикла. 0,0 0 0,1 1 0,2 2 1,0 1,1 1,2 2,0 2,1 2,2 0 1 2 Главная диагональ Побочная диагональ 0,3 1,3 2,3 3,0 3,1 3,2 3,3 3 3 Рис. 5.16. Диагонали в матрице 162 ПРИМЕР Найти среднее арифметическое отрицательных элементов главной диагонали. Решение таково (рис. 5.18): int k=0, s=0; for (int i=0; i k ++ S = S + A[i][i] ‘На гл. диагонали нет отриц. элементов’ k = 0 S = 0 k != 0 SrA = S/k Вывод SrA Рис. 5.17. Среднее арифметическое отрицательных элементов главной диагонали 163 k++; s=s + a[i][i]; } if (k!=0) { float sra=(float)S/(float)k; cout<<”\nsra=”< А теперь рассмотрим такую задачу: ПРИМЕР Обменять элементы главной и побочной диагоналей местами. Обмен происходит следующим образом: вход: 4 2 8 9 3 6 0 1 6 7 8 0 5 3 2 1 A выход: 9 2 8 4 3 0 6 1 6 8 7 0 1 3 2 5 A Алгоритм простой (рис. 5.19): for (int i=0; i } Далее к особенным элементам стоит отнести верхний и нижний треугольники. Нижним треугольником называют главную диагональ и элементы под нею. Верхним треугольником называют главную диагональ и элементы над нею. Треугольники в матрице показаны на рис. 5.20. Условие нахождения элемента в нижнем треугольнике такое: i≥j. Для верхнего треугольника неравенство обратное: i≤j. i=0; i A[i][i] = A[i][N-i+1] A[i][N-i+1] = buf Рис. 5.18. Обмен диагоналей 164 Кроме элементов над и под главной, выделяют также элементы над и под побочной диагональю. Условие нахождения над побочной диагональю такое: j Для обработки элементов из треугольников матриц можно пользоваться двумя способами. 0,0 0 0,1 1 0,2 2 1,0 1,1 1,2 2,0 2,1 2,2 0 1 2 0,3 1,3 2,3 3,0 3,1 3,2 3,3 3 3 0,0 0 0,1 1 0,2 2 1,0 1,1 1,2 2,0 2,1 2,2 0 1 2 0,3 1,3 2,3 3,0 3,1 3,2 3,3 3 3 i≥j i≤j Рис. 5.19. Нижний и верхний треугольники в матрице i=0; i j=0; j ≥ j && A[i][j]==0 k ++ Рис. 5.20. Обработка нижнего треугольника с условием на индексах 165 Первый заключается в просмотре всех элементов с последующей проверкой условия принадлежности индексов элемента тому или иному треугольнику. Такой способ более надежен, однако зря расходует системные ресурсы, просматривая всю матрицу целиком. Треугольник – это примерно половина матрицы. Для более рационального использования ресурсов можно иначе задать границы изменения циклов. Однако, в этом случае больше вероятность риска ошибиться. |