Полная версия

Главная arrow Информатика arrow Базовые средства программирования на Visual Basic в среде VisualStudio. Net

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

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

Рассмотрим сумму вида S= а + а + а + . . . Пусть имеется положительное число е> 0, называемое точностью вычислений. Во многих задачах точность вычисления суммы S считается достигнутой, когда выполняется одно из следующих условий:

• разность , где S. - сумма на i-м шаге цикла (т.е. сумма

содержит i слагаемых), a SM- сумма на предыдущем шаге;

• разность , где а,- значение слагаемого на i-м шаге, а а — на

предыдущем шаге цикла;

• значения и значение

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

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

При описании базовых алгоритмов регулярных циклических структур мы приводили примеры вычисления сумм и произведений конечного (заранее известного) числа членов последовательности (Примеры 5.2-3, 5.2-4, 5.2-5).

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

Если задано некоторое число ?, условия окончания итерационного процесса могут, например, быть следующими:

  • • для убывающей последовательности ап< ?;
  • • для возрастающей последовательности ап> ? (Примеры 6.2-1, 6.2-3,
  • 6.2- 5);
  • • для убывающей знакопеременной последовательности |aj< ? (Пример
  • 6.2- 4);
  • • для некоторых других последовательностей |а -aj< ? (Пример 6.2-2).

Рассмотрим примеры алгоритмов итерационного типа, реализуемых с использованием итеративных циклов.

Пример 6.2-1. Написать процедуру-Function, которая среди последовательности чисел, ... находит первое число, боль шее заданного значения переменной а.

Алгоритм решения данной задачи относится к алгоритмам вычисления членов бесконечных последовательностей (рис.6.2-1).

Схема алгоритма и программный код процедуры Рг621( ), которая среди последовательности чисел находит первое число, большее заданного значения, используя оператор Do While... Loop

Рис. 6.2-1.Схема алгоритма и программный код процедуры Рг621( ), которая среди последовательности чисел находит первое число, большее заданного значения, используя оператор Do While... Loop

Примера 6.2-1

Этот алгоритм использует итеративный цикл с предусловием и реализуется с помощью конструкции Do While... Loop.

Для решения данной задачи проведем формализацию. Для этого введем следующие обозначения: b - очередной член бесконечной последовательности; П - номер этого члена, который в данной задаче совпадает со значением знаменателя дроби, добавляемой к предыдущему члену для получения значения очередного члена последовательности. Таким образом, итерационная формула вычисления очередного члена последовательности будет иметь следующий вид:

, где п - номер члена.

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

Рис. 6.2-2. Пример обращения к процедуре Рг621()

Решение данного примера может быть реализовано также с использованием конструкции Do Until...Loop (рис. 6.2-3), а цикл с предусловием можно заменить на цикл с постусловием и соответствующим ему изменением настройки цикла (рис. 6.2-4).

Изменим в цикле условие продолжения выполнения цикла (на рис. 6.2-1 заменим условие Ь<=а на условие Ь>а), т е. будем проводить вычисления членов последовательности до тех пор, пока не встретится член, больший заданного числа. Заменим условие Ь<=а на условие Ь>а.

Тогда алгоритм и функция будут выглядеть, как на рис. 6.2-3.

Если вычисление членов последовательности проводится в теле цикла, начиная с первого, то алгоритм и процедура-функция примут вид, показанный на рис 6.2-4.

Мы получили структуру итеративного цикла с постусловием, изменив настройку цикла: П=0, Ь=0. В данном случае условием окончания вычислительного процесса служит значение True логического выражения Ь>а, а продолжением - значение False (конструкция Do...Loop Until).

Изменив условие на Ь<=а, получим конструкцию цикла с Do...Loop Wile.

Следовательно, задача может быть решена с использованием как цикла с предусловием, так и цикла с постусловием.

Схема алгоритма и программный код процедуры Рг621(), которая среди последовательности чисел находит первое число, большее заданного значения, и, используя оператор Do Until...Loop

Рис. 6.2-3. Схема алгоритма и программный код процедуры Рг621(), которая среди последовательности чисел находит первое число, большее заданного значения, и, используя оператор Do Until...Loop

Примера 6.2-1

Схема алгоритма и программный код процедуры Рг624(), которая среди последовательности чисел находит первое число, большее заданного значения, используя, оператор Do...Loop Until

Рис. 6.2-4. Схема алгоритма и программный код процедуры Рг624(), которая среди последовательности чисел находит первое число, большее заданного значения, используя, оператор Do...Loop Until

Примера 6.2-1

Пример 6.2-2. Написать процедуру-Function, которая вычисляет корень уравнения ех + х = 0 с точностью ?=10'4.

Воспользуемся известной итерационной формулой х =— eXi,

где i=0,1, 2,...; х0=0. Следует закончить итеративный процесс, как только |х.+1-х.| станет меньше ?=10'4.

Для решения этой задачи необходимо из очередного приближения вычисленного корня х.+1 вычитать значение предыдущего приближения корня х. Для этого при каждом повторении цикла перед вычислением очередного значения корня х, сохраняем в переменной а текущее значение х (оно становится предыдущим). Цикл прекращаем, если разность между а (т. е. х.) и х (т. е. х.+1) станет меньше ?=10‘4.

Алгоритм решения данной задачи относится к итерационным алгоритмам (рис. 6.2-5) и может быть реализован, например, с помощью конструкции Do ... Loop Until с постусловием.

Схема алгоритма и программный код процедуры Рг625 ( ), которая реализует ввод данных с их проверкой Примера 6.2-2

Рис. 6.2-5. Схема алгоритма и программный код процедуры Рг625 ( ), которая реализует ввод данных с их проверкой Примера 6.2-2

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

Пример 6.2-3. Задана возрастающая последовательность

Требуется написать программу, которая вычисляет все члены последовательности, до тех пор, пока значение очередного члена не превысит некоторое заданное число d, например (3

В нашей задаче для вычисления любого члена последовательности можно

воспользоваться формулой , где n=0,1, 2,... - номер члена.

Во многих задачах, использующих итеративные алгоритмические структуры, следует предусмотреть так называемую «страховку от зацикливания», так как иногда условие продолжения цикла остается истинным бесконечно. В данном примере цикл с постусловием будет выполняться не более 100 раз, даже если очередной член последовательности будет оставаться меньше d (рис. 6.2-7). Так как вывод в Text Box членов последовательности должен происходить в процессе вычисления (внутри цикла), то для решения задачи напишем процедуру-Sub, для которой (в отличие от Function) не требуется возврата одного значения.

Схема алгоритма и программный код процедуры Рг627( ), которая вычисляет члены последовательности до выполнения определенных условий Примера 6.2-3

Рис. 6.2-7. Схема алгоритма и программный код процедуры Рг627( ), которая вычисляет члены последовательности до выполнения определенных условий Примера 6.2-3

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

Пример обращения к процедуре Рг627 ( )

Рис. 6.2-8. Пример обращения к процедуре Рг627 ( )

Пример 6.2-4. Написать процедуру-функцию, которая вычисляет сумму членов знакопеременной убывающей последовательности с заданной точностью ?:

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

Отметим, что во многих задачах непосредственный подсчет очередного члена связан с вычислительными трудностями. В этом случае целесообразно использовать рекуррентную формулу, которая позволяет вычислить значение переменной на следующем шаге, используя ее значение на текущем шаге - ап+1 = ап' 9 • Выражение для q можно получить, разделив ап+1 член на Эп член.

Приведем вывод рекуррентной формулы для заданного в примере ряда. Формула для п-го члена приведена в задании:

, тогда формула п+1 члена:

Разделив ап+1 член на ап, получим выражение для q:

Таким образом, рекуррентная формула для данного ряда:

Выбор начального значения номера члена ряда (п) для нашего случая будет п=0, так как при подстановке этого значения в формулу n-го члена ряда

мы получим значение первого члена, равного х-1 или а=х-1.

Схема алгоритма и процедура-Function приведены на рис. 6.2-9, причем алгоритм этот с предусловием, в котором предусмотрено выполнение цикла не более 100 раз, чтобы избежать возможного зацикливания.

Схема алгоритма и программный код процедуры Рг629( ), которая вычисляет сумму членов знакопеременной убывающей последовательности с точностью ? Примера 6.2-4

Рис. 6.2-9. Схема алгоритма и программный код процедуры Рг629( ), которая вычисляет сумму членов знакопеременной убывающей последовательности с точностью ? Примера 6.2-4

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

Пример обращения к процедуре Рг629( )

Рис. 6.2-10. Пример обращения к процедуре Рг629( )

Рекуррентную формулу для вычисления очередного значения члена последовательности, приведенную выше, можно вычислить по-другому, используя его значение на предыдущем шаге ап = ап_1 • q.

Для этого случая вывод будет следующий:

Тогда

Таким образом, рекуррентная формула в этом случае:

Схема алгоритма и код процедуры-функции приведены на рис. 6.2-11. В этом случае, в отличие от предыдущего, увеличивать n (п=п+1) следует до, а не после вычисления очередного члена ряда.

Схема алгоритма и программный код процедуры Рг6211(), которая вычисляет сумму членов знакопеременной убывающей последовательности с точностью ? Примера 6.2-4

Рис. 6.2-11. Схема алгоритма и программный код процедуры Рг6211(), которая вычисляет сумму членов знакопеременной убывающей последовательности с точностью ? Примера 6.2-4

Пример 6.2-5. Написать процедуру-Sub, вычисляющую сумму всех чисел Фибоначчи, которые не превосходят заданного натурального числа ш, и определить количество таких чисел.

Числа Фибоначчи (F.) определяются по формулам

т. е. каждое очередное число равно сумме двух предыдущих.

Подобная задача была решена при рассмотрении регулярных циклических структур (пример 5.2-4). Однако здесь число слагаемых (членов последовательности) заранее неизвестно, поэтому организуем итеративный цикл с предусловием. Обозначим это число слагаемых к. В данном примере до начала цикла задаются значения трех чисел Фибоначчи F0, F1? и F2=F0+F1=2, и их сумма S=F0+Fj+F2=4. В цикле переопределяем значение переменных F0 и Ff, выводим очередное (предыдущее) число Фибоначчи, вычисляем следующее число и добавляем его в сумму. Когда текущее число Фибоначчи превосходит заданное число m (F22). Таким образом, в окончательном значении суммы будут учтены только те числа Фибоначчи, которые еще не превосходят Ш.

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

Схема алгоритма и программный код процедуры Рг6212(), которая вычисляет сумму чисел Фибоначчи, не превосходящих заданного натурального числа Ш Примера 6.2-5

Рис. 6.2-12. Схема алгоритма и программный код процедуры Рг6212(), которая вычисляет сумму чисел Фибоначчи, не превосходящих заданного натурального числа Ш Примера 6.2-5

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

Пример обращения к процедуре Рг6212()

Рис. 6.2-13. Пример обращения к процедуре Рг6212()

Пример 6.2-6. Написать процедуру-Function, которая вычисляет с точностью ?=0.001 сумму членов ряда

Очевидно, что задана знакопеременная убывающая последовательность, поэтому для вычисления суммы ряда с точностью ? будем вычислять и суммировать члены последовательности до тех пор, пока очередной член ряда не станет меньше точности по модулю.

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

член последовательности можно представить как , где z- множитель, равный 1 или -1 (знак члена ряда); п - первый сомножитель в числителе каждого слагаемого (в данном случае совпадает с номером члена ряда); b - второй сомножитель в числителе; с- знаменатель каждого слагаемого.

В свою очередь, знаменатель члена ряда представляет собой произведение нескольких сомножителей, причем с увеличением номера члена ряда увеличивается и количество сомножителей в знаменателе. Таким образом, знаменатель можно представить как C=C*d, где d - сомножитель, добавленный к значению знаменателя предыдущего члена ряда.

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

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

Схема алгоритма и программный код процедуры Рг6214(), которая вычисляет с точностью ?=0.001 сумму членов заданного ряда Примера 6.2-6

Рис. 6.2-14. Схема алгоритма и программный код процедуры Рг6214(), которая вычисляет с точностью ?=0.001 сумму членов заданного ряда Примера 6.2-6

Пример обращения к процедуре Рг6214( )

Рис. 6.2-15. Пример обращения к процедуре Рг6214( )

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>