Лекция6(2) Типовые алгоритмы
.pdf
Алгоритм объединения двух массивов с чередованием элементов
Объединить два массива А и В одинакового размера М в один массив с чередованием элементов.
Нечетные элементы С(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
Лекция 6 Информатика, часть 2 |
21 |
Алгоритм нахождения максимального элемента массива
Найти максимальный (минимальный)
элемент массива В размерностью 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
BMAX=B(1) |
K= 1 |
I=1,N |
Нет |
BMAX>B(I |
Да |
BMAX=B(I) |
K= I |
Задание начального значения переменной суммы BMAX=B(1), K=1.
Формула в цикле ВМАХ=B(I), K=I, если ВМАХ>B(I)
Лекция 6 Информатика, часть 2 |
22 |
Алгоритм формирования массива из элементов другого массива, удовлетворяющих условию
Сформировать новый массив В из
элементов массива А размерностью N, удовлетворяющих условию A(I)<T.
Входные данные: N, A(N), T.
Задание начального значения индекса нового массива J=0. Формулы в цикле: J=J+1 и В(J)=A(I), если А(I)<T
Выходные данные: B(J), J – |
|
|
|
||
массив В и количество элементов |
J= 0 |
||||
массива. |
|
|
|
I=1,N |
|
Вспомогательные данные: I |
|
|
|||
|
|
Нет |
|||
Математическая постановка задачи |
|
||||
|
A(I)<T |
||||
J = J + 1, |
N |
åñëè |
A(I ) < |
T |
Да |
B(J ) = å A(I) |
J=J+1 |
||||
|
|
|
|
|
|
|
I = 1 |
|
|
|
B(J)=A(I) |
Например: N=5, Т= 2, Массив А:3, 2, -3, 7,1, |
|
||||
тогда массив В(1)=-3, В(2)=1 |
|
|
|
||
Лекция 6 Информатика, часть 2 |
23 |
Алгоритм удаления элемента из массива
Удаление К элемента из массива |
Параметр цикла I изменяется от |
|
А размерностью М. |
К до М-1. |
|
Удалить К элемент из массива |
Формула в цикле: A(I)=A(I +1). |
|
можно сдвинув весь «Хвост» |
|
|
массива, начиная с К+1 |
|
|
элемента на одну позицию |
I=K, M-1 |
|
влево, выполняя операцию: |
|
|
|
|
|
А(I)=A(I+1), I=K, K+1,…,M |
A(I)=A(I+1) |
|
Входные данные: M, A(M), К. |
|
|
Выходные данные: А(M-1) – |
|
|
массив результата (на один |
|
|
элемент меньше исходного). |
Например: M=5, К=2 |
|
Вспомогательные данные: I |
|
|
Массив А: 3, 6, -3, 7, 1 |
|
|
текущее значение индекса |
|
|
Тогда результат |
|
|
элементов массива. |
|
|
Массив А: 3, -3, 7, 1 |
|
|
|
|
|
Лекция 6 Информатика, часть 2 |
24 |
|
Алгоритм включения нового элемента в массив в указанную позицию
Включение элемента D в К |
Параметр цикла I изменяется от |
|||||||||||
позицию массива А |
||||||||||||
размерностью М. |
М до К с шагом -1. |
|
|
|
|
|||||||
Перед включением элемента |
Формула в цикле: A(I+1)=A(I). |
|
|
|||||||||
Включение в К позицию массива |
||||||||||||
нужно раздвинуть массив, |
||||||||||||
начиная с К позиции, т.е. |
значения переменной D |
|
|
|
|
|||||||
сдвинуть весь «хвост» |
A(K)=D, увеличение размера |
|
|
|||||||||
массива, начиная с К+1 |
массива М=М+1 |
|
|
|
|
|||||||
элемента на одну позицию |
|
|
|
|
|
|
|
|
|
|
|
|
вправо, выполняя операцию: |
|
|
|
|
|
|
|
|
|
|
|
|
А(I+1)=A(I), I=M, M -1,…,K, |
|
|
I=M, K,-1 |
|
|
|
|
|||||
( шаг изменения I= -1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Перемещение элементов нужно |
|
|
|
|
|
|
|
|||||
|
|
A(I+1)=A(I) |
|
|
|
A(K)=D |
||||||
начинать с конца. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Входные данные: M, A(M), К,D. |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
M=M+1 |
|||||
Выходные данные: А(M+1) – |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
массив результата (на один |
|
Например: M=5, К=2, D=8 |
|
|
||||||||
элемент больше исходного). |
|
|
|
|||||||||
Вспомогательные данные: I |
|
Массив А: 3, 2, -3, 7, 1 |
|
|
||||||||
|
Тогда результат |
|
|
|
|
|||||||
|
|
|
|
25 |
|
|||||||
текущее значение индекса Информатика, часть 2 |
|
|
|
|||||||||
элементов массива. |
|
Массив А: 3, 8, 2, -3, 7, 1 |
|
|
||||||||
Алгоритм перестановки двух элементов массива местами
Перестановка К и 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 |
Лекция 6 Информатика, часть 2 |
||
Алгоритм инвертирования (перестановки) элементов массива
• |
Инвертирование массива А |
N=INT(M/2) |
|
размерностью М ( перезапись |
|
|
элементов массива в обратном |
|
|
порядке. |
I=1, N |
Перезапись осуществляется с |
|
|
|
использованием вспомогательной |
P=A(I) |
|
переменной Р, в которую вначале |
A(I)=A(M-I+1) |
|
записывается 1-й элемент массива, |
|
|
|
|
|
затем в 1 элемент записывается М-й, в |
A(M –I+1)=P |
|
M-й из переменной Р переписывается |
|
|
1-й. |
|
•Входные данные: M, A(M).
Выходные данные: А(M) – |
|
|
инвертированный массив. |
Например: M=5, К=2 |
|
Вспомогательные данные: I , Р и |
Массив А: 3, 2, -3, 7, 1 |
|
N=INT(M/2) – средина массива. |
Тогда результат |
|
INT – функция выделения целой части |
Массив А: 1, 7, -3, 2, 3 |
|
числа. |
|
|
|
|
27 |
Лекция 6 Информатика, часть 2 |
||
Алгоритмы со структурой вложенных циклов
•В цикл, называемый внешним, могут входить один или несколько вложенных циклов, называемых внутренними.
•Организация внешнего и внутренних циклов осуществляется по тем же правилам, что и простого цикла.
•Параметры внешнего и внутреннего циклов разные и изменяются не одновременно, то есть при одном значении параметра внешнего цикла параметр внутреннего цикла принимает поочередно все значения.
•Приемы программирования, изложенные ранее, можно использовать и при организации вложенных циклов.
Лекция 6 Информатика, часть 2 |
28 |
Алгоритм сортировки элементов массива
•Упорядочить (отсортировать) элементы массива (В(1), В(2), В(3), В(4), …, В(N), расположив их в порядке возрастания в том же массиве.
•Для решения используется алгоритм, состоящий из двух циклов:
•Внешний цикл – это номер просмотра массива или его части и перестановки найденного во внутреннем цикле минимального элемента массива с первым .
•Во внутреннем цикле первый элемент массива или его части сравнивается со всеми последующими элементами. И находится минимальный элемент.
•Для упорядочения всех элементов массива внешний цикл повторяется К=1,…, N-1 раз. Количество повторений внутреннего цикла на каждом шаге внешнего цикла равно N – К раз. Когда остается в массиве последний элемент сортировка завершена.
Лекция 6 Информатика, часть 2 |
29 |
Алгоритм сортировки элементов массива (вложенные циклы)
•Упорядочение (сортировка) массива В(N) в порядке возрастания значений элементов массива.
Для сортировки по возрастанию нужно во внутреннем цикле находить минимальный элемент массива и переставлять его местом с первым.
Входные данные: N, B(N).
Выходные данные: В(N) – упорядоченный массива.
Вспомогательные данные: I, J, K, BMIN
Например: N=5, Массив B: 3, 2, -3, 7, 1 Упорядоченный массив В: -3, 1, 2, 3, 7
J=1,N-1 |
|
BMIN=B(J) |
|
K= J |
|
I=J+1,N |
|
Нет |
|
BMIN<B(I) |
|
Да |
|
BMIN=B(I) |
B(K)=B(J) |
K= I |
B(J)=BMIN |
Лекция 6 Информатика, часть 2 |
30 |