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

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

Приведем пример схемы алгоритма циклической структуры.

Задача 3. Вычислить множество значений функции Y = X2+ b для всех значений X от –10 до 10 с шагом 2, при b = 5.

Разработка алгоритма. Значения Y необходимо вычислить 11 раз, то есть необходимо 11 раз выполнить алгоритм линейной структуры (рис. 8).

Задание X можно автоматизировать, организовав цикл. Для этого необходимо задать начальное значение X, т. е. X = –10. Далее рассчитать Y по формуле, вывести численное значение Y, изменить X и вернуться к расчету Y.

Тогда схема будет выглядеть следующим образом (рис. 9).

На рис. 10 представлена схема алгоритма циклической структуры. Блоки 3, 4, образующие тело цикла, повторяются многократно. Сколько раз? Бесконечное количество. При каждом расчете к предыдущему значению X прибавляется 2, далее следует возврат к расчету Y, вывод Y и опять X изменяется на 2. По условию задачи расчетом Y при X = 10 нужно ограничиться. Следовательно, необходимо включить условие окончания расчетов. До тех пор, пока X  10, расчеты производить; как только X станет больше 10 – вычисления закончить. В схему включим логический блок.

В блоке 2 осуществляется задание начального значения для X. В блоке 3 рассчитываются значения Y. В блоке 5 фиксируется текущее значение X с заданным шагом. В блоке 6 анализируется величина X. Если X еще не превысил своего конечного значения, то необходимо вернуться к блоку 3 и повторить вычисления. Если X стал больше предельного значения, расчеты нужно закончить.

Чтобы алгоритм стал более универсальным, начальное значение ХН, конечное значение XКи шаг изменения Х зададим в блоке ввода (рис. 11).

Величина, с изменением которой связано многократное выполнение цикла, называется параметром цикла. В нашем примере это X. Блоки 4, 5 – тело цикла. Блок 3 представляет собой подготовку цикла. Блок 6 – изменение параметра цикла (подготовка очередного шага), а блок 7 – условие продолжения цикла.

Представим схемы циклов в общем виде.

Такая циклическая структура называется циклом “До” (рис. 12). Особенность этого цикла состоит в том, что он выполняется хотя бы один раз, так как первая проверка условия выхода из цикла происходит после того, как тело цикла выполнено.

Существует еще цикл “Пока” (рис. 13).

Цикл “Пока” отличается от цикла “До” тем, что здесь проверка условия проводится до выполнения тела цикла. Если при первой проверке условие выхода из цикла выполняется, то тело цикла не выполняется ни разу.

Используем цикл типа “Пока” для нашего примера (рис. 14).

Для изображения алгоритмов циклической структуры используется также блок “модификация” (рис. 15). В блоке “модификация” объединяются несколько блоков: подготовка цикла, проверка окончания, изменение параметра цикла (подготовка очередного шага). В блоке модификации записывается параметр цикла, знак равенства (присваивание), начальное значение параметра цикла, конечное значение параметра цикла и шаг изменения параметра цикла. Для нашего примера схема алгоритма с использованием блока модификации выглядит следующим образом.

Блок 3 можно прочитать таким образом: выполнить для всех X от XH до XK с шагом X. Тело цикла выделено линией потока, замкнутой на блок модификации.

Задача 6. Определить средний рост студентов в группе.

Разработка алгоритма. Исходной информацией для решения этой задачи являются число студентов в группе и рост каждого студента. В этой задаче мы встречаемся с распространенной задачей расчета суммы. Сумма получается путем накопления слагаемых в какой–либо переменной. Накопление осуществляется в цикле. Начальному значению суммы присваивается значение ноль. В цикле к текущему значению суммы прибавляется значение очередного слагаемого S = S + R.

Число студентов в группе обозначим N. Это исходная величина. В переменной S будем накапливать сумму. Зададим S значение ноль. Подсчет номера студента будем осуществлять в переменной i. Начнем с первого студента i = 1. Вводим рост первого студента. К предыдущему значению суммы, т. е. к нулю, прибавим рост первого студента и результат присвоим переменной S. Перейдем к следующему шагу i = i+1 = 1+1 = 2. У переменной I теперь значение 2. Выполним проверку выхода из цикла. Если i не превысило еще значения N, то мы возвращаемся к блоку 5 и вводим рост следующего студента. К предыдущему значению суммы, а это рост первого студента, прибавляем рост второго студента и результат записываем в переменную S. В переменной S теперь будет храниться сумма двух значений: рост первого студента и рост второго студента. Далее переходим к следующему шагу. Цикл повторится N раз и в переменной S накопится сумма всех значений ростов студентов (рис. 16)..

Средний рост определяем по формуле S = S/N. Необходимо обратить внимание на форму записи данного выражения. В правой и в левой части этого выражения наименование одной и той же переменной. Такая запись означает: вычислить численное значение выражения в правой части и присвоить это значение переменной стоящей слева.

Запишем схему, используя блок модификации (рис. 17).

Еще раз обратите внимание на то, что блок 4 – модификация – включил в себя три блока предыдущей схемы – блоки 4, 7, 8.

Нельзя точно сказать, какая из типов циклических структур (“До” или “Пока”) скрывается в блоке “модификация”. Например, в языках программирования эта структура организована по разному.

Задача 7. Определить количество студентов в группе, имеющих рост выше среднего.

Разработка алгоритма. Исходные данные: количество студентов и рост каждого студента. Первая половина алгоритма разработана в предыдущей задаче – определен средний рост. Далее рост каждого сравнивается со средним.

Если вводимое значение роста студента превышает среднее значение, то в счетчик числа таких студентов необходимо добавить единицу К = К + 1. Счетчик образуется из переменной K, начальное значение которой полагаем равным нулю (блок 8), а суммирование происходит в блоке 12, если условие (блок 11) выполняется. В схеме А (рис. 18) имеется один недостаток: рост студентов в группе вводится дважды. Если представить, что задача решается на ЭВМ, то в этом случае придется вводить одну и ту же информацию дважды. Этот недостаток можно устранить введением переменной с индексом. В схеме В (рис. 18) рост студента обозначен переменной Ri, где i – текущий номер студента. R – одномерный массив из N элементов. Блок 10 из алгоритма исключен.

 

Задача 8. Задана последовательность из n чисел. Определить количество положительных, отрицательных и нулевых элементов.

Разработка алгоритма. Исходные данные – одномерный массив из N элементов. Назовем его А. Элементы массива – а1, а2, а3,..., аn. Ввести последовательность – это значить ввести все элементы одномерного массива. В схеме (рис. 19) будет присутствовать элемент

Этот элемент должен повториться для всех i от 1 до N. Следовательно, необходимо организовать цикл.

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

Если шаг параметра цикла равен единице (+1), то в блоке “модификация” шаг можно не указывать. Шаг 1 принято принимать по умолчанию.

Чтобы определить количество отрицательных элементов, нужно перебрать все элементы и проверить условие ai< 0. Если условие выполняется, то такой элемент нужно сосчитать, т. е., как в предыдущей задаче, отложить 1 в отведенную для подсчета переменную. К – количество отрицательных элементов, L – количество положительных элементов, M – количество нулевых элементов. Для подсчета L и M не нужно организовывать новые циклы. Подсчет количества отрицательных, положительных и нулевых элементов организован в одном цикле (рис. 20).

А – соединитель. При большой насыщенности схемы символами отдельные линии потока допускается обрывать. При этом в конце (начале) обрыва должен быть помещен символ А – соединитель.

Задача 9. Найти наибольший элемент последовательности из N элементов.

Разработка алгоритма. Схема ввода последовательности чисел (одномерного массива) разобрана в предыдущей задаче. Для поиска максимального элемента введем вспомогательную переменную M (рис. 21).

Присвоим M значение первого элемента и далее будем перебирать все элементы последовательности от 2 до N, сравнивая a и М. Если а окажется больше, чем М, то М нужно присвоить значение аi. В противоположном случае осуществляется переход к следующему элементу последовательности. По окончании цикла М примет значение наибольшего элемента.

Задача 10. Задана последовательность а1, а2,..., аN. Расположить элементы в убывающей последовательности.

Разработка алгоритма (рис. 22). Воспользуемся алгоритмом разработанным в предыдущей задаче. В исходной последовательности найдем наибольший элемент и запомним его порядковый номер К. Пусть это будет аК. Поменяем aKместами с элементом а1. Наибольший элемент оказался на первом месте. Такую процедуру нужно проделать с оставшимися элементами от 2 до N. В этом случае наибольший элемент а нужно поменять местами со вторым элементом. На втором месте окажется второй по величине элемент. Далее ищем наибольший элемент последовательности от 3 до N. Получается, что процедуру поиска наибольшего элемента нужно повторить N–1 раз. Последний элемент сам с собой можно не сравнивать. Для запоминания порядкового номера максимального элемента используем переменную К.

Блоки 2, 3, 4 – ввод одномерного массива. Блок 5 – организуется цикл для определения порядкового номера элемента, с которого начинается поиск максимального. Блоки 6, 7 – задаются начальные значения для М и К. В М записывается значение наибольшего элемента, в К – порядковый номер этого элемента. Блоки 8, 9, 10 – алгоритм поиска максимального элемента последовательности. Блок 11 – запоминаем порядковый номер элемента, записанного в М. Блок 12 – на место максимального элемента записываем i–ый элемент (с i – го элемента начинается поиск максимального). Блоки 14, 15 – вывод последовательности.

Следует обратить внимание на то, что блоки 12 и 13 нельзя поменять местами. Если это сделать, то значение а будет потеряно.

Задача 11. Вычислить сумму бесконечного ряда.

 

с точностью .

Разработка алгоритма (рис. 23). Исходными данными являются Х и . До сих пор циклы имели заданное число повторений. В данной задаче число повторений неизвестно, так как неизвестен порядковый номер последнего слагаемого. Необходимо подсчитать сумму членов последовательности, удовлетворяющих условию. Каждый член последовательности должен быть получен из предыдущего члена этой последовательности.

 

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

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

Блок 3 – обнуляем начальное значение суммы. Блок 4 – вспомогательное действие. Задание начального значения для Р. Блок 5 – задание порядкового номера члена последовательности. Блок 6 – расчет величины текущего члена последовательности. Блок 7 – сравнение текущего члена последовательности с заданной точностью. Если Р, то такой элемент нужно суммировать, если нет, то заданная точность достигнута и расчет можно закончить. Блок 8 – накопление суммы. Блок 9 – переход к следующему текущему номеру и затем к блоку 6.

В данном примере организована циклическая структура типа “Пока”.

Повторение последовательности операторов с проверкой условия в начале каждого прохода цикла называется итерацией.