Семакин И.Г., Шестаков А.П. Основы программирования

Подождите немного. Документ загружается.

лить на нем понятия «следующий», «предыдущий». Однако рас-

стояние между двумя последовательными значениями на этом

множестве оказывается величиной субъективной, в частности,

зависящей от размера ячейки памяти, в которой хранится число.

Например, если под мантиссу выделяется 3 байта, то следующее

значение получается путем прибавления к мантиссе единицы в

24-м разряде; если 5 байт — единицы в 40-м разряде.

Бесконечное количество действительных чисел вообще непред-

ставимо точно в памяти ЭВМ. Если вещественное значение

Xпо-

падает между двумя точно представимыми значениями

г,-

и /•,+,, то

оно заменяется на значение меньшего по модулю из этой пары

чисел (некоторые типы процессоров выполняют «правильное»

округление). Следовательно, в общем случае вещественные числа

хранятся в памяти приближенно, т.е. несут в себе погрешность,

которая называется

погрешностью машинного

округления.

Из сказанного следует, что если два числа X и Уудовлетворяют

условиям r,< X< r

; r,< Y< /*,+,, но ХФ

У,

то в машинном пред-

ставлении они неразличимы.

Разность между вещественной единицей и ближайшим к ней

числом, представимым в памяти машины, называется машинным

эпсилон е. Иначе говоря, если г,- = 1, то r

i+i

+ г. Легко понять,

что величина машинного е связана только с разрядностью ман-

тиссы в представлении вещественных чисел на данной ЭВМ.

Для определения величины машинного £ можно использовать

следующую программу:

Program Epsilon;

Var Eps:

Real;

Begin Eps:=1/2;

While 1.0+Eps>1.0 Do

Eps:=Eps/2;

WriteLn('Машинный эпсилон=',Eps)

End.

Упражнения

С помощью приведенной выше программы определите на

вашем компьютере величину машинного £.

Если на вашем компьютере это возможно, определите ма-

шинное е для удвоенной или повышенной точности представле-

ния вещественных чисел.

Составьте программу определения машинного нуля. Прове-

дите численный эксперимент на вашем компьютере.

Результат выполнения следующей программы доказывает

некорректность сравнения на равенство двух вещественных чисел.

Program Test;

Var X,StepX:

Real;

Begin X:=0;

StepX:=0.1;

Repeat

X:=X+StepX

Until X=1E3

End.

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

Попробуйте экспериментально доказать, что в «плавающей»

арифметике на ЭВМ не всегда выполняются законы ассоциативно-

сти:

(х

+ у) +

—

(у + z)

дистрибутивности: (х

+ у) •

yz.

6. Проведите эксперимент на исследование целочисленного

переполнения, т.е. установите, что происходит с целой перемен-

ной, когда ее значение превышает Maxlnt.

3.13.

Подпрограммы

С понятием вспомогательного алгоритма вы уже знакомы (см.

разд. 1.4).

языках программирования вспомогательные алгоритмы

называются

подпрограммами.

Паскале различаются две разновид-

ности подпрограмм:

процедуры

функции.

Рассмотрим этот вопрос

на примере следующей задачи: даны два натуральных числа а и Ь.

Требуется определить наибольший общий делитель трех величин:

Ь,

\а

Ь\,

а-

Ь.

Запишем это так: НОД(д

Ь,

\а-

Ь\,

•

Ь).

Идея решения состоит в следующем математическом факте:

если х, у, z — три натуральных числа, то НОД(х, у, z) =

= НОД(НОД(х, у),

z)-

Иначе говоря, нужно найти НОД двух вели-

чин, а затем НОД полученного значения и третьего числа (по-

пробуйте это доказать).

Очевидно, что вспомогательным алгоритмом для решения по-

ставленной задачи является алгоритм получения наибольшего об-

щего делителя двух чисел. Эта задача решается с помощью изве-

стного алгоритма Евклида (см. раздел 1.3). Запишем его в форме

процедуры на алгоритмическом языке.

Процедура Евклид(цел

M,N,K);

нач

пока MON

нц

если M>N

то

M:=M-N

иначе

N:=N-M

кв

кц;

К:=М

кон

Здесь

являются формальными параметрами процедуры,

параметры-аргументы, к

—

параметр-результат. Основной ал-

горитм, решающий исходную задачу, будет следующим:

алг задача;

цел а,b,с;

нач ввод(а,Ь);

Евклид(a+b, Ia-bI,с) ;

Евклид(с,а*Ь,с);

вывод(с)

кон.

Процедуры

Паскале. Основное отличие процедур в Паскале от

процедур в Алгоритмическом языке (АЯ) состоит в том, что про-

цедуры в Паскале описываются в разделе описания подпрограмм,

а в АЯ процедура является внешней по отношению к вызываю-

щей программе. Теперь посмотрим, как решение поставленной

задачи программируется на Турбо Паскале.

Program

NODI;

Var А,В,С: Integer;

Procedure Evklid(M,N: Integer; Var К:

Integer);

Begin

While MON Do

If M>N

Then M:=M-N

Else N:=N-M;

K:=M

End;

Begin

Write('a=');

ReadLn(A);

Write('b=');

ReadLn(B);

Evklid(A+B,Abs(A-B),C);

Evklid(C,A*B,C);

WriteLn('HOfl=',C)

End.

В данном примере

обмен

аргументами и результатами между

основной программой и процедурой производится через пара-

метры (формальные

фактические).

Существует и другой меха-

низм обмена

—

через глобальные переменные. Но об этом чуть

позже. А сейчас рассмотрим синтаксическую диаграмму описа-

ния процедуры (рис. 27).

Из диаграммы видно, что процедура может иметь параметры, а

может быть

без

них.

Чаще всего аргументы представляются как па-

раметры-значения (хотя могут быть и параметрами-переменными),

д для передачи результатов используются параметры-переменные.

«Описание процедуры>

—• •Оаголовок процедуры>—•^ 5

)—•<Блок>-

Оаголовок процедуры>

_— • Procedure —• <Имя процедуры>-

•> <Список формальных параметров> И ) )—'

<формальные параметры>::=<параметры-значения>

|<параметры-переменные>

<Параметры-переменые> Х~~\

• • Var-КСписок переменных»( : )-*-<Тип>—•

<Параметры-значения> /" N

• <Список переменных>—•(

)-ХТип>—•

Рис.

Процедура в качестве результата может передавать в вызываю-

щую программу множество значений (в частном случае — одно),

а может и ни одного. Теперь рассмотрим правила обращения к

процедуре. Обращение к процедуре производится в форме опера-

тора процедуры

(рис. 28).

«Эператор процедуры>

• • <Имя процедуры>

•>< Список фактических параметров> •( ) )—'

Рис.

Если описана процедура с формальными параметрами, то и об-

ращение к ней производится оператором процедуры с фактичес-

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

фактическими параметрами: соответствие по количеству, соответ-

ствие по

последовательности

и соответствие по типам.

Первый вариант взаимодействия формальных и фактических

параметров называется передачей по значению: вычисляется зна-

чение фактического параметра (выражения) и это значение при-

сваивается соответствующему формальному параметру. Второй

вариант взаимодействия называется передачей по

имени:

при вы-

полнении процедуры имя формальной переменной заменяется на

имя соответствующей фактической переменной (в откомпилиро-

ванной программе имени переменной соответствует адрес ячейки

памяти).

рассмотренном нами примере формальные параметры Ми N

являются параметрами-значениями. Это аргументы процедуры. При

обращении к ней первый раз им соответствуют значения выраже-

ний а

+ Ь

abs

(a-

b);

второй раз

—

с и а

•

Ь.

Параметр К является

параметром-переменной.

ней получается результат работы про-

цедуры.

обоих обращениях к процедуре соответствующим факти-

ческим параметром является переменная с. Через эту переменную

основная программа получает результат.

Теперь рассмотрим другой вариант программы, решающей ту

же задачу.

ней используется процедура

без

параметров.

Program

NOD2;

Var A,B,K,M,N: Integer;

Procedure Evklid;

Begin

While MON Do

If M>N

Then

M:=M-N

Else

N:=N-M;

K:=M

End;

Begin

Write('a=');

ReadLn(A);

Write('b=');

ReadLn(B);

M:=A+B;

N:=Abs(A-B);

Evklid;

M:=K;

N:=A*B;

Evklid;

WriteLn('HOfl равен',К)

End.

Чтобы разобраться в этом примере, требуется объяснить новое

для нас понятие:

область действия

описания.

Областью действия описания любого программного объекта

(переменной, типа, константы и т.д.) является тот блок, в кото-

ром расположено это описание. Если данный блок вложен в дру-

гой (подпрограмма), то присутствующие в нем описания являют-

локальными.

Они действуют только в пределах внутреннего бло-

ха. Описания же, стоящие во внешнем блоке, называются гло-

бальными по отношению к внутреннему блоку. Если глобально

описанный объект используется во внутреннем блоке, то на него

распространяется внешнее (глобальное) описание.

В программе N0D1 переменные М, N, К — локальные внутри

процедуры; переменные а, Ь, с — глобальные. Однако внутри про-

цедуры переменные а, Ь, с не используются. Связь между вне-

шним блоком и процедурой осуществляется через параметры.

В программе N0D2 все переменные являются глобальными. В

процедуре Evklid нет ни одной локальной переменной (нет и

параметров). Поэтому переменные Ми N, используемые в проце-

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

новном блоке программы. Результат получается в глобальной пе-

ременной К, значение которой выводится на экран.

Использование механизма передачи через параметры делает

процедуру более универсальной, независимой от основной про-

граммы. Однако в некоторых случаях оказывается удобнее ис-

пользовать передачу через глобальные переменные. Чаще такое

бывает с процедурами, работающими с большими объемами ин-

формации. В этой ситуации глобальное взаимодействие экономит

память ЭВМ.

Функции. Теперь выясним, что такое подпрограмма-функция.

Обычно функция используется в том случае, если результатом

подпрограммы должна быть скалярная (простая) величина. Тип

результата называется типом функции. В Турбо Паскале допуска-

ются функции строкового типа. Синтаксическая диаграмма опи-

сания функции представлена на рис. 29.

Как и у процедуры, у функции в списке формальных парамет-

ров могут присутствовать параметры-переменные и параметры-

значения. Все это аргументы функции. Параметры вообще могут

отсутствовать (если аргументы передаются глобально).

«Эписание функции>

• <Заголовок> И ; ) •<Блок>-

<Заголовок> f \

• •Function—>-<Имя функции>—i х>( : )-КТип»

( )-*<Список формальных параметров>-

Рис.

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

ванием функции будет выглядеть следующим образом:

Program N0D3;

Var А,В,Rez:Integer;

Function Evklid(M,N:Integer):Integer;

Begin

While HON Do

If M>N

Then M:=M-N

Else N:=N-M;

Evklid:=M

End;

Begin

Write('a=');

ReadLn(A);

Write('b=');

ReadLn(B);

Rez:=Evklid(Evklid(A+B,

Abs(A-B)), A*B);

WriteLnCNOD равен',Rez)

End.

Из примера видно, что тело функции отличается от тела про-

цедуры только тем, что в функции

результат присваивается

пере-

менной

тем оке

именем,

что

функция.

Обращение к функции является операндом в выражении. Оно

записывается в следующей форме:

<Имя функции> (<Список фактических параметров>)

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

параметрами все те же. Сравнивая приведенные выше програм-

мы,

можно сделать вывод, что программа

N0D3

имеет определен-

ные преимущества перед другими. Функция позволяет получить

результат путем выполнения одного оператора присваивания. Здесь

иллюстрируется возможность того, что фактическим аргументом

при обращении к функции может быть эта же функция.

По правилам стандарта Паскаля возврат

вызывающую програм-

му из подпрограммы происходит, когда выполнение подпрограммы

доходит

до

ее конца (последний End). Однако в Турбо Паскале есть

средство, позволяющее выйти из подпрограммы в любом ее месте.

Это

оператор-процедура Exit. Например, функцию определения наи-

большего из двух данных вещественных чисел можно описать так:

Function Max(X,Y:

Real):

Real;

Begin

Max:=X;

If X>Y Then Exit Else Max:=Y

End;

Еще раз об области действия описаний. В Паскале неукосни-

тельно действует следующее правило: любой программный объект

(константа, переменная, тип и т.п.) должен быть описан перед

использованием

программе.

Иначе говоря, описание объекта дол-

жно предшествовать его первому появлению в других фрагментах

программы. Это правило относится и к подпрограммам.

На рис. 30 схематически показана структура взаимного распо-

ложения описаний подпрограмм в некоторой условной програм-

ме.

Попробуем, используя эту схему, разобраться в вопросе об

области действия описаний подпрограмм.

Основная программа

Подпрограмма А

Подпрограмма А\

Подпрограмма

А 2

Подпрограмма В

Подпрограмма

Подпрограмма В2

Подпрограмма

В 21

Подпрограмма В22

Рис.

Любая подпрограмма может использоваться лишь в пределах

области действия ее описания. Например, область действия под-

программ А и В

—

основная программа. Поэтому из основной про-

граммы можно обратиться к подпрограммам А и В. В свою оче-

редь,

в подпрограмме В могут быть обращения к подпрограмме А;

а из А нельзя обратиться к В, поскольку описание А предшествует

описанию В. Подпрограммы А\ и А2 локализованы в подпрограм-

ме А и могут использоваться только в ней; из А2 можно обратить-

ся к А\, но не наоборот.

Из подпрограммы В\ можно обратиться к А, поскольку ее опи-

сание является глобальным по отношению к 51, но нельзя обра-

титься к А\, поскольку область действия описания А\ не распро-

страняется на блок подпрограммы В.

Из подпрограммы 522 можно обратиться только к 521, 51, А.

Объясните сами почему.

Все понятно? Если нет, то прочитайте еще раз этот раздел. Очень

важно в нем разобраться.

Если одно и то же имя описано во внешнем блоке (глобально)

и во внутреннем блоке (локально), то последнее описание (ло-

кальное) перекрывает первое в пределах внутреннего блока. Рас-

смотрим следующий пример:

Program Example1; Program Example2;

Var X: Integer; Var X: Integer;

Procedure P; Procedure P;

Var X: Integer; Begin

Begin WriteLn('x=',X) WriteLn('x=',X)

End; End;

Begin X:=l; Begin X:=l;

P P

End. End.

Что выведется на экран в результате работы программы

Examplel и Example2? Первая программа выдаст результат:

На месте многоточия будет какое-то произвольное значение,

соответствующее неопределенной величине х. Вторая программа в

результате даст

х=1

В первом случае переменная с именем х описана как глобаль-

но,

так и локально. Но процедура выводит значение локальной

переменной, которой ничего не присвоено. В этом примере иден-

тификатором х обозначены две совершенно разные величины, им

соответствуют две разные ячейки памяти.

Во втором примере переменная х одна на всю программу. Она

описана глобально. Поэтому значение 1, присвоенное ей в основ-

ной программе, передается и в подпрограмму.

Далее разговор пойдет о ситуации на первый взгляд совершен-

но парадоксальной. Оказывается, подпрограмма в своем описа-

нии может содержать обращение к самой себе. Такая подпрограм-

ма называется рекурсивной.

Рекурсивные подпрограммы. В математике рекурсивным называ-

ется определение любого понятия через самое себя. Классическим

примером является определение факториала целого числа, боль-

шего или равного нулю:

л!

если п = О,

«(«-!)!,

если п > 0.

Здесь функция факториала определена через факториал. Не-

трудно понять справедливость такого определения. Для п

> О

И!

= 1]1 = Ь2...(В-1)-Л = В-П/ =

Л(Й-1)!

Вариант 0!=1 является тривиальным. Но это «опорное» значе-

ние,

от которого начинается раскручивание всех последующих

значений факториала:

1!=

х0! = 1x1 = 1;

= 2х

= 2;

= 3х2! =

и т.д.

Рассмотрим подпрограмму-функцию, использующую в своем

описании приведенную выше рекурсивную формулу.

Function Factor(N: Pozlnt): Pozlnt;

Begin

If N=0

Then Factor:=1

Else Factor:=N*Factor(N-l)

End;

Предполагается, что тип Pozlnt объявлен глобально следую-

щим образом:

Type Pozlnt=0..Maxlnt;

Пусть в основной программе для вычисления в целой перемен-

ной х значения

используется оператор

X:=Factor (3);

При вычислении функции с аргументом 3 произойдет повтор-

ное обращение к функции Factor (2). Это обращение потребует

вычисления Factor (1). И наконец, при вычислении Factor (0)

будет получен числовой результат 1. Затем цепочка вычислений

раскрутится в обратном порядке:

Factor(1)=l*Factor(0)=1

Factor(2)=2*Factor(l)=2

Factor(3)=3*Factor(2)=6.

Последовательность рекурсивных обращений к функции долж-

на обязательно выходить на определенное значение. А весь марш-

рут последовательных вхождений машина запоминает в специ-

альной области памяти, называемой

стеком.

Таким образом, вы-

полнение рекурсивной функции происходит в два этапа: прямой

ход

—

заполнение стека; обратный ход

—

цепочка вычислений по

обратному маршруту, сохраненному в стеке.

Использование рекурсивных функций

—

красивый прием

точ-

ки зрения программистской эстетики. Однако этот путь не всегда

самый рациональный. Рассмотренную задачу с п\ можно решить

так: