- •С. А. Ступаков, е. А. Сидорова основы алгоритмизации омск 2008
- •Введение
- •1. Свойства и виды алгоритмов
- •2. Способы представления алгоритмов
- •3. Линейный алгоритм
- •4. Разветвляющийся алгоритм
- •4.1. Сокращенная форма разветвления
- •4.2. Полная форма разветвления
- •4.3. Задания
- •5. Циклический алгоритм
- •5.1. Арифметический цикл
- •5.2. Итерационные циклы
- •5.3. Задания
- •644046, Г. Омск, пр. Маркса, 35
5. Циклический алгоритм
Цикл – многократное выполнение (повторение) одной и той же последовательности команд, называемой телом цикла. В качестве тела цикла может выступать одна команда или несколько (составная команда). Любая циклическая конструкция (цикл) содержит в себе элементы разветвления.
Различают арифметический и итерационный циклы.
5.1. Арифметический цикл
Цикл называется арифметическим, если количество его повторений (шагов) заранее известно по условию задачи или может быть легко вычислено. Арифметический цикл имеет и другие названия: цикл с параметром, с известным числом повторений, регулярный, счетный.
В арифметическом цикле число его повторений однозначно определяется законом изменения параметра цикла. Закон изменения параметра отражается в заголовке цикла и характеризуется интервалом (начальным и конечным значениями) параметра и шагом его изменения. Обозначим: параметр цикла – x, его начальное значение – n, конечное значение – k, шаг изменения – h.
Рассмотрим процесс изменения параметра цикла:
-
1-й шаг –
x = n
2-й шаг –
x = n + h
3-й шаг –
x = n + 2h
и т. д.
. . .
последний шаг –
x = k
Цикл с параметром описывается следующим образом.
Псевдокод
НЦ
Повторить для x := n, k, h // Заголовок цикла
{Тело цикла}
КЦ
Графически цикл с параметром можно изобразить двумя способами: с применением условного блока (полная форма ГСА) и блока модификации (краткая форма ГСА). Блок модификации объединяет в себе действия блоков № 1, 2 и 4 полной формы, которая более детально отражает последовательность циклического процесса.
ГСА (полная форма) ГСА (краткая форма)
1 x
= n
Нет
Да
4x
= x +х
Пример 3. Напечатать нечетные числа от 1 до 15 (т. е. 1, 3, 5, …, 15).
Составим алгоритм решения задачи.
1) Задаем арифметический цикл с параметром i, для чего определяем интервал и шаг изменения параметра:
начальное значение – 1, конечное значение – 15; шаг изменения – 2.
2) Определяем тело цикла, которое составляет команда вывода i.
Псевдокод ГСА (краткая форма)
АЛГ Арифметический цикл
НАЧ
НЦ
Повторить для i := 1, 15, 2
Вывод i
КЦ
КОН
5.2. Итерационные циклы
Цикл называется итерационным, если число его повторений заранее неизвестно и определяется некоторым условием (например, цикл завершается при достижении отрицательного значения параметра). По этой причине ГСА итерационного циклического процесса изображается только в полной форме, использование блока модификации невозможно.
В зависимости от момента проверки условия выполнения циклического процесса итерационные циклические алгоритмы делятся на циклы с предусловием и циклы с постусловием. Число повторений тела цикла в обоих случаях зависит от входных данных задачи.
В циклах с предусловием сначала анализируется результат проверки условия и только в случае его истинности выполняется тело цикла. Цикл повторяется пока истинно условие, при невыполнении условия цикл прекращается. Особенность данного цикла заключается в том, что если изначально результат проверки условия отрицателен (ложь), то тело цикла не выполнится ни разу.
Пример 4. Заданы два числа: a = 0 и b = 5. Требуется увеличивать значения a с шагом a = 1 и выводить их до тех пор, пока выполняется условие a ≤ b.
Составим алгоритм решения задачи.
1. Ввести значения a и b (а = 0, b = 5).
2. Проверить условие: ЕСЛИ a ≤ b ТО вывести а.
3. Увеличить значение а на величину шага a = 1.
3. Повторить п. 2 и 3.
4. В случае невыполнения условия, приведенного в п. 2, закончить цикл.
Тело цикла составляют две команды: 1) вывод а, 2) а = а + 1, которые будут выполняться при следующих значениях а: 0, 1, 2, 3, 4, 5.
Псевдокод ГСА
АЛГцикл с предусловием
НАЧ
a := 0; b := 5
НЦ
ЕСЛИа ≤ bТО
Вывод а
а := а + 1
// Конец разветвления
КЦ
КОН
В отличие от цикла с предусловием тело цикла с постусловием всегда будет выполнено хотя бы один раз, после чего проверяется условие.
Решим предыдущую задачу с помощью цикла с постусловием.
Псевдокод ГСА
АЛГ цикл с постусловием
НАЧ
a := 0; b := 5
НЦ
1:Вывод а
а := а + 1
ЕСЛИа ≤bТО
Возврат к метке 1
// Конец разветвления
КЦ
КОН
Тело цикла осталось неизменным (вывод а, а = а + 1). Как и в цикле с предусловием, тело цикла будет выполняться при а = 0, 1, 2, 3, 4, 5.