Алгоритмизация и программирование
Содержание
Задача вычисления значений членов бесконечного ряда с заданной точностью
Решение осуществляется в итерационном цикле, так как заранее не известно, при каком n выполнится условие.
Блок-схема алгоритма вычисления членов ряда
Запоминание результатов
Запоминание результатов
Алгоритмы табулирования функций с запоминанием результатов.
Алгоритмы табулирования функций с использованием блока модификации
Типовые алгоритмы обработки одномерных массивов
Алгоритмы ввода и вывода элементов одномерных массивов
Алгоритм вычисления суммы элементов массива и среднего значения
Алгоритм вычисления произведения элементов массива
Алгоритм объединения двух массивов c суммированием их элементов
Алгоритм подсчета количества элементов массива, удовлетворяющих заданному условию
Алгоритм суммирования элементов массива, удовлетворяющих заданному условию
Алгоритм объединения двух массивов с чередованием элементов
Алгоритм нахождения максимального элемента массива
Алгоритм формирования массива из элементов другого массива, удовлетворяющих условию
Алгоритм удаления элемента из массива
Алгоритм включения нового элемента в массив в указанную позицию
Алгоритм перестановки двух элементов массива местами
Алгоритм инвертирования (перестановки) элементов массива
Алгоритмы со структурой вложенных циклов
Алгоритм сортировки элементов массива
Алгоритм сортировки элементов массива (вложенные циклы)
Типовые алгоритмы обработки двумерных массивов
Двумерные массивы
Ввод и вывод элементов двумерных массивов
Алгоритм вычисления среднего значения элементов массива по строкам
Алгоритм вычисления среднего значения элементов массива по столбцам
Алгоритм транспонирования матрицы
Алгоритм произведения матрицы А(N,M) на вектор B(M)
Алгоритм преобразования матрицы в одномерный массив
Алгоритм нахождения максимального элемента в строках двумерного массива
Алгоритм удаления строки из матрицы
Алгоритм включения строки в матрицу
Алгоритм перестановки строк в матрице
Алгоритм умножения двух матриц
620.57K
Categories: programmingprogramming informaticsinformatics

Алгоритмизация и программирование. Типовые алгоритмы решения задач

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, a
2. Вычислим количество точек 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. Типовые алгоритмы обработки одномерных массивов

13

14.

Обычно в программировании используются
одномерные и двумерные массивы.
Одномерные массивы – это столбец или строка
каких-либо величин обозначенных одним
именем и индексом, указанным в скобках.
В математике аналогом одномерного массива
является вектор-строка или вектор –столбец.

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)
English     Русский Rules