Глава 2. Проектирование алгоритмов простой структуры - 2.3. Алгоритмы, использующие итерационный цикл

E-mail Печать PDF
Рейтинг пользователей: / 1
ХудшийЛучший 
Индекс материала
Глава 2. Проектирование алгоритмов простой структуры
2.2. Алгоритмы, использующие арифметический цикл
2.3. Алгоритмы, использующие итерационный цикл
Задачи для самостоятельного решения
Все страницы

2.3. Алгоритмы, использующие итерационный цикл

Пример 2.10. Даны действительные числа x, e (x ? 0, e > 0). Вычислить с точностью e:

.

Математическая модель. Выведем рекуррентное соотношение, используя способ,  показанный в примере 2.8. Пусть с - слагаемое, S - сумма

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

Для вычисления факториала числа можно воспользоваться формулой p = p ? k, которую мы вывели ранее. Начальное значение p = 1. Проверьте правильность этой формулы, последовательно вычисляя значение k!

Выведем общую формулу для вычисления  слагаемого.

k = 0,     с = x0/ 20 = 1;

k = 1,     с = x1/ 21 = x/ 2;

k = 2,     с = x2/ 22 = (x/ 2) ? (x/ 2) = с ?x/ 2;

k = 3,     с = x3/ 23 = (x2/ 4) (x/ 2) = с ?x/ 2;

k = 4,     с = x4/ 24 = (x3/ 8) (x/ 2) = с ?x/ 2.

Обобщая, для произвольного значения k можно записать такую формулу: c = с ?x/2, где значение переменной с в правой части формулы вычисляется на предыдущем шаге. Начальное значение с =1 при k = 0.

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

Переменная k - целого типа, переменные x, e, c, S - вещественного типа. Переменную p следует взять вещественного типа, т.к. диапазон целых чисел ограничен, а факториал быстро возрастает с ростом значения k.

Решение

Ввод x, e

p = 1,  c = 1, S =1

k =1

Пока с/k > e повторять

нц

    с = с * x/2

    S = S + c/p

    k = k + 1

кц

Вывод S

Пример 2.11. Вычислить сумму элементов знакочередующегося степенного ряда с точностью e:

S = 1 - x/1! + x2/2! - x3/3! + ... + (-1)nxn/n!

Дано: x, e - переменные вещественного типа.

Найти S с заданной точностью e.

Математическая модель. Выведем рекуррентное соотношение. Формулировка задачи предполагает, что элементы последовательности суммируются, пока очередное слагаемое больше заданной точности вычислений. Как только слагаемое станет меньше точности вычислений, суммирование прекращается.

Сумма вычисляется по формуле: сумма = сумма + слагаемое. Определим общий вид слагаемого. Обозначим Р1 - слагаемое, Р - числитель, а F - знаменатель члена последовательности. Мы уже рассматривали алгоритмы нахождения произведения и факториала. Используем их для заполнения таблицы.

n

P

F

P1

1

P = -x

F = 1! = 1

P1 = -P/F

2

P = x2 = x ? x = P ?x

F = 2!= 1! ? 2 = F ? n

P1 = -(P ? x)/(F ? n) = -P1 ? x/n

3

P = -x3 = x2? x = -P ? x

F = 3!= 2! ? 3 = F ? n

P1 = -(P ? x)/(F ? n) = -P1 ? x/n

4

P = x4 = x3? x = P ? x

F = 4!= 3! ? 4 = F ? n

P1 = -(P ? x)/(F ? n) = -P1 ? x/n

Из таблицы видно, что на каждом шаге вычислений значение элемента последовательности, вычисленное на предыдущем шаге, умножается на дробь x/n.

Итак, общий элемент последовательности с учетом знака определяется по формуле Р1 = -P1 ? x/n.

Исходя из условий задачи, определим начальные значения переменных следующим образом: S = 1, P1 = 1.

Так как элемент последовательности Р1 является знакопеременным, то при проверке условия в заголовке цикла используем функцию abs(), вычисляющую модуль числа.

 

Посмотрим, как работает алгоритм при x = 1, e = 0,01.

 

Условие

P1

S

n

Abs(1)>0,01? Да

-1 ? 1 = -1

1 + (-1) = 0

2

Abs(-1)>0,01? Да

-(-1 ? 1/2) = 0,5

0 + 0,5) = 0,5

3

Abs(0,5)>0,01? Да

-0,5 ? 1/3 = -0,666

0,5 + (-0,666) = -0,1666

4

Abs(-0,666)>0,01? Да

-(-0,666?1/4) = 0,166

-0,166 + 0,166 = 0

5

Abs(0,166)>0,01? Да

-0,166 ?1/5 = -0,044

0 + (-0,033) = -0,033

6

Abs(-0,033)>0,01? Нет

 

 

 

Итак, S = -0,033 при заданном значении х и точности вычислений 0,01.

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



 

Добавьтe Ваш комментарий

Ваше имя (псевдоним):
Ваш адрес почты:
Заголовок:
Комментарий:

Комментарии

Интересное




Похожие материалы

Партнёры