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

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

1. определяются действия, составляющие тело цикла;

2. заполняется блок подготовки итерации;

3. определяется условие выхода из цикла (счетчик или логическое выражение);

4. заполняется блок подготовки цикла.

Пример 2.1. Задано натуральное число a. Получить все члены последовательности a, a², a³, …, не превышающие числа b.

Схема алгоритма решения этой задачи представлена на рисунке 2.2.

Рисунок 2.2 – Схема алгоритма получения последовательности

При подготовке цикла присваивается начальное значение вспомогательной переменной с. Тело цикла включает последовательное вычисление переменной c, которая равна a, a², a³, … Изменение значения с происходит до тех пор, пока оно не станет больше или равно значению b. Если a  b, то не будет выведено не одного элемента последовательности.

2Табулирование функции

Типичным примером циклического процесса с заданным числом повторений является задача табулирования функции (получение таблицы значений функции).

Задача сводится к вычислению значений функции y = f(x) при изменении x от начального значения a до конечного значения b с постоянным шагом h. Такая программа реализуется посредством цикла с заданным числом повторений, причем число повторений определяется по формуле:

Решение задачи можно осуществить с помощью алгоритма, схема которого приведена на рисунке 2.3.

Рисунок 2.3 – Схема алгоритма вычисления значений функции

Здесь при подготовке цикла вычисляется количество его повторений и присваивается начальное значение переменной x. В теле цикла рассчитывается значение функции в точке x и, затем, выводится значение x и y. При подготовке итерации изменяется значение x.

3Нахождение суммы ряда

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

Условие окончания цикла зависит от поставленной задачи, как правило, оно связано с достижением требуемой точности.

Примеры постановок задач.

1. Найти сумму первых n членов ряда . В этом случае условие выхода из цикла: i > n.

2. Вычислять сумму ряда до тех пор, пока очередной член ряда r_i не будет меньше заданного . Здесь условием выхода из цикла будет: | r_i | < .

3. Вычислить сумму ряда с точностью , если известно точное значение суммы, равное A. Здесь условие выхода из цикла: | S - A | < .

Рисунок 2.4 – Обобщенная схема алгоритма вычисление суммы ряда

Очередной член ряда вычисляют одним из следующих способов:

• в простейших случаях – по общей формуле, например:

1) , ;

2) , ;

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

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

1) , ;

2) , ;

• если член ряда удобно представить в виде произведения, один из сомножителей вычисляется по рекуррентному соотношению (т.е. по предыдущему члену), второй – непосредственно, например:

, .

4Приближенное вычисление определенных интегралов

Пусть требуется вычислить определенный интеграл , где f(x) – некоторая непрерывная функция, заданная на промежутке [a, b]. Как известно, значение определенного интеграла равно площади криволинейной трапеции, ограниченной подынтегральной функцией. Простейшими методами приближенного вычисления определенных интегралов являются метод прямоугольников и метод трапеций.

4.1Метод прямоугольников

Разобьем отрезок [a,b] точками a=x₀ < x₁ < x₂ <... < x_n-1 <x_n=b, причем |x_i, x_i+1|=(b-a)/n. Заменим площадь каждой криволинейной трапеции с основанием [x_i, x_i+1] площадью прямоугольника со сторонами (b-a)/n и f(x_i) (см. рисунок 2.5).

Рисунок 2.5 – Метод прямоугольников

Тогда площадь каждого такого прямоугольника вычисляется по формуле: S_i=f(x_i)(b - a)/n. Сумма всех площадей полученных прямоугольников приближенно равна значению определенного интеграла:

.

Очевидно, что чем больше количество отрезков разбиения, тем выше точность вычислений.

Пример схемы алгоритма вычисления определенного интеграла методом прямоугольников приведен на рисунке 2.6.

В этом алгоритме через N обозначено количество точек разбиения, d – длина отрезков разбиения. Тело цикла алгоритма содержит внутренний цикл с заданным числом повторений. Число повторений внутреннего цикла представляет собой количество прямоугольников, на которые мы разбили криволинейную трапецию. После отработки внутреннего цикла проверяется условие точности вычисления. Если точность недостаточна, то количество отрезков разбиения увеличивается (например, удваивается) и вычисления площади повторяются вновь.

Рисунок 2.6 – Схема алгоритма вычисления интеграла методом прямоугольников

Условие точности зависит от поставленной задачи. Будем пользоваться двумя способами оценки погрешности:

1. Если задано точное значение интеграла, равное I, то условием выхода из цикла будет условие | S - I | < .

2. Если не задано точное значение интеграла, то будем сравнивать сумму, полученную при последнем разбиении n, с суммой, полученной при предыдущем значении параметра n.

4.2Метод трапеций

Метод трапеций аналогичен методу прямоугольников, только здесь криволинейная трапеция заменяется не прямоугольниками, а трапециями (см. рисунок 2.7).

Рисунок 2.7 – Метод трапеций

Формула приближенного вычисления определенного интеграла методом трапеций примет вид:

или

5Определение корней уравнения

Рассмотрим уравнение f(x)=0, о котором известно, что оно имеет корень на отрезке [a, b], причем функция f(x) на этом интервале непрерывна и на концах отрезка [a, b] принимает различные знаки (т.е. f(a)f(b)<0). Излагаемые здесь методы состоят в приемах, при помощи которых находится новый интервал [a₁, b₁], такой что

a  a₁ < x₀ < b₁  b,

где x₀ корень уравнения.

5.1Метод половинного деления

Этот метод является одним из самых простых. Приближение к корню уравнения здесь осуществляется с помощью деления отрезка [a, b] пополам. В результате мы получаем новую точку c (см. рисунок 2.8).

Рисунок 2.8 – Метод половинного деления

Далее проверяется, является ли точка c корнем уравнения f(x)=0. В случае положительного ответа задача решена, в случае отрицательного мы сравниваем знак функции в точке c и, в дальнейшем, будем рассматривать тот отрезок ([a, c] или [c, b]), где функция принимает разные знаки. Новый отрезок снова делится пополам, и все действия повторяются вновь. Таким образом, длина рабочего отрезка будет постоянно уменьшаться, а искомый корень уравнения будет оставаться внутри этого отрезка. Вычисления прекращаются тогда, когда будет достигнута заданная точность вычислений  (т.е. |f(с)|< ).

5.2Метод хорд

Метод хорд аналогичен методу половинного деления, но дает более быстрое приближение к корню уравнения. Здесь новая точка выбирается по несколько другому закону. Точки с координатами (a, f(a)) и (b, f(b)) соединяются отрезком (хордой) и точка c выбирается как точка пересечения полученной хорды с осью OX(см. рисунок 2.9.)

Рисунок 2.9 – Метод хорд

Координату точки c находят по формуле:

или

6Нахождение длины кривой

Пусть на отрезке [a,b] уравнением y=f(x) задана непрерывная кривая. Нужно найти длину, заданной кривой. Задачу можно решить, если разбить отрезок [a,b] на несколько частей, см. рисунок 2.10.

Рисунок 2.10 – Метод хорд нахождения длины кривой

Если теперь провести прямые, параллельные оси OY, то кривая будет разбита на такое же количество более мелких кривых. Соединив точки разбиения кривой прямым линиями, получим ломаную, длину которой определить не представляет большого труда, поскольку каждая вершина имеет координаты (x_i, f(x)). Очевидно, что чем больше звеньев у ломанной, тем ближе ее длина к длине кривой. Поэтому алгоритм вычисления можно построить следующим образом: нужно увеличивать количество точек разбиения и вычислять длину ломанной до тех пор, пока не будет достигнута требуемая точность.

1. Массивы

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

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

1. Последовательная обработка элементов массива.

2. Выборочная обработка элементов массива.

3. Изменение порядка следования элементов без изменения размеров исходного массива.

4. Переформирование массива с изменением его размеров.

5. Одновременная обработка нескольких массивов или подмассивов.

6. Поиск в массиве единственного элемента, отвечающего некоторому условию.

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

7Приемы обработки одномерных массивов

Одномерными называют массивы, для доступа к элементам которых необходимо задавать один индекс. Рассмотрим наиболее распространенные приемы программирования обработки одномерных массивов.

7.1Последовательная обработка элементов массива

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