Документ: Основы алгоритмизации вычислительных процессов. методические указания по курсу «Информатика» для студентов I-го курса всех специальностей. Авдеев В.П., Венгерова Г.Т, страницы 26-30

26

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

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

Пример 2. Составить алгоритм для вычисления суммы членов беско-

нечного ряда	y =1 +	x	+	x2	+	x3	+...
		2!
			3!		4!

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

чения погрешности ε.

Решение.

Блок-схема алгоритма приведена на рис 4.8. В начале алго-

Начало

ритма должны быть введены величины

х и ε

(блок 1). На рис 4.8 приняты обо-

значения: u - очередной член ряда, n -

1

x, ε

номер этого слагаемого. При n=1 будет

u=1, а любому значению n будет соот-

2

п = 1

ветствовать член

ряда

x

n

. Теперь

(n +

1)!

3

и= 1

можно записать соотношения, связы-

вающие все последующие значения ве-

4

у= 1

личин

u =

u x

,

y = y +u,

n = n +1.

n +1

5

x

Так как в начале вычисления n=1, u=1,

u = u

y=1, то эти значения должны быть при-

n +1

своены указанным переменным (блоки

6

у= у + и

2, 3, 4). Поскольку вначале n=1, то сле-

дующий член ряда равен u =

x

, а сумма

7

2

п= п + 1

x

y =1 +

(блоки 5, 6). После вычисле-

да

8

2

и ≥ ε

ния суммы двух слагаемых нужно уве-

нет

личить номер n на единицу

(блок 7) и

9

проверить условие |u| ≥ ε (блок 8). Если

y

это условие выполняется, то необходи-

мо вычислить следующий член ряда и

Конец

добавить

к ранее полученной сумме,

т. е. повторить операции в блоках 5,6,7.

Рис.4.8

27

Этот цикл вычислений должен повторятся до тех пор, пока u не станет меньше ε. После этого значение y должно быть выведено на печать (блок 9), и вычисления завершаются.

Пример 3. Составить блок-схему вычисления sin x для задаваемых х и ε, используя разложение sin x в ряд Тейлора:

sin x = y = x −	x3	+	x5	−	x7	+ +(−1)n+1	x2n−1	+
							(2n −1)!
3!		5!		7!

с точностью очередного члена ряда	x2n−1	<ε, где n=1, 2, 3,…
	(2n −1)!

		Начало
	1
		x, ε
	2
	и = х	у = х	п = 1
	3	−ux2
	u =	−ux2
		2n( 2n +1)
	4
		у = у + и
	5
	n = п + 1
да	6	\|и\| > ε
		\|и\| > ε
	7	нет
	7
		y
		Конец
		Рис.4.9

Решение. Для сокращения объема вычислений при алгоритмизации подобных вычислительных процессов используется следующая общая методика, которую приведем в применении к рассматриваемой задаче. Для получения рекуррентной формулы запишем выражения для n-ого и (n+1)-ого членов записанного ряда:

un =( −1)n+1			x2n−1		;
un =( −1)n+1					;
		( 2n −1)!
un+1 = (−1)n+2			x2n+1			.
un+1 = (−1)n+2			(2n +1)!			.
			(2n +1)!
Отношение	un+1	= −	x	2			позволя-
Отношение	un	= −	2n(2n +1)				позволя-
	un		2n(2n +1)

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

u		= u		− x2	.
	n+1		n	2n(2n +1)

Алгоритм вычисления sin x представлен блок-схемой на рис. 4.9. В блоке 2 задаются: начальное значение члена ряда u=x, начальная сумма ряда y=x и начальный индекс n=1.

Вблоке 3 вычисляется очередной член ряда в соответствии с рекуррентной формулой.

Вблоке 4 происходит увеличение суммы ряда y на величину следующего члена.

28

Вблоке 5 производится увеличение индекса n на 1 для перехода к следующему члену ряда.

Вблоке 6 проверяется окончание цикла: если очередной член ряда дос-

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

Пример 4. Шар катится к краю горизонтальной полки со скоростью V, затем падает с высоты H на пол с твердым покрытием и, многократно ударяясь об пол и отскакивая, продолжает изменять свое положение в горизонтальном направлении (рис.4.10)

			Рис.4.10
Построить блок-схему алгоритма, имитирующего этот физический процесс.
Высоты подъема шара изменяются по закону убывающей геометрической
прогрессии	с заданным знаменателем Q. Требуется определить, пренебрегая
изменением горизонтальной составляющей скорости шара V, расстояние по
горизонтали от точки, в которой началось падение шара, до точки удара, по-
сле которого высота подъема шара составляет менее 10% от первоначальной,
и общее число ударов шара к этому моменту.
Решение. Если известна высота H подъема шара, то может быть получено и
Начало				время Т свободного падения:
Начало					2H ,
1				T =	2H ,		где	g-	ускорение
H, V, Q						g
H, V, Q				свободного падения.
				свободного падения.
2				Время		подъема		шара		после
H1 = H/10				удара равно времени после-
N = O				дующего падения. Следова-
S = V	2H			тельно, расстояние по горизон-
	g			тали, которое шар проходит
3				между			ударами,			равно
N = N + 1				2V		2H .
H = Q H				2V		2H .
			5			g
			5	В рассматриваемом					процессе
4			S = S + 2V 2H	В рассматриваемом					процессе
H < H1		нет	S = S + 2V 2H	повторяется один и тот же на-
	да	нет	g	бор	событий: удар				шара об
6				бор	событий: удар				шара об
				пол, подъем, падение. В опыте

N, S
N, S				изменяются некоторые						физи-
				ческие характеристики: поло-
Конец				жение шара, его энергия. Суть
Рис.4.1.1				моделирования				процесса
Рис.4.1.1

29

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

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

Составим перечень необходимых переменных:

Q - знаменатель геометрической прогрессии, по которой изменяется высота подъема шара. Q зависит от упругих свойств материалов поверхности

ишара;

Н - изменяющаяся высота подъема шара (амплитудные значения); Н1 - высота, равная 10% от первоначальной высоты;

V - заданная горизонтальная составляющая скорости шара;

S - нарастающее расстояние по горизонтали от точки начала падения; N - нарастающее число ударов шара.

Блок-схема алгоритма представлена на рис.4.11. В алгоритме используется итерационный цикл для накопления значений N и S. В нем многократно используется инструкция H=Q H (блок 3), в результате чего последовательные значения Н образуют убывающую геометрическую прогрессию.

Первое падение шара учитывается до цикла в блоке 2

S =V	2H	.

	g

Цикл оканчивается по выполнению условия H<H1.

Контрольные вопросы и упражнения

1.Дать определение итерационного вычислительного процесса.

2.Какой метод используется при алгоритмизации итерационных процессов?

3.Какова идея метода итерации?

4.Какая величина управляет итерационным циклом?

5.Почему при составлении алгоритмов с итерационными циклами нельзя использовать блок модификации?

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

7.Поясните смысл рекуррентной формулы.

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

9.Составить блок-схему алгоритма вычисления корня k-й степени уравнения y = k x по итерационной формуле


		1				x
yn+1 =		1	( K −1)yn		+	x	.
yn+1 =			( K −1)yn		+	k −1	.
		K				yn
Погрешность вычислений	yn+1 − yn			<ε ; начальное приближение yn=y0.
Погрешность вычислений	yn+1 − yn			<ε ; начальное приближение yn=y0.

30

10.Используя формулу предыдущего задания, составить блок-схему алго-

ритма вычисления y = 3 72 с точностью 10- 4 при y0=1.

11.Составить блок-схему алгоритма нахождения приближенного значения

корня			уравнения		x =		1	по итерационной формуле
						2	+sin x
			1
xi+1	=			при х0 = 0 с точностью 10-2.
		2	+sin xi

12.Составить блок-схему алгоритма определения наименьшего целого

K>0, при котором вычисленное значение функции у = xk становится

K

меньше a. Определить условия, при которых задача имеет решение. 13.Составить блок-схему определения для заданного х значения cosx по

формуле cos x = y =1− x2 + x4 − x6 + с точностью очередного чле- 2! 4! 6!

x2n < ε

на ряда ( ) . 2n !

14.Исходя из представления arctg x знакопеременным степенным рядом

arctgx = y =

π

−

1

+

1

−

1

+

1

−

(x>1), построить алгоритм,

2

x

3x3

5x7

7xx

приближенно вычисляющий значения arctg x с точностью ε . 15. Вычислить сумму членов ряда

z =	1	+	mx	+	m( m −1)	x2	+	m( m −1)( m − 2 )	x3	+
			( m +1)!
	m!				( m + 2 )!			( m +3 )!

с точностью ε. Для определения текущего значения члена ряда использовать рекуррентную формулу

Un+1 =Un	x(m −n +1)	, n - номер члена ряда.
	m + n

16. Получить рекуррентную формулу и вычислить сумму членов ряда

y =	1		+	2	+ +	n	+ с точностью ε.
	2	3		3 4		(n +1)(n + 2)

17. Начертить блок-схему алгоритма вычисления f(x) с заданной точно-

стью ε :

а)

f (x) = x −

x3

+

x

5

−

x

7

+ ;

3!

3

5!

5

7! 7

∞

x

i

б)

f (x) = ∑(−1)i −1

;

i =1

i

в)

∞

+1)(−x)i

;

f (x)= ∑(i

i=0

Смотрите также: