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

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

· Ввод и вывод членов последовательности (Пример 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);

Рассмотрим последовательность данных a₀, a₁,…,a_i,…,a_n.

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

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

В простейшем случае используется выражение a_i=f(a_i-1) для i>0, a₀=c, где с – известное значение нулевого члена последовательности. Например, для арифметической прогрессии a_i=a_i-1+d, a₀=a, а для геометрической – b_i=b_i-1 ∙q, b₀=b. При программировании итераций такого типа используется выражение a=f(a). Использование этого выражения основано на специфике операции присваивания. Сначала вычисляется правая часть выражения при предыдущем значении a,равном a_i-1, а затем a из­меняется на вычисленное значение, тем самым получается текущее значение a,равное a_i.

С помощью рекуррентных формул удобно находить суммы и про­изведения членов последовательности. Обозначим 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.

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

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

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

Пример 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 Single Dim x, y As Single a = vvodSng3(TextBox1) b = vvodSng3(TextBox2) h = vvodSng3(TextBox3) For x = a To b Step h y = Sin(x) vivodSng3Fxy8(x, y, TextBox4) Next x EndSub

Рис. 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 Single For x = a To b Step h y = Sin(x) vivodSng3Fxy8(x, y, TextBox4) Next x End Sub

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

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

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

Dim aa, bb, hh As Single aa=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 Single Dim n, i As Integer n = CInt((b - a) / h) + 1 x = a For i = 1 To n y= Sin(x) x = x + h vivodSngFxy8(x, y, TextBox4) Next i End 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 Single Dim n, i As Integer n = CInt((b - a) / h) + 1 For i = 1 To n x = a + (i - 1) * h y = Sin(x) vivodSngFxy8(x, y, TextBox4) Next i End Sub

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

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

Обратите внимание на то, что при большом диапазоне (в интервале [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 Double Dim x, y, s As Double Dim i As Integer s = 0 x = 0 For i = 1 To n Y = Cos(8 * x) If y > 0 Then s = s + y x = x + h Next i Return s End Function

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

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

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

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

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

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

.

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

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

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

Sub Pr529(ByVal n As Integer, _ ByRef s As Long, _ ByRef p As Long) Dim f As Long Dim I As Integer f = 1 : s = 0 : p = 1 For i = 2 To n f = -i * f s = s + f p = p * f Next i End Sub

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

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

Dim ss, pp As Long Dim nn As Integer nn= vvodInt4(TextBox1) Pr529(nn, ss, pp) vivodLngFx7(ss, TextBox2) vivodLngFx7(pp, TextBox3)

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

Пример 4.5.2-4. Написать процедуру-Function, которая вычисляет
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 задано).

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

Function Pr5211(ByVal n As Integer) As Integer Dim a, b, c As Integer Dim i As Integer b = 1 c = 1 For i = 3 To n a = b + c b = c c = a Next i Return a End Function

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

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

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

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