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

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

Ввод и вывод членов последовательности (Пример 4.5.2-3).
Вычисление значений функций одной переменной с заданным диапазоном и шагом их изменения при заданных условиях (Пример 4.5.2-2).
Вычисление значений функций двух переменных с заданными диапазонами и шагами их изменения при заданных условиях с заданными критериями (Пример 4.5.2-8).
Вычисление конечных сумм и произведений значений функции n-го членов последовательности при заданных условиях (Примеры 4.5.2-3 – 4.5.2-4, 4.5.2-6).
Вычисление n-го члена последовательности с заданными критериями (Пример 4.5.2-5).
Определение наибольшего (наименьшего) значения функции одной и более переменных с заданными критериями (Пример 4.5.2-7);

Рассмотрим последовательность данных a0, a1,…,ai,…,an.

В одном случае член последовательности ai можно определить, вычисляя выражение ai.

В других случаях член последовательности ai можно определить через k предыдущих членов той же последовательности: ai = f(a i-k, a i-k+1,… a i-1), для k ? i.То есть, для нахождения i-го члена последовательности должны быть заданы члены a0, a1, …, ai-1. Такое определение называется итерацией или рекуррентной формулой, а алгоритмы вычисления произвольного члена последовательности – итерационными. Как правило, итерационные алгоритмы реализуются с помощью циклов – как регулярных, так и итеративных.

В простейшем случае используется выражение ai=f(ai-1) для i0, a0=c, где с – известное значение нулевого члена последовательности. Например, для арифметической прогрессии ai=ai-1+d, a0=a, а для геометрической – bi=bi-1 •q, b0=b. При программировании итераций такого типа используется выражение a=f(a). Использование этого выражения основано на специфике операции присваивания. Сначала вычисляется правая часть выражения при предыдущем значении a,равном ai-1, а затем a изменяется на вычисленное значение, тем самым получается текущее значение a,равное ai.

С помощью рекуррентных формул удобно находить суммы и произведения членов последовательности. Обозначим Sk – сумму k членов последовательности a1,… ai,… an. Очевидно, что Sk=S k-1 + ak для k=1,…, n; начальное значение суммы следует обнулить — S0=0. Аналогично произведение k членов этой последовательности Pk=Pk-1 •ak, для k=1,…,n; начальное значение произведения надо установить равным единице, P0=1.

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

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

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

Пример 4.5.2-1. Написать процедуру-Sub, которая вычисляет значение функции y(x) = sin(x) при значениях x, изменяющихся на отрезке [a; b] с шагом h.

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

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

Sub Pr521()Dim a, b, h As SingleDim x, y As Singlea = vvodSng3(TextBox1)b = vvodSng3(TextBox2)h = vvodSng3(TextBox3)For x = a To b Step hy = Sin(x)vivodSng3Fxy8(x, y, TextBox4)Next xEndSub

Рис. 4.5.2-1. Схема алгоритма и программный код процедуры Pr521(),в которойиспользуется в качестве параметра цикла переменная вещественного типа с вводом/выводом Примера 4.5.2-1

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

Процедура Pr521()может быть вызвана, например, как показано на
рис. 4.5.2-2.

Pr521( )

Рис. 4.5.2-2. Пример вызова процедуры Pr521()

Если процедура не будет содержать ввода данных, то она будет выглядеть, как показано на рис. рис. 4.5.2-3.

Sub Pr523(ByVal a As Single, _ByVal b As Single, _ByVal h As Single)Dim x As Single, y As SingleFor x = a To b Step hy = Sin(x)vivodSng3Fxy8(x, y, TextBox4)Next xEnd Sub

Рис. 4.5.2-3. Схема алгоритма и программный код процедуры Pr523(),

в которойиспользуется в качестве параметра цикла переменная вещественного типа выводом данных Примера 4.5.2-1

Процедура вызова Pr523() может быть, например, как показано на
рис. 4.5.2-4.

Dim aa, bb, hh As Singleaa=vvodSng3(TextBox1)bb=vvodSng3(TextBox2)hh=vvodSng3(TextBox3)Pr523(aa, bb, hh)

Рис. 4.5.2-4. . Пример вызова процедуры Pr523()

В алгоритме решения данной задачи используется регулярная циклическая структура, которая в программе реализована оператором For …Next, а в качестве параметра цикла используется вещественный аргумент функции – х.

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

Sub Pr525(ByVal a As Single, _ByVal b As Single, _ByVal h As Single)Dim x, y As SingleDim n, i As Integern = CInt((b — a) / h) + 1x = aFor i = 1 To ny= Sin(x)x = x + hvivodSngFxy8(x, y, TextBox4)Next iEnd Sub

Рис. 4.5.2-5. Схема алгоритма и программный код процедуры Pr525(),

в которойиспользуется в качестве параметра цикла переменная целого типа, а очередное значение х вычисляется через предыдущее путем добавления шага Примера 4.5.1-3

Избежать подобных неприятностей можно путем предварительного вычисления числа повторений цикла и использования в качестве параметра цикла переменной целого типа, назначение которого – подсчет количества повторений цикла (рис. 4.5.2-5 и рис. 4.5.2-6). Различие между алгоритмами состоит только в способах вычисления текущего значения аргумента x. В первом алгоритме очередное значение х вычисляется через предыдущее путем добавления шага, а во втором алгоритме х вычисляется через параметр цикла.

Sub Pr526(ByVal a As Single, _ByVal b As Single, _ByVal h As Single)Dim x, y As SingleDim n, i As Integern = CInt((b — a) / h) + 1For i = 1 To nx = a + (i — 1) * hy = Sin(x)vivodSngFxy8(x, y, TextBox4)Next iEnd Sub

Рис. 4.5.2-6. Схема алгоритма и программный код процедуры Pr526(),

Обратите внимание на то, что при большом диапазоне (в интервале [a; b] переменная a имеет маленькое значение, а переменная b большое) c маленьким шагом h, вычисление по формуле x=x+h дает большую погрешность, чем формула x=a+(i-1)*h (даже при использовании данных типа Double).

Пример 4.5.2-2. Написать процедуру-функцию, которая вычисляет сумму положительных значений функции y=cos(8x) при изменении x от 0 до p с шагом p/16.

Алгоритм решения данной задачи относится к алгоритмам вычисления конечных сумм (рис.4.5.2-7).

Процедура-функция Pr527() может быть вызвана из любой другой процедуры или из модуля формы, например, как показано на рис. 4.5.2-8.

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

Function Pr527(ByVal n As Integer,_ByVal h As Double) As DoubleDim x, y, s As DoubleDim i As Integers = 0x = 0For i = 1 To nY = Cos(8 * x) If y0 Then s = s + y x = x + h Next iReturn sEnd Function

Рис.4.5.2-7. Схема алгоритма и программный код процедуры Pr527() Примера 4.5.2-2

Dim ss, hh As DoubleDim nn As Integerh = Math.PI / 16n = CInt((Math.PI -0) / h) + 1’nn=17ss = Pr527(nn, hh)vivodDblFx6(ss, TextBox1)

Рис. 4.5.2-8. Пример вызова процедуры Pr527()

Алгоритм решения данной задачи относится к алгоритмам вычисления конечных сумм (рис.4.5.2-7).

Так как при таком способе организации цикла (через целый параметр), аргумент x уже не будет автоматически изменяться при каждом повторении цикла, то в тело цикла добавляется оператор x=x+h, который обеспечивает изменение xна величину шага h при каждом повторении цикла. При этом начальное значение аргумента x должно быть установлено перед первым входом в цикл (x=0). Начальное значение суммы также следует установить равным нулю до цикла (s=0), чтобы после нахождения первого подходящего значения y0 значение суммы стало равно этому значению. Заметим, что если в задаче требуется вычислить конечное произведение, то начальное значение переменной, которая будет накапливать произведение, следует установить равным единице (p=1).

Пример 4.5.2-3. Написать процедуру-Sub, которая вычисляет сумму и произведение n членов последовательности по формуле
fi = -i • fi-1,аf0 = 1.

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

Sub Pr529(ByVal n As Integer, _ByRef s As Long, _ByRef p As Long)Dim f As LongDim I As Integerf = 1 : s = 0 : p = 1For i = 2 To nf = -i * fs = s + fp = p * fNext iEnd Sub

Рис. 4.5.2-9. Схема алгоритма и программный код процедуры Pr529() Примера 4.5.2-3

Процедура Pr529() может быть вызвана из любой другой процедуры или из модуля формы, например, как показано на рис. 4.5.2-10.

Dim ss, pp As LongDim nn As Integernn= vvodInt4(TextBox1)Pr529(nn, ss, pp)vivodLngFx7(ss, TextBox2)vivodLngFx7(pp, TextBox3)

Рис. 4.5.2-10. Пример вызова процедуры Pr529()

Пример 4.5.2-4. Написать процедуру-Function, которая вычисляет
n-й член последовательности по формуле fi= fi-1 + fi-2, а f0 = f1 = 1.

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

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

Function Pr5211(ByVal n As Integer)As IntegerDim a, b, c As IntegerDim i As Integerb = 1c = 1For i = 3 To na = b + cb = cc = aNext iReturn aEnd Function

Рис. 4.5.2-11. Схема алгоритма и программный код процедуры Pr5211() Примера 4.5.2-4

Процедура – функция Pr5211() может быть вызвана из любой другой процедуры или из модуля формы, например, как показано на рис. 4.5.2-12.

Dim aa As IntegerDim nn As Integernn = vvodInt4(TextBox1)aa = Pr5211(nn)vivodInt4(aa, TextBox2)

Рис. 4.5.1-12. Пример вызова процедуры Pr5211()

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

Статьи к прочтению:

Основы Программирования — #1 — Логика. Алгоритмы

Похожие статьи: