12.2 Итерационные циклы

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

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

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

Пример 12.1. Вычислить значение функции Sin(Х) по приближенной формуле F=sin(X) = X - X³/3! + X⁵/5! - … с погрешностью Е = 10^-5.

Функция F представляет собой сумму членов степенного ряда: F = U1 + U2 + ... + Un . Условие окончания вычисления функции F : |Un – Un+1 | ≤ E, где Un – общий член ряда; Un+1 – следующее слагаемое. Un+1 через Un можно определить как:

Схема алгоритма задачи приведена на рис.12.4.

Рисунок 12.4 – Алгоритм решение задачи итерационных циклов

Индивидуальные задания

Написать алгоритм решения задачи, используя рекурсию.

1. Описать рекурсивный алгоритм для вычисления n!.

2. Описать рекурсивный алгоритм для вычисления xⁿ.

3. Описать рекурсивный алгоритм pow(x,n) от вещественного x (x≠0) и целого n, которая вычисляет величину xⁿ согласно формуле

4. Рекурсивно найдите максимальный элемент в одномерном массиве.

5. Используя рекурсивный алгоритм, найти n-ый член последовательности

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

7. Используя рекурсию, найти максимальный элемент из n членов последовательности, вводимых с клавиатуры.

8. Используя рекурсию, найти максимальный элемент из первых n членов последовательности

9. Используя рекурсию, вывести первые n членов последовательности , которые больше m.

10. Используя рекурсию, распечатать номера первых n членов последовательности x_n=2*x_n-3+3*x_n-1-4, x₀=2, x₁=0, x₂=1,, которые больше m.

11. Составьте алгоритм вычисления суммы .

12. Определите n–й член последовательности, в которой каждый следующий член равен сумме всех предыдущих.

Контрольные вопросы

1) На чем основан рекурсивный метод программирования?

2) В чем разница между «циклическим» и «рекурсивным» способами определения? Какой элемент является обязательным в рекурсивном определении?

4) К чему приводит «рекурсивное зацикливание»?

5) Какое условие должно обязательно присутствовать в любой рекурсивной процедуре?

6) Что такое явная и косвенная рекурсии?

Лабораторная работа № 13 Тема: «Исследование основных алгоритмов сортировок»

Цель работы – изучить принцип построения алгоритмов сортировок.

Теоретические сведения