9.1.5. Алгоритмы циклической структуры

Циклом называется повторение одних и тех же действий. Последовательность действий, которые повторяются в цикле, называют телом цикла. Существует несколько типов алгоритмов циклической структуры (рис.9.7; рис.9.8; рис.9.9, рис.9.10):

- алгоритм с предусловием (условие проверяется до тела цикла, проверяется условие продолжение цикла), рис.9.7;

- алгоритм с постусловием (условие проверяется после цикла, проверяется условие выхода из цикла), рис.9.8;

- алгоритм циклической структуры без условия(известно сколько раз необходимо повторить цикл), рис. 9.9;

- условный циклический алгоритм с известным числом повторений, рис. 9.10.

тело цикла

i=in

i=in, ik, di

усл-е

i<=ik

усл-е

тело цикла

тело цикла

Тело цикла

i=in+di

Рис.9.7 Рис.9.8 Рис. 9.9 Рис. 9.10

Выполнение безусловного циклического алгоритма начинается с присвоения переменной I стартового значения in. Затем следует проверка, не превосходит ли переменная I конечное значение ik. Если превосходит, то цикл считается завершенным и управление передается следующему за телом цикла оператору. В противном случае выполняется тело цикла и переменная i меняет свое значение в соответствии с шагом di. Безусловный цикл можно заменить любым условным.

Пример 5.5.

Дано: Два натуральных числа А и В.

Найти: наибольший общий делитель этих чисел.

Для решения используем алгоритм Евклида. Большее из чисел уменьшаем на величину меньшего до тех пор, пока оба значения не станут равными (см. таблицу 9.3.).

Таблица 9.3.

Исходные данные	Первый шаг	Второй шаг	Третий шаг	НОД (А.В)=5
А=25	А=10	А=10	А=5
В=15	В=15	В=5	В=5

В блок схеме алгоритма используется цикл с предусловием, то есть тело цикла повторяется до тех пор, пока А не равно В (рис.9.11.).

Отладка циклических алгоритмов

Отладка циклических алгоритмов не имеет особенностей и проводится согласно ранее описанным алгоритмам.

пуск

А, В

А<>В

А

А>В

останов

А=А-В

В=В-А

Рис. 9.11. Поиск наибольшего общего делителя двух чисел

Отладка циклических алгоритмов

Отладка циклических алгоритмов не имеет особенностей и проводится согласно ранее описанным алгоритмам.

9.1.6. Алгоритмы обработки одномерных массивов

Массив – это структурированный тип данных, состоящий из фиксированного числа элементов одного типа. Массивы часто используются во множествах. Массивы бывают одномерные и многомерные.

Пример одномерного массива (таблица 9.4.).

Таблица 9.4.

15,7	0.45	-1,7	0	35,3	21,7	45,3	5,0	141,4	16,9
1 – й элемент массива	2 – й элемент массива	3 – й элемент массива	4 – й элемент массива	5 – й элемент массива	6– й элемент массива	7 – й элемент массива	8 – й элемент массива	9 – й элемент массива	10 – й элемент массива

Пример многомерного числового массива (двухмерного, таблица 9.5.)

Таблица 9.5.

		Номера столбцов
Номера строк		1	2	3	4
	1	10	15	35	-34
	2	0	-45	-57	59
	3	67	35	56	78
	4	90	-78	60	45

Ввод-вывод элементов одномерного массива

При вводе одномерного массива необходимо последовательно вводить 1-й, 2-й и т.д. элементы массива, аналогично поступают при выводе. Для ввода или вывода массива необходимо организовать цикл. Наиболее удобно использовать для ввода и вывода одномерного массива алгоритм с использованием безусловного цикла (рис.9.12.).

I=1,N

Ввод

Рис.9.12. Алгоритм ввода массива с использованием безусловного цикла

Вычисление суммы элементов массива

Пусть дан массив X, состоящий из n элементов. Нужно найти сумму элементов данного массива. Переменной S присваивается значение равное нулю, затем последовательно суммируются элементы массива X (рис.9.13.).

S=0

I=1,N

S=S+Xi

Рис.9.13. Алгоритм вычисления суммы элементов массива

Вычисление произведения элементов массива

Дан массив Х, состоящий из n элементов. Необходимо найти произведение элементов данного массива. Решение этой задачи сводится к тому, что значение переменной Р, в которую предварительно была записана единица, последовательно умножается на значение I – го элемента массива (рис.9.14.).

Р=1

I=1,N

Р=S*Xi

Рис. 9.14. Вычисление произведения элементов массива

Поиск максимального элемента в массиве и его номера

Пусть дан массив Х, состоящий из n элементов. Необходимо найти максимальный элемент массива и его номер, под которым он хранится в массиве (рис.9.15.).

Пусть в переменной с именем Мах хранится значение максимального элемента массива, а в переменной с именем Nmax – его номер. Предположим, что первый элемент массива является максимальным и запишем его в переменную Мах, а в Nmax занесем его номер, т.е. – 1. Затем все элементы, начиная со второго, сравниваем в цикле с максимальным. Если текущий элемент массива оказывается больше максимального, то записываем его в переменную Мах, а в переменную Nmax – текущее значение индекса i

Мах=Х1

Nmax=1

i=2,N

Мах<

Мах=Xi Nmax=i

Вывод

Мах, max

Рис. 9.15. Поиск максимального элемента и его номера в массиве

Таблица. 9.6. Определение максимального элемента и его номера в массиве

Номера элементов	1	2	3	4	5	6	7
Исходный массив	4	7	3	8	9	2	5
Значение переменной Мах	4	7	7	8	9	9	9
Значение переменнойNmax	1	2	2	4	5	5	5

Поиск минимального элемента в массиве и его номера

Пусть дан массив Х, состоящий из n элементов. Необходимо найти минимальный элемент массива и его номер, под которым он хранится в массиве (рис.5.16.).

Пусть в переменной с именем Мин хранится значение минимального элемента массива, а в переменной с именем Nmin – его номер. Предположим, что первый элемент массива является минимальным и запишем его в переменную Мин, а в Nmin занесем его номер, т.е. – 1. Затем все элементы, начиная со второго, сравниваем в цикле с минимальным. Если текущий элемент массива оказывается меньше минимального, то записываем его в переменную Мин, а в переменную Nmin – текущее значение индекса.

Мин=Х1

Nmin=1

i=2,N

нет

Мин<

да

Вывод

Мин, Nmin

Мин=Xi

Nmin=i

Рис. 9.16. Поиск минимального элемента и его номера в массиве

Таблица. 9.7. Определение минимального элемента и его номера в массиве

Номера элементов	1	2	3	4	5	6	7
Исходный массив	4	7	3	8	9	2	5
Значение переменной Мин	4	4	3	3	3	2	2
Значение переменной Nmin	1	1	3	3	3	6	6

Сортировка элементов в массиве

Сортировка представляет собой процесс упорядочения элементов в массиве в порядке возрастания или убывания их значений. Существует большое количество алгоритмов сортировки, но все они базируются на трех основных:

- сортировка методом «пузырька»;

- сортировка обменом;

- сортировка выбором;

- сортировка вставкой.

Сортировка методом «пузырька».

Задан массив Y из n целых чисел. Необходимо разложить их в порядке возрастания. Сравним первый элемент массива со вторым, если первый окажется больше второго, то поменяем их местами. Аналогично поступим для второго, третьего, i-го, (i+1), (n-1), n-го элементов. В результате этих действий самый большой элемент станет на последнем месте. Повторяем данный алгоритм сначала, но без рассмотрения последнего элемента n, так как он уже стал на свое место. Так повторяем до тех пор, пока не упорядочится весь массив.

В таблице 9.8 подробно расписан процесс упорядочения элементов в массиве. Для преобразования массива из n элементов, необходимо просмотреть его n-1 раз, каждый раз уменьшая диапазон просмотра на один элемент.

Таблица. 9.8. Процесс упорядочения элементов в массиве по возрастанию

Номер элемента	1	2	3	4	5
Исходный массив	7	3	5	4	2
Первый просмотр	3	5	4	2	7
Второй просмотр	3	4	2	5	7
Третий просмотр	3	2	5	4	7
Четвертый просмотр	2	3	4	5	7

Для перестановки элементов в массиве по убыванию их значений необходимо при сравнении элементов массива заменить знак больше на меньше.

J=1, n-1

i=1, n-j

нет

Yj>Yj+1

да

b=Yj+1

Yj+1=Yj

Yj=b

Рис. 9.17. Сортировка массива пузырьковым методом

Сортировка выбором (рис.9.18.).

Найдем в массиве самый большой элемент (блоки 3-7) и поменяем его местами с последним блоком (блок 8). Повторим алгоритм поиска максимального элемента, уменьшив количество просматриваемых элементов на единицу (блок 9) и поменяем его местами с предпоследним элементом (блок 3-7). Описанную выше операцию поиска проводим до полного упорядочения элементов в массиве. Так как в блоке 9 происходит изменение переменой n, то в начале алгоритма ее значение необходимо сохранить (блок 1).

1 k=n

2 j=1,k

9 n=n-1

3 Мах=Y1

4 Nom=1

8 b=Ynom

Ynom =Yn

Yn =b

5 i=2,n

нет

6 Yj>max

да

7 b=Yj+1

Yj+1=Yj

Yj=b

Рис.9.18. Сортировка массива выбором наибольшего элемента

Сортировка вставкой

Сортировка вставкой (рис.9.19; рис.9.20.) заключается в том, что сначала упорядочивается два элемента массива. Затем делается вставка третьего элемента в соответствующее место по отношению к первым двум элементам. Четвертый элемент помещают в список из уже упорядоченных трех элементов. Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены.

Пример. Имеется массив из восьми элементов. Нужно седьмой элемент вставить между вторым и четвертым

Y1

Y2

Y3

Y4

Y5

Y6

Y7

Y8

x

Рис. 9.20. Процесс вставки элемента в массив

Сохраним седьмой элемент во вспомогательной переменной Х, а на его место переместим шестой элемент, на место шестого поместим пятый, на место пятого помести четвертый, на место четвертого помести третий. На место третьего поместим их переменой Х седьмой элемент.

пуск

1 пуск

4 i=2,n

2 n

10 Yj+1=X

5 X=Yi

6 j=i+1

3 i=1,n

нет

7 i=2, n

4 Yj

да

8 Yj+1=Yj

11 i=1,n

9 j=j-1

12 Yj

останов

Рис.9.21. Сортировка массива вставкой

Удаление элемента из массива

Необходимо удалить из массива Х, состоящего из n элементов, m-й по номеру элемент. Для этого достаточно записать элемент (m+1) на место элемента m, (m+2) на место (m+1) и т.д (рис.5.20, таблица 9.9.).

Таблица № 9.9. Процесс удаления элемента из массива

1

2

3

…..

m

m+1

m+2

m+3

m+4

…..

n-1

n

i=m,n-1

i=1,n-1

Xi=Xi+1

Xi

Рис. 9.20. Алгоритм удаления элемента из массив