Similar presentations:
Алгоритмизация и программирование. Типовые алгоритмы решения задач
1. Алгоритмизация и программирование
Типовые алгоритмы решения задачАвтор: Нелинов С.В.
Преподаватель информатики
ГБОУ СОШ №275
Санкт-Петербурга
2. Содержание
1. Алгоритм с итерационным циклом.2. Запоминание результатов.
3. Типовые алгоритмы обработки
одномерных массивов.
4. Типовые алгоритмы обработки
двумерных массивов.
2
3. Задача вычисления значений членов бесконечного ряда с заданной точностью
Вычислить значения членов бесконечного рядаx2
xn
õ, ,..., ,...
2!
n!
с точностью до члена ряда
xn
n!
3
4. Решение осуществляется в итерационном цикле, так как заранее не известно, при каком n выполнится условие.
Для итерационных циклов числоповторений зависит не от параметров
цикла, а от некоторого промежуточного
или окончательного результата.
Сравнивая два соседних члена ряда,
можно заметить, что уn/ yn-1=x/n.
4
5.
Члены рядаn Уx2 x3
xn
õ, , ,...,
2! 3!
n!
Условие
завершения
цикла
Ón
xn
n!
• Для вычисления текущего члена ряда в цикле
используется рекуррентная формула Уn= Уn-1
*x/n.
• Для первого члена ряда У1 = У0*x/1 задается У0
=1.
• Параметр, изменяющийся в этом цикле –
номер члена ряда n.
• Формула для вычисления текущего члена
ряда У=У* х/n.
5
6. Блок-схема алгоритма вычисления членов ряда
1. Ввести значения Х и ε.2. Задать n=1 и начальное
значение У1- первого члена
ряда.
3. НЦ
1. Вычислить следующий член
ряда
Уn=Уn *Х/n
2. Напечатать n и Уn.
3. Вычислить номер следующего
члена ряда n=n+1.
3.4. Если Уn >ε то перейти к НЦ.
3.5. КЦ
4. Конец
Начало
Х ,
Yn=1, n=1
НЦ
Уn= Уn Х/n
n, У n
n=n+1
Да
У n >
КЦ
Ко нец
6
7. Запоминание результатов
В приведённых выше примерах результатывычислений рассматривались как простые
переменные. Поэтому после окончания
вычислений сохранялись лишь последние
их значения.
Новые значения сохраняясь в переменной
затирали её старые значения.
7
8. Запоминание результатов
Если требуется сохранить в памяти (запомнить)все значения результатов, то необходимо:
1. Выделить для хранения результатов
требуемое число ячеек памяти (массив).
2. Вычислять результат как переменную с
индексом.
8
9.
Массив – это упорядоченная последовательностьвеличин, обозначаемая одним именем.
Упорядоченность заключается в том, что элементы
массива располагаются в последовательных ячейках
памяти.
При описании массива в программе указываются его
имя и размер, то есть количество элементов в
массиве.
Например, Х(N), массив с именем Х, содержит N
элементов. Отдельные элементы этого массива
запишутся так: Х(0), Х(1), Х(2),…, Х(N), то есть
элементы имеют такое же имя как массив и
отличаются друг от друга индексом.
9
10.
Номер элемента называется Индексом.Индексы в массиве записываются в скобках.
Индексом может быть константа или
выражение.
Действия над элементами массивов обычно
производятся в циклах, при этом параметром
цикла являются переменные, обозначающие
индексы элементов массивов.
11. Алгоритмы табулирования функций с запоминанием результатов.
Н ач а л оХн,Хк,h,a
n = (Х к - Х н )/h + 1
I= 1
X(I)= Х н
У(I)= а-Х(I)2
НЦ1
I= I+1
Х(I)=Х(I-1)+h
Да
I< = n
КЦ1
НЦ2
I= 1 , n , 1
Х(I), У(I)
КЦ2
Конец
1. Введем хн, хк, h, a
2. Вычислим количество точек n=(Хк-Хн)/h+1 ,
для которых будут вычислены Х и У, n
определяет размерность массивов.
3. Задаем начальное значение параметра
цикла I=1 (I – это номер точки).
4. Задаем X(I)=x н
5. НЦ1
1. Вычислим У(I)=a*X(I)2
2. Вычислим I=I+1
3. Вычислим X(I)=X(I-1)+h
5.4. Если I<=n идти к НЦ
6. КЦ1
7. НЦ2 Параметр цикла I изменяется от 1 до n
с шагом 1.
7.1 Печать массивов Х(I), Y(I)
8. КЦ2
9. Конец.
12. Алгоритмы табулирования функций с использованием блока модификации
1. Введем хн, хк, h, a2. Вычислим количество точек n=(Хк-Хн)/h+1,
для которых будут вычислены Х и У, n определяет размерность массивов.
3. Задаем начальное значение X(1)=xn
4. Задаем начальное значение параметра
цикла I=1 (I – это номер точки).
5. Задаем X(I)=xн
6. НЦ1 Параметр цикла I изменяется от 1 до n
с шагом 1.
1. Вычислим У(I)=a*X(I)2
2. Вычислим X(I)=X(I-1)+h
7. КЦ1
8. НЦ2 Параметр цикла I изменяется от 1 до n
с шагом 1.
8.1 Печать массивов Х(I), Y(I)
9. КЦ2
10. Конец.
сть 2
Н ачало
Хн,Хк,h,a
n=(Хк-Х н)/h+1
X(1)= Хн
I=1,n,1
НЦ1
У(I)= а-Х(I) 2
Х(I)=Х(I-1)+h
КЦ1
I=1,n,1
Х(I), У(I)
КЦ2
НЦ2
Конец
12
13. Типовые алгоритмы обработки одномерных массивов
1314.
Обычно в программировании используютсяодномерные и двумерные массивы.
Одномерные массивы – это столбец или строка
каких-либо величин обозначенных одним
именем и индексом, указанным в скобках.
В математике аналогом одномерного массива
является вектор-строка или вектор –столбец.
15. Алгоритмы ввода и вывода элементов одномерных массивов
Ввод элементов одномерногомссива X(N), I=1,2,…,N.
Шаг изменения I равен 1.
При N=5 элементы массива
Х(1), Х(2), Х(3), X(4), X(5).
N
НЦ
I=1,N,1
Х (I)
КЦ
Вывод элементов одномерного
массива У(N), I=1,…,N
Шаг изменения I равен 1.
При N= 5 элементы массива
Y(1), Y(2), Y(3), Y(4), Y(5).
НЦ
I=1,N
Y(I)
КЦ
15
16. Алгоритм вычисления суммы элементов массива и среднего значения
Вычислить среднее значениеэлементов массива А(М).
Входные данные: M, A(M).
Выходные данные: S – сумма
элементов массива, SR – среднее
значение.
Вспомогательные данные: I
Математическая постановка задачи
M
S A(I )
I 1
SR
S
M
S=0
НЦ
I=1,M,1
S=S+A(I)
SR=S/M
КЦ
1.Задание начального значения
переменной суммы S=0.
2.НЦ Параметр цикла I изменяется
от 1 до М с шагом 1.
2.1.
Вычисление суммы S=S+А(I).
3. КЦ
4. Вычисление среднего SR=S/M.
Например: M=5, А(1)=3, А(2)=2, А(3)=-3, А(4)=7, А(5)=1 , тогда S=10, SR=2 16
17. Алгоритм вычисления произведения элементов массива
Вычислить произведениеэлементов массива А(М).
Входные данные: M, A(M).
Выходные данные:
Р – произведение элементов
массива.
Вспомогательные данные: I
Математическая постановка
задачи
M
P A(I )
I 1
P=1
НЦ
I=1,M,1
P=P*A(I)
КЦ
1. Задание начального значения
переменной произведения Р=1.
2. НЦ Параметр цикла I
изменяется от 1 до М с шагом 1.
1. вычислим произведение Р=Р*А(I)
3. КЦ
Например: M=5, А(1)=3, А(2)=2, А(3)=-3, А(4)=7, А(5)=1 , тогда P=-126
18. Алгоритм объединения двух массивов c суммированием их элементов
Объединить два массива А и Водинакового размера с
суммированием элементов,
имеющих одинаковые индексы
С(I)=A(I) +B(I)
Входные данные: M, A(M), B(M).
Выходные данные: C(M) –
массив результатов.
Вспомогательные данные: I
текущее значение индекса
элементов массива.
Например: M=5,
Массив А: 3, 2, -3, 7, 1
Массив B: 4, 3, 1,-5, 5
Тогда
Массив С: 7, 5,-2, 2,6
НЦ
I=1,M,1
C(I)=A(I)+B(I)
КЦ
18
19. Алгоритм подсчета количества элементов массива, удовлетворяющих заданному условию
Подсчитать количествоэлементов массива А
размерностью М,
удовлетворяющих условию
A(I)>T.
Входные данные: M, A(M), T.
Выходные данные: K –
количество элементов массива,
удовлетворяющих условию.
Вспомогательные данные: I
Математическая постановка
задачи
K
M
1
åñëè
A(I ) T
K=0
НЦ
I=1,M,1
Нет
A(I)>T
Да
K=K+1
КЦ
1. Задание K=0.
2. НЦ Параметр цикла I
изменяется от 1 до М с шагом 1.
2.1 Если А(I)>T то
2.2. К=К+1
3. КЦ
I 1
Например: M=5, Т= 2, А(1)=3, А(2)=2, А(3)=-3, А(4)=7, А(5)=1 , тогда К=2
20. Алгоритм суммирования элементов массива, удовлетворяющих заданному условию
Просуммировать элементы массиваВ размерностью N,
удовлетворяющих условию B(I)>Z.
Входные данные: N, B(N), Z.
Выходные данные: S – Сумма
элементов массива,
удовлетворяющих условию.
Вспомогательные данные: I
Математическая постановка задачи
M
S
B(I )
I 1
åñëè
B ( I ) Z
S=0
I=1,N,1
Нет
B(I)>Z
Да
S=S+B(I)
Задание начального значения
переменной суммы S=0.
Формула в цикле(сумма)
S=S+B(I)
Например: N=5, Z= 2, В(1)=4, В(2)=3, В(3)=1, В(4)=-5, В(5)=5 , тогда S=13
0
21. Алгоритм объединения двух массивов с чередованием элементов
Объединить два массива А и Водинакового размера М в один
массив с чередованием
элементов.
Нечетные элементы С(2*I-1)=A(I)
Четные элементы С(2*I)=B(I)
Входные данные: M, A(M), B(M).
Выходные данные: C(2*M) –
массив результатов.
Вспомогательные данные: I
текущее значение индекса
элементов массива.
I=1,M,1
C(2*I-1)=A(I)
C(2*I)=B(I)
Например: M=5, Массив А: 3, 2, -3, 7, 1
Массив B: 4, 3, 1,-5, 5
Тогда массив С
С(1)=А(1)=3, С(6)=В(3)=1
С(2)=В(1)=4, С(7)=А(4)=7
С(3)=А(2)=2, С(8)=В(4)=-5
С(4)=В(2)=3, С(9)=А(5)=1
С(5)=А(3)=-3, С(10)=В(5)=5
21
22. Алгоритм нахождения максимального элемента массива
BMA=B(1 )Найти максимальный (минимальный)
элемент массива В размерностью
N, с запоминанием его положения
(индекса) в массиве.
Входные данные: N, B(N).
Выходные данные: BMAX –
максимальный элемент массива, К
–номер индекса максимального
элемента.
Вспомогательные данные: I
АНАЛОГИЧНО осуществляется поиск
минимального элемента в массиве.
Например: N=5, B(1)=3, B(2)=2, B(3)=-3,
B(4)=7, B(5)=1 , тогда BMAX=7, K=4
K= 1
I=1,N
Н ет
BMAX>B(I
Да
B M A X = B(I)
K= I
Задание начального значения
переменной суммы
BMAX=B(1), K=1.
Формула в цикле ВМАХ=B(I),
K=I, если ВМАХ>B(I)
22
23. Алгоритм формирования массива из элементов другого массива, удовлетворяющих условию
Сформировать новый массив В изэлементов массива А
размерностью N,
удовлетворяющих условию A(I)<T.
Входные данные: N, A(N), T.
Выходные данные: B(J), J –
массив В и количество элементов
массива.
Вспомогательные данные: I
Математическая постановка задачи
J J 1,
B(J ) A(I )
N
Задание начального значения
индекса нового массива J=0.
Формулы в цикле: J=J+1 и
В(J)=A(I), если А(I)<T
J= 0
I=1,N
Н ет
A (I)<T
Да
åñëè
A(I ) T
I 1
J=J+1
B (J)=A (I)
Например: N=5, Т= 2, Массив А:3, 2, -3, 7,1,
тогда массив В(1)=-3, В(2)=1
23
24. Алгоритм удаления элемента из массива
Удаление К элемента измассива А размерностью М.
Удалить К элемент из
массива можно сдвинув
весь «Хвост» массива,
начиная с К+1 элемента на
одну позицию влево,
выполняя операцию:
А(I)=A(I+1), I=K, K+1,…,M
Входные данные: M, A(M), К.
Выходные данные: А(M-1) –
массив результата (на один
элемент меньше исходного).
Вспомогательные данные:
I текущее значение
индекса элементов
массива.
Параметр цикла I изменяется от
К до М-1.
Формула в цикле: A(I)=A(I +1).
I=K, M-1
A(I)=A(I+1)
Например: M=5, К=2
Массив А: 3, 6, -3, 7, 1
Тогда результат
Массив А: 3, -3, 7, 1
24
25. Алгоритм включения нового элемента в массив в указанную позицию
Включение элемента D в Кпозицию массива А
размерностью М.
Перед включением элемента
нужно раздвинуть массив,
начиная с К позиции, т.е.
сдвинуть весь «хвост»
массива, начиная с К+1
элемента на одну позицию
вправо, выполняя операцию:
А(I+1)=A(I), I=M, M -1,…,K,
( шаг изменения I= -1)
Перемещение элементов нужно
начинать с конца.
Входные данные: M, A(M), К,D.
Выходные данные: А(M+1) –
массив результата (на один
элемент больше исходного).
Вспомогательные данные: I
текущее значение индекса
Лекция 6 Инфо
элементов массива.
Параметр цикла I изменяется от
М до К с шагом -1.
Формула в цикле: A(I+1)=A(I).
Включение в К позицию массива
значения переменной D
A(K)=D, увеличение размера
массива М=М+1
I=M, K,-1
A(I+1)=A(I)
A(K)=D
M=M+1
Например: M=5, К=2, D=8
Массив А: 3, 2, -3, 7, 1
Тогда результат
25
26. Алгоритм перестановки двух элементов массива местами
Перестановка К и L элементовмассива А размерностью М
местами.
Перезапись осуществляется с
использованием
вспомогательной переменной Р,
в которую временно помещается
один из элементов массива.
Например, в Р записывается К-й
элемент массива, затем в К-й
элемент записывается L-й, в L-й
из переменной Р
переписывается K-й.
Входные данные: M, A(M), K, L.
Выходные данные: А(M) –массив
c переставленными элементами.
Вспомогательные данные: I , Р
P = A (K )
A(K )=A (L)
A(L)=P
Например: M=5, К=2, L=4
Массив А: 3, 2, -3, 7, 1
Тогда результат
Массив А: 3, 7, -3, 2, 1
26
27. Алгоритм инвертирования (перестановки) элементов массива
• Инвертирование массива Аразмерностью М ( перезапись
элементов массива в обратном
порядке.
Перезапись осуществляется с
использованием вспомогательной
переменной Р, в которую вначале
записывается 1-й элемент массива,
затем в 1 элемент записывается М-й, в
M-й из переменной Р переписывается
1-й.
• Входные данные: M, A(M).
Выходные данные: А(M) –
инвертированный массив.
Вспомогательные данные: I , Р и
N=INT(M/2) – средина массива.
INT – функция выделения целой части
числа.
N=INT(M/2)
I=1, N
P=A(I)
A(I)=A(M-I+1)
A(M –I+1)=P
Например: M=5, К=2
Массив А: 3, 2, -3, 7, 1
Тогда результат
Массив А: 1, 7, -3, 2, 3
27
28. Алгоритмы со структурой вложенных циклов
• В цикл, называемый внешним, могут входить один илинесколько вложенных циклов, называемых
внутренними.
• Организация внешнего и внутренних циклов
осуществляется по тем же правилам, что и простого
цикла.
• Параметры внешнего и внутреннего циклов разные и
изменяются не одновременно, то есть при одном
значении параметра внешнего цикла параметр
внутреннего цикла принимает поочередно все
значения.
• Приемы программирования, изложенные ранее, можно
использовать и при организации вложенных циклов.
28
29. Алгоритм сортировки элементов массива
• Упорядочить (отсортировать) элементы массива (В(1), В(2),В(3), В(4), …, В(N), расположив их в порядке возрастания в
том же массиве.
• Для решения используется алгоритм, состоящий из двух
циклов:
• Внешний цикл – это номер просмотра массива или его части
и перестановки найденного во внутреннем цикле
минимального элемента массива с первым .
• Во внутреннем цикле первый элемент массива или его части
сравнивается со всеми последующими элементами. И
находится минимальный элемент.
• Для упорядочения всех элементов массива внешний цикл
повторяется К=1,…, N-1 раз. Количество повторений
внутреннего цикла на каждом шаге внешнего цикла равно N –
К раз. Когда остается в массиве последний элемент
сортировка завершена.
29
30. Алгоритм сортировки элементов массива (вложенные циклы)
Упорядочение (сортировка) массиваВ(N) в порядке возрастания
значений элементов массива.
Для сортировки по возрастанию нужно
во внутреннем цикле находить
минимальный элемент массива и
переставлять его местом с первым.
Входные данные: N, B(N).
Выходные данные: В(N) –
упорядоченный массива.
Вспомогательные данные: I, J, K,
BMIN
J=1,N-1
BMIN=B(J)
K= J
I=J+1,N
Нет
BMIN<B(I)
Да
B(K)=B(J)
BMIN=B(I)
K= I
B(J)=BMIN
Например: N=5, Массив B: 3, 2, -3, 7, 1
Упорядоченный массив В: -3, 1, 2, 3, 7
30
31. Типовые алгоритмы обработки двумерных массивов
32. Двумерные массивы
• Двумерный массив – это таблица, содержащаяинформацию и состоящая из нескольких строк и
столбцов. В математике аналогом является матрица.
• Каждый элемент двумерного массива имеет тоже имя,
что и весь массив и отличается от другого элемента
номером строки и номером столбца, на пересечении
которых он находится.
• Номер строки и номер столбца называются
индексами.
• Индексы в двумерном массиве записываются в скобках
через запятую. На первом месте стоит индекс строки,
на втором месте – индекс столбца.
• Например, В(I,J) –элемент двумерного массива с
именем В, стоящий на пересечении I строки и J
столбца.
32
33. Ввод и вывод элементов двумерных массивов
Ввод элементов двумерного мссива X(N,M),I=1,2,…,N, J=1,2,…,M
Шаг изменения I и J равен 1.
Пусть N=2, M=3.
При I=1, изменения J=1,2,…,3
вводятся элементы массива
Х(1,1), Х(1,2), Х(1,3)
При I=2, изменения J=1,2,…,3
вводятся элементы массива
X(2,1), X(2,2), X(2,3)
АНАЛОГИЧНО
Вывод элементов двумерного массива
У(N,M), I=1,…,N, J=1,2,…,M
Шаг изменения I и J равен 1.
При N= 3 и M=2 элементы массива
Y(1,1), Y(1,2), Y(2,1), Y(2,2), Y(3,1),У(3,2)
N ,M
I=1,N,1
J = 1 ,M , 1
Х(I,J)
I=1,N
I=1,N
Y(I,J)
33
34. Алгоритм вычисления среднего значения элементов массива по строкам
Вычислить средние значения элементовмассива А(N,М) по строкам.
Входные данные: N,M, A(N,M).
Выходные данные: S(N) – сумма
элементов массива по строкам, SR(N) –
средние значения по строкам.
Вспомогательные данные: I,J
Математическая постановка задачи
M
S(I ) A(I , J )
j 1
А(1,1)
А(2,1)
А(3,1)
А(4,1)
А(1,2)
А(2,2)
А(3,2)
А(4,2)
А(1,3)
A(2,3)
А(3,3)
A(4,3)
S(I )
SR(I)
M
S(1)
S(2)
S(3)
S(4)
SR(1)
SR(2)
SR(3)
SR(4)
Задание начального
значения суммы S(I)=0.
Формула в цикле(сумма)
S(I)=S(I)+А(I,J).
Среднее SR(I)=S(I)/M
I=1,N,1
S(I)=0
J=1,M,1
S(I)=S(I)+A(I,J)
SR(I)=S(I)/M
34
35. Алгоритм вычисления среднего значения элементов массива по столбцам
Вычислить средние значения элементовмассива А(N,М) по столбцам.
Входные данные: N,M, A(N,M).
Выходные данные: S(M) – сумма
элементов массива по строкам, SR(M) –
средние значения по строкам.
Вспомогательные данные: I,J
Математическая постановка задачи
N
S (J ) A(I , J )
i 1
А(1,1) А(1,2)
А(2,1) А(2,2)
А(3,1) А(3,2)
А(4,1) А(4,2)
S(1)
S(2)
SR(1) SR(2)
А(1,3)
A(2,3)
А(3,3)
A(4,3)
S(3)
SR(3)
SR(J )
S (J )
N
Задание начального
значения суммы S(J)=0.
Формула в цикле(сумма)
S(J)=S(J)+А(I,J).
Среднее SR(J)=S(J)/M
J=1,M,1
S(J)=0
I=1,N,1
S(J)=S(J)+A(I,J)
SR(J)=S(J)/N
35
36. Алгоритм транспонирования матрицы
Транспонирование матрицы . Заменастрок матрицы А(N,М) её столбцами, а
столбцов – строками.
Транспонированная матрица
В(M,N) = A(N,M)
Входные данные: N,M, A(N,M).
Выходные данные: B(M,N) –
Вспомогательные данные: I,J
Математическая постановка задачи
Формула в цикле
B(J,I)=А(I,J)
J=1,M,1
I=1,N,1
B(J,I)=A(I,J)
B(J,I) A(I, J)
А(1,1) А(1,2) А(1,3)
А(2,1) А(2,2) A(2,3)
B(1,1) B(1,2)
B(2,1) B(2,2)
B(3,1) B(3,2)
36
37. Алгоритм произведения матрицы А(N,M) на вектор B(M)
Входные данные: N,M, A(N,M),B(M)
Выходные данные: C(N) – вектор
результата.
Вспомогательные данные: I,J
Математическая постановка
задачи
M
C(I) A(I, J)*B(J)
Задание начального
значения переменной
C(I)=0.
Формула во внутреннем
цикле С(I)=C(I)+А(I,J)*B(J).
I=1,N,1
j 1
А(1,1) А(1,2) А(1,3)
А(2,1) А(2,2) A(2,3)
А(3,1) А(3,2) А(3,3)
С(1)
C(2)
C(3)
C(I)=0
J=1,M,1
C(I)=C(I)+A(I,J)*B(J)
B(1)
B(2)
B(3)
37
38. Алгоритм преобразования матрицы в одномерный массив
Преобразовать массив А(N,М) в векторХ(N*M).
Входные данные: N,M, A(N,M).
Выходные данные: X(N*M) – вектор, в
который последовательно
переписаны строки массива А.
Вспомогательные данные: I,J
Математическая постановка задачи
L (I 1) * M J
X (L) A(I , J )
А(1,1) А(1,2) А(1,3)
А(2,1) А(2,2) A(2,3)
N=2, M=3
N*M=6
X(1) X(2) X(3) X(4) X(5) X(6)
I=2, J=1, M=3
L=(I-1)*M+J=(2-1)*3+1=4
X(4)=A(2,1)
Формулы в цикле:
Вычисление значения
индекса массива Х
L=(I-1)*M+J
Запись элемента X(L)=A(I,J)
I=1,N,1
J=1,M,1
L=(I-1)*M+J
X(L)=A(I,J)
38
39. Алгоритм нахождения максимального элемента в строках двумерного массива
Найти максимальные элементыв строках массива В (N, M) с
запоминанием
максимального элемента и
его индекса.
Входные данные: N, M, B(N,M).
Выходные данные: MAX(N) –
массив максимальныx
элементов, IMAX (N) –массив
индексов максимальных
элементов.
Вспомогательные данные:
I,J Постановка задачи
В(I,1)
10
1
2
B(I,2)
20
10
30
B(I,3) IMAX(I) MAX(I)
10
2
20
20
1
25
25
2
30
Задание начальных значений
MAX(I)=B(I,1), IMAX(I)=1.
Формулы в цикле
МАХ(I)=B(I,J) и IMAX(I)=J ,
если МАХ(I)>B(I,J)
I= 1,N
MAX(I)=B(I,1)
IMA X ( I) = 1
J=1,M
Н ет
MAX(I)>B(I,J )
Да
MAX(I)=B(I,J )
IM A X (I)
M A X ( I)
IMA X ( I) = J
39
40. Алгоритм удаления строки из матрицы
Удаление К строки из матрицыА(N,М).
Все строки, начиная с К+1
переместить вверх. Число строк
уменьшится на 1.
Входные данные: N,M, К, A(N,M).
Выходные данные: А(N-1,M)
Вспомогательные данные: I,J
Математическая постановка задачи
A(I , J ) A(I 1, J )
100 100 100
1
200 200
300 300 300
1
400 400
100 100 100
K=3
1
2
3
100
100
200
400
100
100
200
400
100
Формула в цикле
A(I,J)=А(I+1,J)
N=N-1
I=K,N,1
J=1,M,1
A(I,J)=A(I+1,J)
40
41. Алгоритм включения строки в матрицу
Включить строку Х(M) в матрицу А(N,М) как Ктую строку.
Входные данные: N, M, К, A(N,M), X(M).
Выходные данные: A(N+1,M) – массив, в
котором строки с 1 по К -1 остались
прежними, К строка переписана из массива
Х(М), а строки , начиная с К+1 вновь из
массива А.
Вспомогательные данные: I,J
Постановка задачи
Вставили в К-ую
строку массив X
1
100 100 K=3
200 200 200 500 500 500
1
300 300
1
100 100
400 400 400
Переписали
«Хвост»
массива на
одну строку в
конец
Формулы в цикле:
Сдвиг строк «хвоста» массива на
1: А(I+1,J)= A(I,J)
Запись элементов X в строку
A(K,J)=X(J)
I=N,K,-1
J=1,M,1
A(I+1,J)=A(I,J)
200 200 200
1
100 100
1
300 300
300 300 300
400 400 400
200 200 200
J=1,M,1
500 500 500
300 300 300
A(K,J) =X(J)
N=N+1
41
42. Алгоритм перестановки строк в матрице
Перестановка L и K строк в матрице А(N,M)осуществляется с использованием
вспомогательной переменной Р:
В Р записывается J-й элемент L строки,
в J элемент L строки записывается J элемент K
строки,
в J-й элемент K строки записывается элемент из
переменной Р .
L=2, K=4
J=1, M
P=A(L,J)
A(L,J)=A(K,J)
A(K,J)=P
Входные данные: N, M, A(N,M).
Выходные данные: А(N,M) – c
переставленными строками.
Вспомогательные данные: I , J, Р, К.
РЕЗУЛЬТАТ
1
40
1
20
50
10
40
30
20
50
10
40
30
20
50
10
40
30
20
50
L=2,K=4
P
1
2
3
4
50
10
20
30
40
50
10
20
30
40
50
10
20
30
40
50
42
43. Алгоритм умножения двух матриц
(количество столбцов первой матрицы должно совпадать сколичеством строк второй матрицы)
Умножить матрицы А(N,K) и B(K,M)
Входные данные: N,M, К, A(N,K), B(K,M)
Выходные данные: C(N,M) – матрица
результата.
Вспомогательные данные: I,J
Математическая постановка задачи
I=1,N,1
J=1,M,1
C(I,J)=0
L=1,K,1
K
C(I, J) A(I, L)*B(L, J)
C(I,J)=C(I,J)+A(I,L)*B(L,J)
l 1
N=3
А(1,1)
А(2,1)
А(3,1)
K=2
А(1,2)
А(2,2)
А(3,2)
K=2
M=4
B(1,1) B(1,2) B(1,3) B(1,4)
B(2,1) B(2,2) B(2,3) B(2,4)
N=3
M=4
C(1,1) C(1,2) C(1,3) C(1,4)
C(2,1) C(2,2) C(2,3) C(2,4)
C(3,1) C(3,2) C(3,3) C(3,4)
C(1,1)=A(1,1)*B(1,1)+ A(1,2)*B(2,1)
C(1,2)=A(1,1)*B(1,2)+ A(1,2)*B(2,2)
C(1,3)=A(1,1)*B(1,3)+ A(1,2)*B(2,3)
C(1,4)=A(1,1)*B(1,4)+ A(1,2)*B(2,4)