Лекция 8. Матрицы. Параметрический цикл (часть 2) (Воробьева И.А. «Информатика. Язык Питон» (2016))

1Воробьева И.А. «Информатика. Язык Питон»Массивы (продолжение-2)Простейшие алгоритмы в массивах: две задачи за один проход. Просмотрмассива: полностью, по частям, с досрочным выходом.5.5. Остальные операции в матрицах. Просмотр массивов почастямФункция len() и матрицы.Пусть задана матрицаиз двух строк и трех столбцов.Применив функцию len() к матрице , мы получим число строк в :len(C) вернет значение «2».Если применим len() к любой из строк, то получим число столбцов:len(C[0]) или len(C[1]) вернут значение «3».Это легко объяснимо, если вспомним, что матрица, по сути, в Python –это массив массивов.Присвоение (копирование) матриц допустимая операция, но имеетту же особенность, что и присвоение одномерных массивов. Напомним,что будет при простом присваивании (копировании):A=[[9,9],[8,8]]# целочисленная изменяемая матрицаprint( A) на экранеB=A# присвоив матрицуматрице , мы лишь указали, чтотеперь одному объектусоответствует два имени иprint( B) на экранеДействительно, изменим первый элемент в матрице :B[0][0]=78print(B) на экранеprint(A) на экране2Воробьева И.А.

«Информатика. Язык Питон»Поэтому, если мы хотим получить действительно два самостоятельныхобъекта с одинаковыми значениями, нужно использовать безопасноекопирование объектов:for i in range(len(A)):for j in range(len(A[i])):B[i][j]=A[i][j]Обмен содержимым между двумя элементами матрициспользуемвспомогательнуюпеременную подходящего типа,например, Zer=0 # целое дляпусть m[6][3] (содержит «24») целочисленных матрициm[5][7] (содержит «-75»)надо m[6][3] ↔ m[5][7]Zer= m[6][3]m[6][3]= m[5][7]m[5][7]= Zerтеперь m[6][3] (содержит «-75»)иm[5][7] (содержит «24»)Еще способ:Обозначим m[6][3] через A, а рекомендуется только для целыхm[5][7] через B.А=A+B; B=A-B; A=A-BЧасто в задачах требуется найти элемент или подсчитатьопределенную величину только на какой-то части элементов. Мы ужерешали задачу поиска экстремума среди элементов, удовлетворяющихзаданному условию: «Задача 5.1.

Найти минимальный элемент и егономер среди положительных элементов целочисленного массива ».Рассмотрим еще один вариант задачи. Теперь будем вычислятьзаданное выражение на той части элементов массива, где выделяютсяне значения элементов, а их индексы.3Воробьева И.А. «Информатика. Язык Питон»Алгоритм MEANвычисления среднего арифметического навыборочной части элементов массиваЗадача 5.2. Найти среднее арифметическоевсех элементовцелочисленного массива с нечетными индексами (индексацияначинается с нуля).

Размерность массива –.Альтернатива: если размерность массива меньше минимальноразумной (в данной задаче не подходит массив из одного элемента,так как первый элемент имеет четный индекс «0» и нам просто будетнегде считать среднее арифметическое), то сообщить об этом.Метод. Для вычисления среднего арифметического, нам нужны двевеличины:– для суммирования подходящих элементов и– для подсчета их числа.

Тогда, если. Если, что означает отсутствие подходящих элементов (индексов),тогда выведем сообщение«Негде искать среднееарифметическое».o Начальное значение;o Начинаем перебор всех элементов , начиная со второго с шагомдва (), попадет ли индексв диапазон зависит от его четности: Накапливаем сумму элементов; Накапливаем число элементов;o Если по окончании просмотра всех элементов значение,нет элементов c нечетными индексами, выводим сообщение обэтой альтернативной ситуации;o Есливычисляеми выводим результат.4Воробьева И.А.

«Информатика. Язык Питон»Блок-схема (алгоритм) решения задачи.началоВвод/вывод Kol, DSums=0; S=0For i=1; kol-1; +2Sums = Sums + D[i]s=s+1НетMidififs=0?Да«Негде искать Mid»конецВ матрицах частичный просмотр связан со следующими задачами: поменять местами столбцы или строки с указанными номерами; транспонировать квадратную матрицу; искать элементы над/под диагоналями квадратных матриц; зеркальный поворот матриц относительно столбцов или строк и т.п.5Воробьева И.А.

«Информатика. Язык Питон»Операции с элементами, расположенными над (под) главной ипобочной диагоналями квадратной матрицыГлавная диагональ – определена только для квадратных матриц. Это всеэлементы, у которых индексы строк и столбцов равны, т.е. когда.Для индексов элементов, лежащих над главной диагональю, верно, что, а для индексов элементов, лежащих под главной диагональю,верно, что.Побочная диагональ – определена только для квадратных матриц. Этовсе элементы, у которых индексыстолбцов зависят от индексовстрок по правилу:.Легко заметить, что для индексов элементов, лежащих над ипобочной диагональю простой зависимости нет: над диагональю; на диагонали; под диагональю.подВАЖНО! Для прохода по главной или побочной диагоналям достаточноОДНОГО цикла «for».6Воробьева И.А.

«Информатика. Язык Питон»Алгоритм выполнения любой операции ТОЛЬКО надэлементами выше (ниже) главной и выше (ниже) побочнойдиагоналейПусть есть квадратная матрицастрок, – индекс столбцов матрицы,размерности.Ниже главной диагоналии– индексВыше главной диагоналиначалоначалоFor i=0; n-2;+1For i=1; n-1; +1For j=i+1; n-1; +1For j=0; i-1; +1Операция над a[i][j]Операция над a[i][ j]конецконецпример транспонирования квадратнойматрицы зашагов и бездополнительного выделения памяти(«на месте»)пример вывода на экран толькоэлементов над главной диагональюfor i in range (1,n) : # цикл по строкамfor i in range (n-1) : # цикл по строкамi=1,2,…,n-1for j in range (i) : # i-строкапо j=0,1,…,i-1 столбцамz = a[i][ j] # операция обменаi=0,1,…,n-2for j in range (i+1,n) : # i-строкапо j=i+1,i+2,…,n-1столбцамprint(a[i][j]) # операция над элементомa[i][j] = a[j][i]a[j][i] = zИспользовали способ обхода элементов матрицы за «один проход» припомощи двух вложенных циклов «for».

Обратите внимание на диапазонзначений индексов и – мы не просматриваем все элементы, атолько те, которые нужно, что гораздо эффективней..Ниже побочной диагоналиВыше побочной диагонали7Воробьева И.А. «Информатика. Язык Питон»началоначалоFor i=1; n-1; +1For i=0; n-2; +1For j=n-i; n-1; +1For j=0; n-2-i; +1Операция над a[i][j]Операция над a[i][j]конецпример вывода на экран толькоэлементов под побочной диагональюfor i in range (1,n) : # цикл по строкамi=1,2,…,n-1for j in range (i) : # i-строкапо j=0,1,…,i-1 столбцамprint(a[i][ j]) # операция над элементомконецпример вывода на экран толькоэлементов над побочной диагональюfor i in range (n-1) : # цикл по строкамi=0,1,…,n-2for j in range (i+1,n) : # i-строкапо j=i+1,i+2,…,n-1столбцамprint(a[i][ j]) # операция над элементомИспользовали способ обхода элементов матрицы за «один проход» припомощи двух вложенных циклов «for».

Обратите внимание надиапазон значений индексов и – мы не просматриваем всеэлементы, а только те, которые нужно, что гораздо эффективней.Замечание 5.4. Очевидно, что меняя диапазоны индексов и шаг впараметрических циклах, можно просматривать матрицу разными связнымичастями и в разных направлениях. Например, можно просматривать только левуюполовину матрицы или правую, верхнюю половину или нижнюю. Можнопросматривать любую из четвертей матрицы. Обратите внимание, что если взадаче требуется найти последний элемент, удовлетворяющий условию,например, «последний отрицательный», тогда выгодно просматривать матрицу«снизу-вверх и справа-налево» одновременно с итерационными циклами.Матрицу можно просматривать, когда внешний цикл – это столбцы, а не строки.Все зависит от поставленной задачи, но вариантов прохода по матрицам намногобольше, чем привычное «сверху-вниз и слева-направо».8Воробьева И.А. «Информатика.

Язык Питон»Дополнительные варианты прохода по матрицам привыполнении различных задачПусть задана прямоугольная целочисленная изменяемая матрицаA(n, m):n=3m=5A = [ [ 0, 1, 5, -5, 2],[ 0, 0, 0, 10, 0],[-10, 1, 3, -5, -2] ]# 0-я строка# 1-я строка# 2-я строкапросмотр матрицы «снизу-вверх и справа-налево»for i in range (n-1, -1, -1) : # цикл по строкам i=n-1, n-2,…,1,0 ; i= 2, 1, 0 для n=3for j in range (m-1, -1, -1) : # i-строка по j=m-1,m-2,…,1,0 столбцам; j= 4, 3,2,1, 0 для m=5print(A[i][j]) # операция над элементомотражение матрицы относительно вертикалиz=0for i in range (n) : # цикл по строкам i=0,1,…,n-1for j in range (m//2) : # i-строка по столбцам j= 0, 1 для m=5z = A[i][ j] # операция обменаA[i][j] = A[i][m-1-j]A[i][ m-1-j] = zрезультат:A = [ [ 2, -5, 5, 1, 0],[ 0,10, 0, 0, 0],[-2, -5, 3, 1,-10] ]В примере выше использовано свойство целочисленного деления.Выражениебудет правильно работать в алгоритме отраженияматрицы относительно вертикали, как для нечетных значений , так идля четных.Также обратите внимание на индексы элементов обмена.Как произвести отражение матрицы относительно горизонтали,подумайте сами.9Воробьева И.А.

«Информатика. Язык Питон»5.6. Выполнение нескольких задач в матрицах за один проходПриведенные выше примеры, это типичная обработка нужныхэлементов матрицы за «один проход». В первом (внешнем) цикле «for»просматриваются нужные строки, во втором (внутреннем) – нужныестолбцы матрицы. На самом деле, там, где находится всего лишь одиноператор в примерах, могут выполняться гораздо более сложныезадачи.Задача 5.3. Найти среднее арифметическоенеотрицательныхэлементов квадратной матрицы, а также подсчитать, сколькотаких элементовв каждой отдельно взятой строке матрицы.Данные, которые уже заданы и которые потребуются:Вх.: – максимальное значение индексов строк и столбцов,;– матрица из целочисленных элементов, причем значенияэлементов:;Промежуточные:– индекс строк,;– индекс столбцов,;– общее число таких, что,диапазон:– сумма всех,диапазон:;;Вых.:– среднее арифметическое таких, что(обратите внимание, что для «неотрицательных» элементовиспользуем нестрогое неравенство, для «положительных» –нужно использовать строгое), диапазон:;– целочисленный массив длины ; Элементы массива –это число элементовв каждой строке матрицы A (1-йэлемент массива, для первой строки, 2-й – для второй строки ит.д.), диапазон:.10Воробьева И.А.