информатика. Игнатьева Елена Александровна, Измайлова Елена Ивановна. Информатика. Электронный ресурс методические указания

• Название: Игнатьева Елена Александровна, Измайлова Елена Ивановна. Информатика. Электронный ресурс методические указания
• Дата: 20.06.2022
• Размер: 4.32 Mb.
• Имя файла: информатика.pdf
• Тип: Методические указания; #604814
• страница: 11 из 15

Операции с матрицами
Основные виды матриц
В математике матрицей называют прямоугольную таблицу значений, упорядоченных по строкам и столбцам, например, мат- рица A размера n  m имеет вид:













nm
2
n
1
n m
2 22 21
m
1 12 11
a a
a a
a a
a a
a
A
, где a ij
– элемент матрицы А, расположенный в i-ой строке j- ого столбца; m, n – количество строк и столбцов матрицы соот- ветственно.
Матрица характеризуется размерностью, то есть произведе- нием числа строк на число столбцов.
Элементы a ii
(i = j) образуют главную диагональ матрицы А.
Если количество строк и столбцов матрицы совпадают, т.е. n = m то матрицу называют квадратной, если не совпадают – прямоугольной матрицей.

136
Матрица размером 1  m называется вектором-строкой, раз- мера n  1 – вектором столбцом.
Нулевой называется матрица у которой элементы a ij
= 0.
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0












Единичной называется квадратная матрица, у которой на главной диагонали стоят 1, а все остальные элементы равны 0.
1 0
0 0
0 1
0 0
0 0
1 0
0 0
0 1












Диагональной является квадратная матрица, где все элементы
(кроме элементов, расположенных на главной диагонали) равны
0, т.е. a ij
= 0 при i  j.
2 0
0 0
0 8
0 0
0 0
5 0
0 0
0 9












Квадратная матрица A размерностью n  n называется сим- метричной (симметрической), если a ij
= a ji
1 2
3 4
2 5
6 7
3 6
8 9
4 7
9 0












Треугольной называется матрица порядка n  n, у которой одна часть элементов (либо над главной диагональю, либо под ней) равна 0.
1 0
0 0
2 3
0 0
4 5
6 0
7 8
9 10












1 2
3 4
0 5
6 7
0 0
8 9
0 0
0 10













137
Транспонированной матрицей A
T
, называется матрица у ко- торой строки полностью совпадают со столбцами исходной мат- рицы А, а столбцы – со строками матрицы А.
Основные операции с матрицами
Операции над матрицами определяются с помощью опера- ций над их элементами:
1. Две матрицы А и В размерностью n  m равны друг другу
(А = В) в том случае, если a ij
= b ij
;
2. Сумма матриц А и В размерностью n  m есть матрица
C(n  m), то есть С = A + B = (a ij
+ b ij
) = c ij
, где i = 1, 2, …, n; j = 1,
2, …, m;
3. Произведение матрицы А на скаляр  – есть матрица
С =   A = (  a ij
) = c ij
;
4. Произведение матрицы А размерностью n  m на матрицу
В размерностью m  r – есть матрица С размерностью n  r, то есть






m
1
k kj ik ij b
a с
, где i = 1, 2, …, n; j = 1, 2, …, m.
Ввод матриц
1. Блок схема формирования произвольной матрицы А раз- мерностью (n  m)приведена на рис 3.
2. Блок-схема формирования нулевой матрицы А размерно- стью (n  m) приведена на рис. 4.
3. Блок-схема формирования единичной матрицы А размер- ностью (n  n) приведена на рис. 5.

138
Рис. 3. Блок-схема формирования произвольной матрицы А(n ? m)
Рис. 4. Блок-схема формирования нулевой матрицы А(n  m)
4. Блок-схема формирования диагональной матрицы А размерностью (n  n) приведена на рис. 6.
5. Блок-схема формирования симметричной матрицы А размерностью (n  n) представлена на рис. 7.
6. Блок-схема формирования треугольной матрицы А раз- мерностью ( n  n ) представлена на рис. 8, 9.
Ввод N, M
I = 1, N, 1
A(I, J) = 0
J = 1, M, 1
Ввод N, M
I = 1, N, 1
Ввод A(I, J)
J = 1, M, 1

139
Рис. 5. Блок-схема формирования единичной матрицы А(n  n)
Рис. 6. Блок-схема формирования диагональной матрицы А(n  n)
Ввод N
I = 1, N, 1
J = 1, N, 1
I < > J
A(I, J)
A(I, J)
Ввод N
I = 1, N, 1
J = 1, N, 1
I < > J
A(I, J)
Ввод A(I, J)

140
Рис. 7. Блок-схема формирования симметричной матрицы А(n  n)
Рис. 8. Блок-схема формирования треугольной матрицы А(n  n) с нулями под главной диагональю
Ввод N
I = 1, N, 1
J = 1, N, 1
I > J
A(I, J)
Ввод A(I, J)
Ввод N
I = 1, N, 1
J = I, N, 1
I < > J
A(J, I) = A(I,
Ввод A(I, J)

141
Рис. 9. Блок-схема формирования треугольной матрицы
А(n  n) с нулями над главной диагональю
Вывод матриц
На рис. 10 представлена блок-схема вывода матрицы
А(n  n).
Рис. 10. Блок-схема вывода матрицы А(n  n)
I = 1, N, 1
Вывод A(I, J)
J = 1, M, 1
Ввод N
I = 1, N, 1
J = 1, N, 1
I  J
A(I, J)
Ввод A(I, J)

142
Операции над матрицами
1. Блок-схема умножения матрицы А размерностью
(n  m) на константу С и получения результирующей матрицы В представлена на рис. 11.
Рис. 11. Блок-схема умножения матрицы А(n ? m) на константу С и получения результирующей матрицы В(n ? m)
2. Блок-схема транспонирования матрицы А размерностью
(n  n) представлена на рис. 12.
Рис. 12. Блок-схема транспонирования матрицы А(n ? n)
I = 1, N, 1
J = 1, M, 1
B(I, J) = A(I, J)C
I = 1, N, 1
J = I + 1,
X = A(I, J)
A(I, J) =
A(J, I) = X

143 3. Блок-схема сложения матриц А и В размерностями
(n  m) и получения результирующей матрицы Стой же размер- ности представлена на рис. 13.
Рис. 13. Блок-схема А(n  m) и В(n  m) и получения результирующей матрицы С(n  m)
4. Блок-схема умножения матриц А(m  n) и В(n  l) и по- лучения результирующей матрицы С размерностью (m  l) пред- ставлена на рис. 14.
Рис. 14. Блок-схема умножения матриц А(m  n) и В(n  l) и получения результирующей матрицы С(m  l)
I = 1, N, 1
J = 1, M, 1
С(I, J) = A(I, J) +
I = 1, M, 1
J = 1, L, 1
C(I, J) = 0
C(I, J) = C(I, J) + A(I, K) 
K = 1, N, 1

144
3. ПОРЯДОК ВЫПОЛНЕНИЯ
1. Получить задание у преподавателя.
2. Выполнить задание в соответствии с вариантом.
3. Ответить на контрольные вопросы.
4. ЗАДАНИЕ
Варианты заданий для лабораторной работы по теме "мас- сивы"
1. Дан массив натуральных чисел. Найти количество и сумму элементов, кратных заданному числу К.
2. В целочисленной последовательности есть нулевые элементы. Создать массив из номеров этих элементов.
3. Дана последовательность натуральных чисел. Создать массив из четных чисел заданной последовательности. Если та- ких чисел нет, то вывести сообщение об этом.
4. Дана последовательность действительных чисел. Заме- нить все ее члены, большие заданного числа К, этим числом.
Подсчитать количество замен.
5. Дан массив действительных чисел. Поменять местами наибольший и наименьший элементы заданного массива.
6. Дан целочисленный массив. Напечатать те его элемен- ты, индексы которых являются степенями двойки (1, 2, 4, 8 и т. д.).
7. В массиве целых чисел найти наиболее часто встречаю- щееся число. Если таких чисел несколько, то определить наи- меньшее из них.
8. Дана последовательность целых чисел. Найти сумму ее членов, расположенных между максимальным и минимальным элементами (включая оба эти числа).
9. Дана последовательность целых чисел. Вывести произ- ведения всех пар соседних чисел.
10. В заданной последовательности определить максималь- ный элемент. Подсчитать количество элементов равных макси- мальному.
11. В массиве, содержащем номер месяца рождения каждо- го студента группы, подсчитать количество всех студентов, кото- рые родились в заданном месяце К, и напечатать их номера.

145 12. В области 10 районов. Заданы площади, засеваемые в каждом районе пшеницей, и урожай, собранный в каждом рай- оне. Определить среднюю урожайность пшеницы по каждому району и по области в целом.
13. Известны значения ежедневной температуры воздуха в марте. Найти среднюю температуру и количество теплых дней
(выше 0).
14. Даны натуральные числа помощью X1, X2, . . ., X10; Y1,
Y2, . . . , Y10. Определить количество точек с координатами
(Xi, Yi), которые лежат в круге с центром (125, 96) и радиусом 50.
15. Многочлен N-ой степени задан массивом своих коэф- фициентов. Определить коэффициенты первой производной за- данного многочлена.
16. Дана последовательность действительных чисел. Ука- зать те ее элементы, которые принадлежат отрезку [c, d].
17. Даны целые числа a
1
, a
2
, . . . , a n
. Определить только те числа, для которых выполняется условие a i
 i.
Варианты заданий для лабораторной работы по теме "элементарные операции с матрицами"
1. 0.5  (A
2
+ A
T
)
2. (A
2
+ E)  6
3. T  T
T
+ E
4. 3  (C
2
+ E)
5. (A
2
- E)  A
T
6. (2  T + E)  T
T
7. 2  A + (A + E)
2
8. C  (5  C - E)
9. (3  T
2
+ E)
T
10. C
2
+ 2  C + E
11. A  (4  A
T
+ E)
12. (E + 7  T
T
)  T
13. 5  (A + E)
2
14. 8  C
2
+ E
15. T  (3  T – E)
16. (7  A
2
+ E)
T

146 17. C + (E – 6  C
2
)
18. A
2
– 2  (A + E)
19. 3  T
T
+ E + T
2
20. 7  (A
T
+ E)
2
21. (E+C)  2 C
22. A  (5  A
T
+ E)
23. T – (T
T
+ E)
2
24. A
T
 (9  A – E)
25. C
2
– 8  (C + E)
26. A
2
+ E – 3  A
T
27. 2  T
2
– E + T
T
28. 2  (A - E)
T
 A
Обозначения: A, T, C, E – квадратные матрицы порядка N;
A – произвольная матрица;
T – треугольная матрица;
C – симметричная матрица;
E – единичная матрица.
5. КОНТРОЛЬНЫЕ ВОПРОСЫ
1. Что такое массив?
2. Одномерные и двумерные массивы.
3. Статические и динамические массивы.
4. Описание статических массивов.
5. Описание динамических массивов.
6. Функция Rnd.
7. Что такое матрица?
8. Расскажите об основных видах матриц.
9. Блок-схема формирования единичной матрицы.
10. Блок-схема формирования симметричной матрицы
11. Блок-схема транспонирования матрицы.
12. Блок-схема умножения матрицы А(m  n) на матрицу
В(n  l).

147
Лабораторная работа №
8
Сортировка массивов
1. ЦЕЛЬ РАБОТЫ
Целью работы является изучение методов сортировки и по- лучение практических навыков сортировки массивов.
2. ТЕОРЕТИЧЕСКИЕ ПОЛОЖЕНИЯ
Основные положения
В общем случае сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором оп- ределенном порядке.
Цель сортировки – облегчить последующий поиск элемен- тов в таком отсортированном множестве.
Мы встречаемся с отсортированными объектами в телефон- ных книгах, в оглавлениях книг, в библиотеках, в словарях, на складах – почти везде, где нужно искать хранимые объекты. Да- же малышей учат держать свои вещи "в порядке", и они уже сталкиваются с некоторыми видами сортировки задолго до того, как ознакомятся с азами арифметики.
Сортировка – пример задачи, которую можно решать с по- мощью многих различных алгоритмов, имеющих и свои достоин- ства, и свои недостатки. И выбирать алгоритмы, нужно исходя из конкретной постановки задачи.
Введем некоторые обозначения и понятия.
Если у нас есть элементы A
1
, A
2
,…, A
N
, то сортировка есть перестановка этих элементов так, чтобы при некоторой упорядо- чивающей функции F выполнялись отношения: F(A
K1
) ≤ F(A
K2
)
… ≤ F(A
KN
). Если сортировка происходит по убыванию, то знак отношения меняется на противоположный "≥". При решении практических задач упорядочивание массива, как правило, со- провождается некоторыми дополнительными действиями. На- пример, если A
1
,Y
1
; A
2
,Y
2
;…; A
N
,Y
N
– это значения аргумента A и некоторой функции Y = f(A), то перестановка этих аргументов

148 должна сопровождаться одновременной перестановкой и значе- ний функции.
Рассмотрим методы сортировки.
методом прямого включения
Такой метод широко используется при игре в карты. Эле- менты (карты) мысленно делятся на уже "готовую" последова- тельность A
1
, A
2
,…, A
i-1
, и "оставшуюся" (не сортированную) часть: A
i
, A
i+1
,…, A
N
Суть метода заключается в том, что при каждом i-ом шаге
(начиная с i = 2), из неотсортированной части извлекается i-ый элемент и помещается в "готовую" часть, при этом он вставляется на нужное место.
Текстовый алгоритм метода:
1. Начало.
2. Выполнить цикл, пока i имеет значения от 2 до N, шаг = 1: а) i-ый элемент (A(i)) поместить в ячейку A(0); б) присвоить j = -1, то есть j равно номеру элемента, нахо- дящегося слева от испытуемого (i-го) и таким образом стоящего в "готовой" последовательности; в) если А(0) ≥ А(j), то элемент А(0) поместить в ячейку
А(j+1), иначе элемент А(j) поместить в ячейку А(j+1), уменьшить значение j на единицу и вновь выполнить пункт в).
3. Конец.
На рис. 1 представлена блок-схема сортировки методом прямого включения.
Метод работает следующим образом: на i-ом шаге (начиная с i = 2) i-ый элемент помещается в свободную ячейку (например,
А(0)). Этот элемент сравнивается со стоящим в "готовой" части слева от него элементом. Если элемент А(0) меньше, то происхо- дит сдвиг вправо сравниваемого (j-го элемента) на одну позицию, после чего для сравнения берется следующий элемент. Если же элемент А(0) при сравнении оказывается не меньше, то он поме- щается на место, стоящее сразу за сравниваемым элементом.

149
Рис. 1. Блок-схема сортировки методом прямого включения
На рис. 2 приведен пример выполнения сортировки методом прямого включения.
Исходн ая последовател
4 4
5 5
1 2
4 2
9 4
1 8
0 6
6 7
А
(0)
I
= 2 4
4 5
5 1
2 4
2 9
4 1
8 0
6 6
7
I
= 3 4
4 5
5 1
2 4
2 9
4 1
8 0
6 6
7
I
= 4 1
2 4
4 5
5 4
2 9
4 1
8 0
6 6
7
I
= 5 1
2 4
2 4
4 5
5 9
4 1
8 0
6 6
7
I
= 6 1
2 4
2 4
4 5
5 9
4 1
8 0
6 6
7
I
= 7 1
2 1
8 4
2 4
4 5
5 9
4 0
6 6
7
I
= 8 0
6 1
2 1
8 4
2 4
4 5
5 9
4 6
7
Резуль- тат
0 6
1 2
1 8
4 2
4 4
5 5
6 7
9 4
Рис. 2. Пример сортировки методом прямого включения

150
Сортировка прямым включением больше подходит для слу- чая, когда сортируемые данные поступают последовательно (од- но за другим).
Сортировка методом прямого выбора
Суть метода заключается в следующем. Выбирается наи- меньший элемент в "оставшейся" (неотсортированной) части и меняется местами с первым элементом (в этой же неотсортиро- ванной части). После этого длина неотсортированной части уменьшается на один элемент (на первый), и весь процесс про- должается уже с (n – 1) элементами, затем с (n – 2) элементами и т.д., до тех пор, пока не останется один, самый большой элемент.
Этот метод в некотором смысле противоположен методу прямого включения. В методе прямого включения на каждом ша- ге рассматривается только один очередной элемент и все элемен- ты уже "готовой" части последовательности, среди которых оты- скивается точка включения этого очередного элемента. А в мето- де прямого выбора для поиска одного (минимального) элемента просматривают все элементы неотсортированной части, и этот минимальный элемент помещается как очередной элемент в уже "готовую" часть.
Текстовый алгоритм метода:
1. Начало.
2. Выполнить цикл, пока i имеет значения от 1 до N – 1, шаг = 1: а) поместим текущий (i-ый) элемент в какую-нибудь ячейку памяти (Х) и запомним порядковый номер (i) текущего элемента
(в переменной К); б) выполнить цикл, пока j имеет значения от i + 1 (то есть от следующего за i элемента) до N, шаг = +1: тело цикла: если Х > А(j), то помещаем в ячейку Х элемент
А(j) и запоминаем его номер в ячейке К; в) присвоить А(К) = А(i) и А(i) = Х.
3. Конец.
На рис. 3 приведен пример выполнения сортировки методом прямого выбора.

151
Исходн ая последовате
4 4
5 5
1 2
4 2
9 4
1 8
0 6
6 7
I = 1 0
6 5
5 1
2 4
2 9
4 1
8 4
4 6
7
I = 2 0
6 1
2 5
5 4
2 9
4 1
8 4
4 6
7
I = 3 0
6 1
2 1
8 4
2 9
4 5
5 4
4 6
7
I = 4 0
6 1
2 1
8 4
2 9
4 5
5 4
4 6
7
I = 5 0
6 1
2 1
8 4
2 4
4 5
5 9
4 6
7
I = 6 0
6 1
2 1
8 4
2 4
4 5
5 9
4 6
7
I = 7 0
6 1
2 1
8 4
2 4
4 5
5 6
7 9
4
Рис. 3. Пример сортировки методом прямого выбора
На рисунке 4 приведена блок-схема сортировки методом прямого выбора.
Рис. 4. Блок-схема сортировки методом прямого выбора
Сортировка прямым выбором подходит для случая, когда все данные находятся в памяти, а отсортированные данные по- следовательно выводятся.
A(k) = A(i)
A(i) = X
X = A(j)
K = J i= 1, N - 1, 1
X = A(i)
K = i
X ≥ A(j) j = i + 1, N, 1

152