Типовые алгоритмы регулярных циклических структур и примеры их программирования.

Программирование алгоритмов регулярной циклической структуры.

 

Важным и неотъемлемым элементом любого серьезного алгоритма (программы) являются циклы – второй наряду с разветвлениями краеугольный камень программирования. Без использования этого мощного инструмента само программирование вряд ли существовало бы как область человеческой деятельности, превратившись в бессмысленное занятие.

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

Разумеется, многократное повторение выполнения тела цикла не является бессмысленным. При каждом повторении меняются значения некоторых переменных или свойств объектов, присутствующих в теле цикла. Как правило, эти изменения и приводят в конечном счете к решению задачи, реализуемой данным алгоритмом (программой).

Пусть, например, необходимо вычислить сумму S числовой последовательности a₁, a ₂ , … a ₁₀₀. Выполнять такие вычисления в рамках линейной структуры – это безумие. Гораздо эффективнее использовать циклическую структуру: в тело цикла поместить оператор вида S = S + a_i, который при каждом повторении цикла будет добавлять к предыдущему значению суммы очередной член последовательности. Разумеется, необходимо начальное значение S установить равным нулю до начала цикла и обеспечить изменение индекса i от 1 до 100 с шагом 1. В результате после завершения цикла в переменной S накопится искомая сумма.

Различают циклы двух видов: с заранее известным и с заранее неизвестным числом повторений цикла.

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

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

Циклы организуются с помощью базовых циклических структур и их программной реализации. В любой циклической структуре помимо тела цикла всегда присутствует оператор проверки условия и обеспечения выхода из цикла. Но это не оператор разветвления (if в C++), а один из специальных операторов, специфических для каждой базовой структуры.

Имеются всего 3 базовые циклические структуры, отличающиеся способом организации цикла и местом проверки условия выхода из цикла: цикл с предусловием, цикл с постусловием, цикл с предусловием и параметром. Мы рассмотрели их в лекции 7.  В языке C++ они программируются операторами while, do и for.

В этой лекции будем рассматривать именно третью базовую циклическую структуру цикл с предусловием и параметром – цикл for (рис.1).

 

Рисунок 1 -  Структура Цикл с предусловием и параметром

Напомним, что в таком цикле всегда присутствует переменная – параметр цикла (в данном случае p). Начало цикла обозначается символом Подготовка, внутри которого записываются начальное m ₁ и конечное m ₂ значения параметра, а также шаг его изменения m ₃. Если шаг равен 1, то при записи алгоритма он может быть опущен.

При первом входе в цикл параметр p принимает значение m ₁. При каждом входе в цикл проверяется условие p <=   m ₂, т.е. текущее значение параметра сравнивается с его конечным значением. Если условие истинно, то выполняются операторы a ₁, … a_n, составляющие тело цикла, значение параметра увеличивается на величину шага m ₃, и затем управление передается в начало цикла. Как только условие становится ложным (p >   m ₂), происходит выход из цикла.

На рис. 1б изображена “эквивалентная схема” цикла с параметром, реализованная с помощью обычного цикла с предусловием. Из нее следует, что можно обойтись без структуры с параметром, но она компактней и удобнее.

На рис. 1в показано, как цикл с предусловием и параметром изображается по правилам действующего ГОСТ. Здесь имя цикла обычно заменяется именем параметра цикла.

Число повторений цикла с параметром может быть вычислено по формуле, приведенной на рис. 1а. Здесь квадратные скобки обозначают целую часть результата деления.

В языке С++ цикл с параметром реализуется с помощью оператора for. В Примере 1, приведенном ниже на рис.2, выводятся на экран квадраты целых чисел от 0 до 14, и цикл будет выполняться 15 раз:

Результат работы программы выглядит так:

Рисунок 2 -  Простейший цикл с параметром и результаты

Оператор for управляет циклом. Он состоит из ключевого слова for, за которым следуют круглые скобки, содержащие три выражения, разделенные точками с запятой:

for (j = 0 ; j < 15 ; j++)

Первое из трех выражений называют инициализирующим, второе —условием выполнения, а третье — инкрементирующим (модификацией), как показано на рис. 3. Эти три выражения, как правило (но не всегда), содержат одну переменную, которую обычно называют параметром (счетчиком) цикла. В примере счетчиком цикла является переменная j. Она определяется до того, как начнет исполняться тело цикла. Под телом цикла понимается та часть кода, которая периодически исполняется в цикле. В нашем примере тело цикла состоит из единственного оператора,

cout << j * j << " " ;

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

Рисунок 3 -  Синтаксис цикла for

 

Обратите внимание на то, что после оператора for отсутствует точка с запятой (;). Это объясняется тем, что на самом деле оператор for вместе с телом цикла представляют из себя один оператор. Это очень важная деталь, поскольку если поставить после оператора for точку с запятой, то компилятор воспримет это как отсутствие тела цикла, и результат работы программы будет отличаться от задуманного.

 Таким образом, синтаксис (формат) оператора for имеет вид:

for (инициализация; выражение1; модификация) оператор;

Как уже говорилось, здесь:

· Инициализация используется дляобъявления и присвоения начальных значений величинам, используемым в цикле. Инициализирующее выражение вычисляется только один раз — в начале выполнения цикла. В примере вычисленное значение инициализирует счетчик цикла (j =0)

· выражение1 определяет условие выполнения цикла и если его результат равен true, то цикл выполняется. Как правило, условие выполнения цикла содержит в себе операцию отношения. Условие проверяется каждый раз перед исполнением тела цикла и определяет, нужно ли исполнять цикл еще раз или нет. Если условие выполняется, то есть соответствующее выражение истинно, то цикл исполняется еще раз. В противном случае управление передается тому оператору, который следует за циклом. В примере 1 после завершения цикла управление передается оператору cout << endl;

· модификация (инкрементирующее выражение) – выполняется после каждой итерации цикла и служит обычно для изменения параметра (счетчика) цикла. Модификация счетчика происходит после того, как тело цикла полностью выполнилось. В примере 1 увеличение j на единицу происходит каждый раз после завершения тела цикла

· оператор – простой илисоставной оператор (блок операторов в фигурных скобках) представляет собой тело цикла.

Итак, порядок выполнения оператора for следующий:

1) Сначала один раз вычисляется инициализирующая часть.

2) Затем вычисляется выражение1 (условие продолжения цикла) и если его результат равен true, то выполняется текущая итерация:

· выполняется тело цикла;

· вычисляется модификация (инкрементирующее выражение).

3) Итерации продолжаются пока выражение1 (условие продолжения цикла) не примет значение false .

Схема алгоритма, иллюстрирующая выполнение цикла  for в языке С++ показана на рис.4:

Рисунок 4 -  Исполнение цикла for в С++

Из этой схемы видно, что оператор for реализует цикл с предусловием. Но на схемах алгоритмов цикл for мы будем изображать схемой, показанной на рис. 1а.

 Важное замечание: если при первом же входе в цикл условие повторения цикла не выполняется, то сразу же произойдет выход из цикла, и тело цикла не выполнится ни разу.

 

Типовые алгоритмы регулярных циклических структур и примеры их программирования.

 

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

· вычисление значений функции одной переменной в заданном диапазоне изменения аргумента с заданным шагом;

· вычисление значений функции двух и более переменных в заданных диапазонах изменения аргументов с заданным шагом;

· вычисление конечных сумм и произведений значений функций и членов последовательностей;

· определение наибольшего (наименьшего) значения функции одной и более переменных;

· формирование последовательностей по заданным правилам;

· определение члена последовательности с заданным номером.

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

Почти во всех задачах, использующих для решения алгоритмы регулярной циклической структуры, явно или неявно формируется последовательность некоторых значений. Рассмотрим подробнее последовательность данных a₀, a₁,…,a_i,…,a_n.

Иногда член последовательности a_i можно определить, вычисляя выражение a_i по заданной формуле. В некоторых других случаях член последовательности a_i можно определить через k предыдущих членов той же последовательности: для .

То есть, для нахождения i-го члена последовательности должны быть заданы члены a₀, a₁, …, a_i-1. Такое определение называется рекуррентной формулой.

В простейшем случае используется выражение  для i>0, a₀= с, где с – известное значение нулевого члена последовательности. Например, для арифметической прогрессии  (где a₀= a – первый член, d – разность прогрессии); для геометрической –  (где b₀=b  первый член, q – знаменатель прогрессии). С помощью таких рекуррентных формул удобно находить суммы и про­изведения членов последовательности. Обозначим S_k – сумму k членов последовательности a₁,… a_i,… a_n. Очевидно, что S_k=S_k-1 + a_k для k=1,…, n; начальное значение суммы следует обнулить - S₀=0. Аналогично произведение k членов этой последовательности P_k = P_{k -1} ∙ a_k, для k =1,…, n; начальное значение произведения надо установить равным единице, P ₀ =1.

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

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

Пример 2. Разработать алгоритм и запрограммировать функцию вычисления факториала заданного целого числа n.

По определению f=n!=1 ∙ 2 ∙ …∙ (n-1) ∙ n  (при n≥1) и f=0!=1(при n=0).

Таким образом, вычисление факториала сводится к задаче вычисления произведения значений целых чисел, изменяющихся от 1 до n с шагом 1.

Накопление произведения будем производить по рекуррентной формуле: f_i = f_{i -1} ∙ i ; ; f ₀ = 1.

Схема алгоритма и программный код функции приведены на рис. 5.

 Рисунок 5 -  Алгоритм и программный код функции вычисления n !

Функция fact и переменная f объявлены беззнаковыми длинными целыми, чтобы увеличить диапазон возможных значений n, т. к. даже для небольших чисел значения их факториалов очень велико (например, 10! = 3628800). Если n >=2, то цикл повторяется n раз, если n равно нулю или 1 – то ни разу(0! =1, 1! =1). Также обратите внимание, что переменная i объявлена прямо внутри оператора цикла: for ( int i=2; i<=n; i++). Такое определение переменной типично для С++ и, как правило, очень удобно для работы со счетчиками цикла, т.к. стоит наиболее близко к месту употребления этой переменной. Однако, следует помнить, что переменная, описанная в операторе цикла, видна только внутри этого цикла.

Пример 3. Разработать алгоритм и запрограммировать процедуру, котораяформирует таблицу значений функции y ( x )= sin ( x )  ивычисляет сумму значений этой функции при изме­нении x от a до b с шагом h . Значения a , b , h – вводимые величины.

На рисунке 6 приведены схема алгоритма и программный код самого простого варианта решения этой задачи: с использованием аргумента функции x в качестве параметра цикла. Вычисление суммы S производится по рекуррентной формуле: S_i = S_{i -1} + y ( x_i ) ; начальное значение суммы S ₀ = 0.

 

Рисунок 6 -  Алгоритм и программный код функции примера 3, с параметром цикла вещественного типа (первый способ).

Рисунок 7 -  Результаты работы функции примера 3 с параметром цикла вещественного типа (первый способ).

Однако, если мы, например, выполним программу при a =0, b =1 и h =0.1, то последнее выведенное в цикле значение x оказывается равным 0.9 (в режиме отладки видно, что на самом деле оно равно 0.9000001), т.е. точка x = b =1 в таблице не выводится и в сумму не попадает (см. рис. 7).

Дело в том, что параметр цикла x, а также границы и шаг его изменения представляют собой данные вещественного типа (float), представляемые в памяти приближенно. В десятичной системе счисления шаг 0.1 является конечной десятичной дробью, но в двоичной системе – это бесконечная двоичная дробь, и в памяти компьютера хранится ее округленное значение. Эта погрешность округления в цикле накапливается, и последнее значение x оказывается больше 1.

Т.е. такой способ организации цикла опасен тем, что в результате погрешностей округления последнее зна­чение параметра может оказаться не равным в точности значению верхней границы b, и если оно окажется больше b , то выполнение цикла прекратится, a в результате таблица значений функции будет содержать на одну точку меньше.

Как избежать этого неприятного эффекта при решении данной задачи и множества схожих задач? На рис.8 приведены схема алгоритма и программный код второго варианта решения. Суть его заключается в том, что в качестве верхней границы цикла берется значение, сдвинутое на полшага вправо (b + h/2). Если шаг не слишком мал, во всяком случае на порядок больше погрешности округления, то такой способ позволяет избежать ошибки первого способа.

Рисунок 8 -  Алгоритм и программный код функции примера 3, с параметром цикла вещественного типа (второй способ).

Однако более универсальным способом организации цикла в таких задачах является использование целой переменной в качестве параметра цикла. Вернемся к схеме алгоритма регулярного цикла с параметром на рисунке 1а. Цикл с параметром позволяет организовывать регулярные циклы, так как число повторений цикла n определяется значениями m₁, m₂ и m ₃ и может быть заранее вычислено по формуле:

n = [(m₂ - m₁) / m ₃ ] + 1

где квадратные скобки обозначают целую часть результата деления.

 На рис.9 приведены схема алгоритма и программный код третьего варианта решения. Здесь в теле пользовательской функции рассчитано количество значений переменной x (количество повторений цикла n) по вышеприведенной формуле. Циклом управляет целая переменная i, изменяющаяся от 1 до n с шагом 1, начальное значение x = a задается перед входом в цикл, а изменение x на величину шага при каждом повторении цикла производится отдельным оператором в теле цикла.

 

Рисунок 9 -  Алгоритм и программный код функции примера 3, с параметром цикла целого типа, в котором очередное значение аргумента вычисляется через предыдущее путем добавления шага (третий способ).

Внимание, ошибка! В операторе вычисления n должна использоваться функция floor .

 

Но и третий вариант решения задачи имеет один недостаток. При малом шаге h относительно значений a и b выполнение оператора x = x + h сопровождается вычислительной погрешностью, которая накапливается с каждым повторением цикла и при большом числе повторений может стать довольно существенной. Это приведет в данной задаче к тому, что мы будем вычислять значения Sin(x) не в тех точках, где хотелось бы.

На рис.10 приведены схема алгоритма и программный код четвертого варианта решения поставленной задачи. Здесь значение x вычисляется при каждом повторении цикла независимо, через параметр цикла i, поэтому вычислительная погрешность не накапливается.

 

Рисунок 10 -  Алгоритм и программный код функции примера 3, с параметром цикла целого типа, в котором очередное значение аргумента вычисляется через параметр цикла (четвертый способ).

Внимание, ошибка! В операторе вычисления n должна использоваться функция floor .

 

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

Для сравнения приведем результаты работы функций для первого и последнего (четвертого) способов организации работы регулярного цикла. На рисунке 11 приведен программный код главной функции, которая вызывает выше приведенные пользовательские функции CikL1() и CikL4().

 

Рисунок 11 -  Программный код и результаты выполнения главной функции примера 3, в которой вызываются  функции,

решающие задачу 1-м и 4-м способами.

Пример 4. Разработать алгоритм и программный код процедуры,  которая находит наименьшее значение функции y = c ∙ e ^{- dx} ∙ sin (2 x +5), где c , d – входные параметры, а x изменяется на отрезке [ a ; b ] с шагом h .

Схема алгоритма и код программы приведены на рис. 12.

Алгоритм нахождения наименьшего (наибольшего) значения функции основан на последовательном сравнении очередного значения функции с текущим наименьшим (наибольшим) значением функции. В качестве начального наименьшего значения ymin следует использовать число, близкое к наибольшему числу из диапазона возможных значений того типа данных, который описывает рассматриваемую функцию, чтобы наверняка при первом же проходе цикла выполнилось условие y < ymin. То есть, за ymin можно принять число, близкое к наибольшему числу из диапазона значений данных типа float, например, для данной задачи за начальное наименьшее значение принято 10³⁸. Соответственно, за начальное значение ymax можно принять отрицательное число -10³⁸, т.е. число, близкое к наименьшему числу из диапазона значений float, для того, чтобы при первом проходе цикла гарантированно выполнялось условие y > ymax. Для определения значения аргумента xmin ( xmax ), соответствующего найденному наименьшему (наибольшему) значению функции при каждом переопределении текущего наименьшего (наибольшего) значения функции надо одновременно переопределять текущее значение xmin ( xmax ).

 

Рисунок 12 -  Схема алгоритма и программный код процедуры Примера 4

Внимание, ошибка! В операторе вычисления n должна использоваться функция floor .

Пример 5. Разработать алгоритм и программный код процедуры, которая вычисляет n -й член последовательности по формуле f_i = f_{i -1} + f_{i -2} , причем f ₀ = f ₁ = 1 .

Это задача вычисления чисел Фибоначчи, которые определяются по заданной формуле. В данном примере каждый очередной член последовательности зависит от двух предыдущих. Обозначим b= f ₀ , с= f ₁ . Тогда очередной член последовательности a = b + c. Далее операторы присваивания b = c и c = a изменяют значения b и c для очередного вычисления a. Таким образом, значение предыдущего члена последовательности присваивается предшествующему ему члену последовательности (b = c), а значение только что вычисленного члена a присваиваем предыдущему (c = a). Начальное значение параметра цикла i =3, так как вычисление начинается с 3-го члена (два первых числа Фибоначчи f ₀ = f ₁ =1 заданы).

Схема алгоритма и код программы приведены на рис. 13.

 

Рисунок 13 - Схема алгоритма и программный код задачи вычисления n-го числа Фибоначчи для Примера 5

Вложенные циклы

На практике часто встречаются алгоритмы, в которых в теле одного, внешнего цикла находится другой, вложенный цикл. Как правило, оба таких цикла представляют собой циклы с параметром. В таких алгоритмах нет ничего принципиально нового, и их схемы представляют собой комбинацию рассмотренных базовых структур.

Пример 6. Разработать алгоритм и запрограммировать функцию вычисления 1 ^k + 2 ^k + … + n^k для заданных натуральных n и k с использованием операций умножения и сложения без использования математической функции возведения в степень pow (). Заметим, кстати, что такой функции для натуральных чисел в языке С++ нет.                      

На рис. 14 приведены схема алгоритма и программный код функции, использующей вложенные циклы с параметром. Во внутреннем цикле вычисляется степень i^k путем последовательного умножения i самого на себя k раз. Во внешнем цикле накапливается сумма n слагаемых, каждое из которых есть очередное натуральное число, возведенное в k-ю степень.

Рисунок 14 - Схема алгоритма и программный код задачи Примера 6

Пример 7. Разработать алгоритм и программный код процедуры, которая формирует таблицу значений функции от двух переменных z(x,y)=x²+y² в заданных диапазонах значений аргументов , если шаг изменения x равен hx, а шаг изменения y равен hy .

Эта задача табулирования функции похожа на задачу Примера 3, только здесь требуется получить таблицу для функции не от одного, а от двух независимых аргументов, каждый из которых изменяется на своем заданном отрезке со своим заданным шагом. Для ее решения также удобно использовать вложенные циклы с параметром, предварительно вычислив число повторений каждого цикла исходя из начального и конечного значений и шага изменения каждого аргумента. Схема алгоритма и код программы приведены на рис. 15. Заметим, что здесь каждый аргумент изменяется путем прибавления шага, т.е. третьим способом, показанным в Примере 3.

Рисунок 15 - Схема алгоритма и программный код задачи Примера 7

 

Внимание, ошибка! В операторах вычисления n и m должна использоваться функция floor .

---

Дата добавления: 2020-11-29; просмотров: 651; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!