Иванова Г.С. - Основы программирования

3. Управляющие операторы языка

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

Поскольку количество повторе­ ний цикла определить нельзя, попро­ буем преобразовать неструктурный цикл к циклу-пока. Для этого необ­ ходимо операцию S=S+R продубли­ ровать: одну копию поместить до цикла, а вторую ~ в конце цикла. Операторы S=0 и S=S+R, записан­ ные до цикла, заменим оператором S=l, так как в этот момент R=l. Ус­ ловие выхода из цикла также необхо­ димо заменить на противоположное. Окончательный вариант фрагмента алгоритма с ц и к л о м - п о к а показан на рис. 3.14, а. Его реализа­ ция представлена ниже:

	Program ex;	Рис. 3.13. Алгоритм определения
	Var S,R,X,eps:real;
		суммы ряда с заданной точностью
	Begin
	WriteLnCВведите x и эпсилон: *);
	ReadLn(X,eps);
	ifabs(x)>l then	{если x > 1, то ищем сумму ряда}
	begin

S:=l;

R:=I;

while abs(R)>eps do begin

R:='R/X;

S:=S+R;

end;

61

Часть I. Основы алгоритмизации и процедурное программирование

Рис. 3.14. Структурные варианты алгоритма:

а-с использованием цикла-пока; б - с использованием цикла-до

WriteLnCnpu х= \ х:6:2,' S= \ 3:8:2, \ а /?=', R:8:6) end

else Writeln('PHdрасходится*); End.

Тот же алгоритм можно преобразовать так, чтобы цикл можно было реализовать с использованием ц и к л а - д о (рис. 3.14, б). Ниже представле­ на соответствующая программа.

Program ex;

var S,R,X,eps:real; Begin

WriteLnCВведите значение x и эпсилон:'); ReadLn(X,eps);

ifx>l then begin

S:=0; R:-l; repeat

S:=S+R;

R:='R/X

until abs(R ^^x) < =eps;

WriteLnCnpu x= \x:6:2,' S= \S:8:2, \ a /?= \R:8:6) end

62

i. Управляющие операторы языка

else Writeln(THd расходится'); End,

Другие способы реализации неструктурных алгоритмов более подробно будут рассмотрены в параграфе 3.4.

3.5. Практикум. Точность решения задач вычислительной математики

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

Пример 3.6. Разработать программу вычисления определенного интег­ рала функции f(x) на заданном отрезке [а, Ь] методом прямоугольников.

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

нием которых является п-я часть отрезка [а,Ь], а стороной -			значение функ­
ции на одном из концов отрезка (например, левом, как на рис. 3.15).
Итак
Sl= f(xi)x5 + f(x2)x6 + f(x3)x5 + ...+ f(x„)x5 = 5xZ f(xi),
		i = l
где 5 = (b-a) / n.
Значение определенного интеграла SI,
определенное по данной формуле, является не
точным, причем с увеличением количества от­
резков п точность значения S1 увеличивается.
Считают, что значение определено с заданной
точностью, если абсолютная величина разно­
сти двух последовательных приближений ре­		О а	b X
зультата, полученных при разных значениях		п=6
п, не превышает заданной погрешности.		Рис. 3.15. Вычисление
Для определения момента	достижения	определенного интеграла
заданной точности необходимо	организовать	методом прямоугольника

63

Часть L Основы алгоритмизации и процедурное программирование

(	Начало	j	©
/	Ввод	у/	S1:=0
/	a,b,eps	/
	Sl:=10''		r^i:=l,n,lVn
	n:=5
	S2:=S1
	n:=2n
	1

d:=(b-a)/n

x:=a

^

Рис. 3.16. Схема алгоритма вычисления определенного интеграла

еще один - внешний цикл, в котором значение п будем увеличивать, напри­ мер, в два раза, и рассчитывать значение S1, предварительно сохранив пре­ дыдущее значение S1 в переменной S2. Цикл должен завершаться, когда аб­ солютная величина разности двух приближений S1 и S2 станет меньше s. Ис­ ходное значение S2 примем достаточно большим, чтобы цикл не завершился при лервой проверке условия.

Схема алгоритма вычисления определенного интеграла для функции f(x) = х^ - 1 приведена на рис. 3.16.

Ниже приведена программа, реализующая данную схему алгоритма.

Program ex;

Var а, b,Sl,S2,d, eps,x:real:n, i.'longint; Begin

WriteLnCВведите a, b и эпсилон:'); ReadLnfa, b, eps);

S1:=1E+10;

n:=5;

64

3. Управляющие операторы языка

repeat S2-S1; п:=п*2; d:^(b'a)/n; х:=а; S1-0;

for i:=l to п do begin

S]:=SI+x*X'l;

x:=x+d;

end;

SJ:=SJ*d;

until abs(Sl-S2)<eps: WriteLnCI=\Sl:10:6);

End

При выполнении программы с разными значениями погрешности eps и отрезком [0,2] получаем разные приближения результата I (табл. 3.2). Точное значение определенного интеграла равно 2/3. Определим абсолютную и от­ носительную погрешности результата.

В данном случае абсолютная погрешность результата всегда будет меньше eps, так как это определяется самим методом. Последнее верно не для любого метода.

Пример 3.7. Разработать программу, которая определяет корень непре­ рывной функции f(x) на заданном отрезке [а, Ь] методом хорд.

Метод работает в том случае, если значения функции на концах отрезка разных знаков, т.е. если функция только касается оси абсцисс, то ее корень данным методом определить нельзя. Если на заданном отрезке у функции не­ сколько корней, то, используя данный метод, найдем один из них.

Метод хорд заключается в следующем. Значения функции на концах от­ резка соединяют отрезком прямой. В точке пересечения этой прямой с осью абсцисс определяют значение функции. Если это значение меньше заданной

погрешности	функции, то	абсцисса точки	пересечения	считается корнем
				Т а б л и ц а	3.2
eps	п	I	Al	5i,%
0.01	640	0.660420	0.006	0.9	1
0.001	5120	0.665885	0.0002	0.06
0.0001	40960	0.666569	0.00004	0.012

65

Часть 1. Основы алгоритмизации и процедурное программирование

Рис. 3.17. Нахождение корня методом хорд

Г Начало j

/ Ввод У

/a,b,eps /

fa:=a*a-l fb:=b*b-l

-^^2-<fa*fb>0 нет

' "Метод не7 применим

функции, иначе корень функции ищется на том отрезке из двух полу­ ченных, для которого значения функции на концах разных знаков. На рис. 3.17 показана графическая интерпретация метода.

На рис. 3.18 представлена схе­ ма алгоритма программы для функ­ ции f(x) = х^ - 1.

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

( Конец j

Рис. 3.18. Схема алгоритма нахождения корня методом хорд

66

Часть L Основы алгоритмизации и процедурное программирование

Рис. 3.19. Соотношение Лу и А^ в зависимости от вида функции:

а ~ угол наклона производной в корне больше 45**; б - меньше 45**

функции. Однако, если бы производная функции в точке корня была близка к нулю, это соотношение было бы обратным (рис. 3.19), и, следовательно, метод оказался бы неприменимым.

В качестве альтернативы можно предложить алгоритм, в котором выход из цикла вычислений выполняется, когда разность между двумя соседними приближениями значений корня становится меньше заданного eps (по анало­ гии с примером 3.6). Однако этот алгоритм был бы не применим для поиска корня, если угол наклона производной функции в корне больше 45°.

Следовательно, применяя тот или иной методы вычислительной матема­ тики, необходимо проверять обеспечение точности получаемых результатов.

Задания для самопроверки

Задание 1. Разработайте программу вычисления

arctg X = X - х^/З + х5/5 - х^/7 + ...

при заданном значении х и точности 10*^, 10"^. Оцените количество итераций в каждом случае.

Задание 2. Разработайте программу, которая определяет сумму первых к чисел последовательности Фибоначчи. Последовательность задана законом

F, = l,

Fn = F.п-1 + F,п-2

для п > 2.

Задание 3. Разработайте программу вычисления длины кривой на отрезке [0,4]. Кривая задана уравнением у=х^^. Вычисления выполните с точностью 10'^, Ю""*. Оцените количество итераций в каждом случае.

Задание 4. Разработайте программу, которая определяет, является ли введенное

число п простым.	__,	,,
Задание 5. Разработайте программу вычисления:

68

3, Управляющие операторы языка

ем, рассмотренный в примере 3.3. А именно: повторяем в конце тела цикла операторы, выполняемые в начале цикла до условия, и организуем цикл, как цикл-пока. Поскольку выход из цикла-пока осуществляется по нарушению условия цикла, придется также изменить условие цикла. Программа, реали­ зующая структурный вариант алгоритма, имеет следующий вид:

Program ex;

Var a,bjjajb,eps,x:real; Begin

WriteLnCBeedume a, b и эпсилон: *); ReadLn(a, b, eps);

fa:^a*a-l; Jb:^b''b'l;

iffa*fb>-0 then WriteLn(*Метод не пргшеним. *) else

begin

x:=(b'a) *abs(fa)/abs(fa'fb)+a;

while abs(f)>-eps do {условие выхода из цикла} begin

iffaj<0 then

begin b:=x; Jb:=f; end else begin a:=x; fa:=f; end; х:-(Ыа) *abs(fa)/abs(fa'fb)'^a; f:-x*x-l;

end;

WriteLnCnpu x= \ x:9:6, ' y= \ f:10:8); end;

End

Меняя значение погрешности, получим разные значения корня и значе­ ния функции в корне (табл. 3.3). Зная точное значение корня х=1, определим предельную абсолютную и относительную погрешности в каждом случае. Из таблицы видно, что погрешность корня меньше погрешности значения

				Таблица 3.3
eps = Ay	X	У	Ах	5х, %
0.01	0.997260	-0.00547195	0.003	0.3
0.001	0.999695	-0.00060948	0.00031	0.03
0.0001	0.999966	-0.00006774	0.000034	0.003

67

3, Управляющие операторы языка

3.6.Неструктурные алгоритмы и их реализация

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

Для организации неструктурных передач управления используют опера­ тор безусловной передачи управления goto и специальные процедуры.

Оператор безусловной передачи управления. Этот оператор передает управление в точку, определенную специальной меткой (рис. 3.20).

Все метки в программе должны быть описаны инструкцией объявления меток label (рис. 3.21). Метка ставится перед любым выполняемым операто­ ром программы, причем на один оператор можно поставить несколько меток.

Неструктурную передачу управления таюке осуществляют следующие процедуры:

Break - реализует выход из цикла любого типа;

Continue - осуществляет переход на следующую итерацию цикла, игнорируя оставшиеся до конца тела цикла операторы;

Halt (<код, завершения>) - осуществляет выход из программы, возвра­ щая операционной системе заданный код завершения. Считается, что про­ грамма завершилась нормально, если код завершения равен нулю. Возвраще­ ние кода завершения, отличного от нуля, обычно означает,что программа за­ вершена по обнаружении каких-либо ошибок. Коды завершения назначают­ ся программистом, а информация о них помещается в программную доку­ ментацию;

Exit- осуществляет выход из подпрограммы (см. главу 5). Если проце­ дура использована в основной программе, то она выполняется аналогично

	Halt.			о
		-*/^ label Л - j	Целое
	-*/ goto V-H Метка		без знака
			J Идентификатор
			метки
	Рис. 3.20. Синтаксичеркая		о
	диаграмма <Оператор
	безусловной передачи	Рис. 3.21. Синтаксическая диаграмма
	управления>	<Объявление меток>

69

Часть 1. Основы алгоритмизации и процедурное программирование

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

Пример 3.8. Разработать программу, которая определяет первый отри­ цательный элемент последовательности значений функции sin х при задан­ ных п, шаге h и диапазоне изменения х [а, Ь].

Для получения требуемого результата необходимо последовательно вы­ числять значение функции и анализировать его знак. Количество элементов последовательности на задан­

(	Начало	J					ном отрезке и с заданным ша­
/	Ввод	7					гом можно определить, следо­
							вательно, для вычисления зна­
/	a,b,h	/					чений функции	можно ис­
	n:=(b-a)/h+l						пользовать счетный цикл. Для
							конкретных вариантов исход­
	х:=а
							ных данных может оказаться,
гК^1:=1,пл\-							что такого элемента в задан­
							ной последовательности нет.
							Следовательно,	после завер­
	y:=sin(x)						шения цикла необходимо вы­
							вести соответствующее сооб­
		да					щение. Неструктурный вари­
	у <0						ант алгоритма решения задачи
	нет						показан на рис. 3.22.
			Вывод		/		Без преобразований этот
	x:=x+h
		/					вариант алгоритма можно реа­
	IZZJ			break			лизовать только с использова­
			goto		Элемент		нием оператора goto, так как
							он позволяет передать управ­
				гне найден
							ление в любое место програм­
				/ ж	1Г	7	мы, а процедура break - толь­
(	Конец	)					ко оператору, следующему по­
							сле цикла (пунктир на рис.
							3.22). Поэтому реализация с
Рис. 3.22. Схема алгоритма поиска первого							использованием	break потре­
отрицательного элемента последовательности							бует дополнительной провер­
(пунктиром выделен поисковый цикл)							ки (найден ли элемен) на вы-

70