    6. ОБЪЕКТЫ. ПАРАМЕТРЫ. ТИПЫ 77 

    6. Объекты, параметры, типы. Схема вычисления инвариантной функции 

    Мы уже говорили, что исполнители могут иметь память (глобальные объекты), 
а предписания исполнителей могут иметь входные и выходные параметры. С тех 
пор, однако, наша точка зрения на исполнителей несколько изменилась: кроме 
«железных» базовых исполнителей вроде Резчика металла бывают, как мы теперь 
знаем, и исполнители, реализованные программно, например такие, как Резчик 
сита или Обработчик рядов. Естественно, встает вопрос: если мы реализуем 
исполнителя программно, как описать его глобальные объекты, параметры его 
предписаний, как с ними оперировать и что вообще в этом случае значит слово 
память? Ответу на этот вопрос в основном и посвящен настоящий раздел. 
    Объекты. Будем считать, что наши программы по-прежнему выполняет 
гипотетический Универсальный Выполнитель (УВ). УВ, несомненно, обладает 
зачатками интеллекта — во всяком случае он понимает управляющие конструкции и 
соответствующим образом выполняет их. УВ обладает и памятью — уже при вызовах 
подпрограмм ему приходится запоминать, какая программа приостановлена и о 
какого места ее надо продолжить после того, как подпрограмма будет полностью 
выполнена. Память УВ можно, однако, задействовать и явно для хранения, 
изменения и получения любой другой информации. В разных частях памяти УВ и в 
разное время можно хранить разную информацию. Отдельную часть памяти УВ мы и 

    78	ГЛ. 1. НАЧАЛА ПРОГРАММИРОВАНИЯ 

будем называть объектом, а информацию, которая в данный момент в этой 
части хранится, — состоянием или значением объекта. Для того чтобы в программе 
можно было указать, какой именно объект мы имеем в виду, объектам даются 
имена, позволяющие отличить их друг от друга. Еще одной характеристикой 
объекта является тип информации, которая хранится в объекте. Например, 
хранится ли в объекте информация типа да/нет, буква русского алфавита или 
действительное число. 
    Можно представлять себе память УВ в виде доски, а объекты в виде 
прямоугольников, которые  ограничивают части  доски и внутри   которых   
записывается нужная информация, например: 

                       Е     
                       ------------------------
                      |       2.718281     |
                      ------------------------

    Имена объектов надписываются сверху прямоугольников. Состояние объекта—это 
то, что записано внутри прямоугольника. Изменение состояния означает стирание
старой информации и запись новой. 
    Имена, которые даются объектам, на самом деле позволяют различать объекты 
лишь внутри одной программы. В разных программах имена, вообще говоря, могут и 
совпадать. Поэтому правильнее считать, что, начав выполнять какую-то 
программу, УВ рисует для этой программы на доске большой прямоугольник, а уже 
внутри него рисует отдельные объекты: 

                    программа А      программа В 
                  -------------------------       -------------------    
                 |     X                       |      |  X                    |
                 |   -------------------    |      |  -----------------  |
                 |   |                       |   |      |  |                   |   |
                 |   -------------------    |      |  -----------------  |
                 |    Y                        |      |  Y                     |
                 |    -------------------   |      |  ----------------   |
                 |   |                      |    |      |  |                   |   |
                 |   -------------------    |     |   ----------------    |
                 -------------------------      ----------------------

    По окончании выполнения программы УВ стирает с доски весь ее прямоугольник
со всеми объектами внутри. Таким образом, объект X программы А и объект X
программы В -это, вообще говоря, два разных объекта, никак между собой 
не связанных.
    Аналогичным образом УВ заводят область памяти («большой прямоугольник») и 
при начале работы с реализованным программно исполнителем:

      исполнитель И
      __________ 
     |                        |
     |    P                 |
     |    -----------      |
     |   | ______|     |
     |                        |
     |   R                  |
     |   -------------    |
     |  |_______|    |
     |__________ |

    6. ОБЪЕКТЫ, ПАРАМЕТРЫ, ТИПЫ 79 

    В целом, таким образом, «доска» УВ в каждый момент времени разбита на 
большие прямоугольники исполнителей и программ, которые разбиты уже на 
отдельные объекты. Тексты программ обычно также записываются не на отдельных 
листках, а на этой «доске». В процессе выполнения УВ работает только с 
доской—читает программы; помечает, где какая программа приостановлена; заводит 
и стирает прямоугольники объектов, программ и исполнителей; меняет содержимое 
прямоугольников-объектов и т. п. 
    Объекты, расположенные внутри прямоугольника программы, называются 
локальными объектами программы, а расположенные внутри прямоугольника 
исполнителя - глобальными объектами исполнителя.
    Подчеркнем, что имя локального объекта программы можно использовать только 
в данной программе (то же имя в другой программе означает совершенно другой 
объект) и что локальные объекты программы возникают в момент начала выполнения 
программы и исчезают, когда выполнение программы заканчивается. Про эти 
свойства локальных объектов принято говорить, что локальные объекты программы 
локализованы в программе как по тексту, так и по времени существования. 
    Соответственно глобальные объекты исполнителя локализованы в исполнителе 
как по тексту, так и - по времени существования. Локализация по тексту 
означает, что имя глобального объекта исполнителя можно использовать только в 
тексте .данного исполнителя (от слова исполнитель до слов конец исполнителя) 
— то же имя в другом исполнителе означает совершенно другой объект. 
Локализация по времени существования означает, что глобальные объекты 
исполнителя возникают в момент начала работы с ним (предписание «начать 
работу») и исчезают после конца (предписание «кончить работу»), 
    Замечание. Описание объектов в терминах доски и прямоугольников не более, 
чем модель. По сути дела нас интересуют формы записи программ и смысл этих 
форм, т. е. то, что происходит при их выполнении. Как это происходит, не очень 
важно. Мы можем, например, считать, что УВ сначала читает программу целиком, а 
потом «берет в руки инструменты» и изготавливает устройство с кнопкой (или 
кнопками), при нажатии на которую система рычагов или электронных схем 
производит требуемые действия (в частности, в нужной последовательности 
нажимает на кнопки базовых исполнителей). Таким образом, к модели с доской 
нужно относиться лишь как к одному из возможных описаний семантики форм записи 
программ, а не как к объективной реальности. 
    Локальные объекты программ. Рассмотрим простейший пример. Пусть требуется 
написать программу, которая с помощью Стекового калькулятора вычисляет 
произведение чисел от 1 до 10: 

    программа произведение 
    .  дано       : 


    80 ГЛ. 1. НАЧАЛА ПРОГРАММИРОВАНИЯ 


    .  получить:  | на табло Стекового калькулятора произведение 
    .                     | чисел от 1 до 10 
    .       объекты : 
    .       N  :  число 
    . --------------------
    .     N  := 1 
    .     СК.добавить (1) в стек 
    .     цикл 
    .      .   инв: | в вершине стека калькулятора находится 
    .      .	     | произведение чисел от 1 до N                        
    .      .   пока N=?MO 
    .      .   выполнять     
    .      .   N. увеличить на 1 
    .      .   СК. добавить (N) в стек	: 
    .      .   СК. умножить                         
    .      конец цикла                          
    .           утв: |в вершине стека калькулятора находится 
    .                   | произведение чисел от 1 до N и N = 10 
    .      СК. показать результат 
    конец программы 

    Запись «объекты: N: число» означает, что в программе будет использоваться 
локальный объект с именем N типа число (т. е. внутрь «прямоугольника» N будут 
записываться числа). В начале выполнения этой программы УВ «нарисует большой 
прямоугольник» для этой программы, а внутри него — объект с именем N. Кроме 
того, он запомнит, что N — это объект типа число. 
    Строка «N : = 1» означает, что объект N надо установить в состояние 1 (т. 
е. в прямоугольник с именем N надо записать число 1). По историческим причинам 
такая установка состояния (значения) объекта называется присваиванием, знак 
:=. называется операцией присваивания, а строка в целом читается как «N 
присвоить 1». 
    Имена объектов можно использовать в арифметических и логических 
выражениях, например «N != 10». Встретив имя объекта в выражении, УВ заменяет 
его на значение этого объекта (подобно тому, как она заменяет на значения имена 
констант) и только после этого вычисляет значение всего выражения целиком. 
   Имена объектов могут фигурировать и в качестве фактических параметров при 
вызовах предписаний и программ. Например, при вызове «СКдобавить <N> в стек» в 
качестве фактического параметра будет использовано значение объекта N. 
    Кроме того, над объектами, расположенными в памяти УВ, можно выполнять 
некоторые операции. Для объектов разных типов 

    6. ОБЪЕКТЫ,  ПАРАМЕТРЫ, ТИПЫ 81 

набор операций различен. Скажем, объекты типа число можно увеличивать и 
уменьшать, например «N.увеличить на 1». Заметим, что то же самое действие 
можно было выразить и по-другому — с помощью оператора присваивания: 
«N := N + 1».
    Описание локального объекта программы (т. е. запись «объекты: N: число») 
обычно можно опускать. УВ все равно заведет объект с именем N, так как это имя 
встречается в программе, а его тип постарается определить из контекста. Зная, 
например, что в вызове «СК.добавить <N> в стек» параметр должен быть числом, 
УВ сделает вывод, что и объект N имеет тип число. Естественно, что если УВ 
обнаружит противоречия или не сможет определить тип объекта по контексту, то 
программа выполняться не будет. 
    Глобальные объекты исполнителей. Подобно тому как локальные объекты 
программы возникают в момент начала выполнения программы и исчезают, когда 
выполнение программы заканчивается, глобальные объекты возникают при начале 
работы с исполнителем и исчезают после конца работы. Изменяя состояния этих 
объектов, разные программы исполнителя могут передавать информацию друг другу. 
Глобальные объекты исполнителя описываются в подразделе объекты раздела 
описаний исполнителя (между словами исполнитель и конец описаний). Форма 
описаний ничем не отличается от описания локальных объектов программ: 

    исполнитель И 
    .   СП1 
    .   ...........
    .
    .   объекты: 
    .      Р, R : число 
    .    .............
    конец описаний 

    После такого описания во всех программах данного исполнителя (т. е. в 
программах, расположенных между словами конец описаний и конец исполнителя) 
можно использовать имена Р и R для указания на соответствующие глобальные 
объекты исполнителя (оба этих объекта будут иметь тип число). Таким образом, 
внутри программы можно использовать как имена локальных объектов данной 
программы, так и имена глобальных объектов того исполнителя, к которому 
относится программа. Естественно, что эти имена не могут совпадать, т. е. ни в 
одной программе исполнителя и не может быть локальных объектов с именами Р и R. 
    Опускать описания глобальных объектов исполнителя нельзя: если объект не 
описан ни в исполнителе, ни в программе, то он 

    82 ГЛ. 1. НАЧАЛА ПРОГРАММИРОВАНИЯ 


считается локальным, Можно, однако, опустить описание типа, например написать 

    объекты: 
       Р, R : ... 

В этом случае УВ будет считать объекты Р и R глобальными, а тип 
постарается определить по контексту. 
    Входные и выходные параметры программ. Рассмотрим пример: 

    программа сделать (вх : t: Z+) шагов прямо 
   .  дано        : | Путник где-то в квадранте 
   .  получить : | Путник сделал t шагов вперед 
   . -----------------
    .    цикл t раз                                                                           (*)
    .    .  выполнять 
    .    .  Путник.сделать шаг .   
    .   конец цикла 
   конец программы 

    Запись «<вх: t: Z+>» в имени программы означает, что объект с именем t 
является входным (вх) формальным параметром (т. е, объектом) программы и имеет 
тип Z+ (неотрицательное целое). Если в какой-то другой программе написать 
«сделать <5> шагов прямо», то при выполнении этого вызова объект t программы 
(*) будет иметь состояние 5. Если написать «сделать <7> шагов прямо», то t будет 
иметь значение 7. Если «сделать <N> шагов прямо», то 1 будет иметь значение 
объекта N. А если «сделать <К + 3> шагов прямо», то t будет иметь значение выражения 
К + 3  (это значение будет вычислено УВ в момент вызова). Аналогично в программе:, 

    программа идти до-препятствия <вых : расстояние : Z+>
    .  дано        : | Путник где-то в квадранте 
    .  получить : | Путник прошагал прямо до упора, в выходном, 
    .                     | объекте — число сделанных Путником шагов 
    .                     | (расстояние до препятствия) 
    . ------------------
    .  расстояние := 0                                                                      (**)
    .  цикл 
    .  .   утв: | расстояние = число сделанных Путником шагов 
    .  .   пока Путник.впереди свободно 
    .  .   выполнить 
    .  .     Путник.сделать шаг 
    .  .     расстояние.увеличить на 1 . 
    .  конец цикла 
    конец программы 


    6. ОБЪЕКТЫ, ПАРАМЕТРЫ, ТИПЫ 83 

запись «<вых: расстояние: Z+>» означает, что объект с именем «расстояние» 
является выходным формальным параметром (объектом) программы и имеет тип Z+ 
(неотрицательное целое). Если теперь написать «идти до препятствия (вых: К)», 
то после выполнения этого вызова в Объекте К будет число сделанных Путником 
шагов (расстояние до препятствия). Если «идти до препятствия <вых: М: Z+>», 
то число шагов Путника окажется в объекте М и т. п. 
    Обратите внимание, что для повышения выразительности текста в вызове можно 
указать, каким именно является параметр (входным, выходным, входно-выходным), 
а также указать его тип. 
    Входно-выходные формальные параметры сочетают в себе свойства и
входных и выходных: в момент начала выполнения программы 
входно-выходной формальный параметр имеет значение соответствующего 
фактического параметра, указанного в вызове, а после окончания выполнения 
программы фактический параметр имеет значение, полученное в программе. 
Естественно, что выражение в качестве фактического выходного 
или входно-выходного параметра указать нёльзя.
    Параметры программ не случайно называются «формальными». По сути дела, они 
являются не объектами, а обозначениями для соответствующих фактических 
параметров, указанных в вызове. В программе (*), например, объект t не 
создается («прямоугольник» для t вообще не рисуется) — УВ прямо использует 
значение фактического параметра (5, 7, N, К + 3). Аналогично при выполнении 
вызова «идти до препятствия <вых : М : Z+)» УВ не создает объекта «расстояние» 
в программе (**), а прямо работает с объектом М (вместо «расстояние : = 0», 
например, выполняет «М:=0»). Именно поэтому «расстояние» называется 
формальным, а М — фактическим параметром программы, 
    Если параметр является входным, то это значит, что его значение 
используется в программе, но не меняется в результате ее выполнения. Другими 
словами, значения входного параметра до и после выполнения программы должны 
совпадать. Если параметр выходной, то в результате выполнения программы его 
значение может быть изменено, однако начальное (перед выполнением программы) 
значение объекта несущественно и в программе не используется. Если параметр 
входно-выходной, то это значит, что его начальное значение может быть 
использовано в программе, а в результате выполнения это значение может измениться. 
    Наконец, заметим, что имена формальных параметров, как и имена локальных 
объектов программы, локализованы в тексте программы. В качестве обозначений 
конкретных фактических 

    84 ГЛ. 1. НАЧАЛА ПРОГРАММИРОВАНИЯ 

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

    программа расстояние : Z+ 
    .  дано        : | Путник где-то в квадранте 
    .  получить : | Путник прошагал прямо до упора, в ответе — 
    .                     | число сделанных Путником шагов 
    .                     | (расстояние до препятствия) 
    .------------------
    .  ответ :=0 
    .  цикл 
    .  .  утв     : | ответ = число сделанных Путником шагов 
    .  .  пока Путник.впереди свободно 
    .  .   выполнять 
    .  .    Путник.сделать шаг                                                  
    .  .    ответ.увеличить на 1                                                
    .  конец цикла 
    конец программы 

    Тогда, написав «М := расстояние», можно получить расстояние до 
препятствия в объекте М, а написав - «N := расстояние», — в объекте N. При 
выполнении, например, оператора присваивания «М := расстояние» УВ выполнит 
программу «расстояние» и полученное при этом в ответе значение присвоит 
объекту М. 
    Программы, вырабатывающие значение, являются, по сути дела, программами с 
одним выходным параметром. Запись «программа расстояние: Z+» можно понимать 
как сокращение от «программа расстояние (вых ; ответ : Z+)». Основные отличия 
заключаются в форме использования: если программу с одним выходным параметром 
надо вызывать отдельно, то программу, вырабатывающую значение, можно 
использовать непосредственно в арифметических и логических выражениях. В целом 
особенности описания и использований программ, вырабатывающих значения, 
иллюстрируются табл. 6.1, Выбрав из двух приведенных в этой таблице путей 
использования программы тот, который нам больше нравится (это дело вкуса), мы 
можем соответственно реализовать ее либо как программу с одним выходным 
параметром, либо как программу, вырабатывающую значение, 

    6. ОБЪЕКТЫ,   ПАРАМЕТРЫ,  ТИПЫ  85 


    Таблица  6.1 

          Программы,                                         Программы 
вырабатывающие значение       с одним   выходным   параметром

                                             Описание
    программа G: да/нет                программа G (вых: q: да/нет) 

                                        Использование 
    если G то ...                                     G (вых: успех) 
                                                              если успех то ... 

                                         Описание 
    программа F <вх: X): R                программа F <вх: X, вых: Y: R> 

                                       Использование 
    B := F(А)                                               F (А, В)
    Z := (F<X1>+F«2»/2.0                        F(X1, Y1) 
                                                                   F(X2, Y2) 
                                                                   Z:=(Y1+Y2)/2.0 


    Типы объектов. Для объектов разных типов УВ может выполнять разные наборы 
операций. Таким образом, 

      ||  тип характеризует множество состояний, которые может 
      ||  принимать объект, и множество операций, которые над ним допустимы. 

    Например, состоянием (значением) объекта типа число может быть любое 
действительное число (множество состояний — множество действительных чисел). 
Над этим объектом допустимы любые арифметические операции и операции сравнения 
(при использовании имени объекта в выражениях), а кроме того, операции 
присваивания, увеличения и уменьшения на некоторую величину (т. е. на значение 
некоторого выражения) и др. Естественно, возникает вопрос: какие еще типы, 
кроме типа число, могут иметь объекты в программе? Ответ на этот вопрос звучит так: 

||    Объекты программы либо могут быть некоторых предопределенных типов (эти 
||    типы мы сейчас перечислим), либо построены с помощью способов конструирования 
||    из других объектов (подобъектов). Подобъекты в свою очередь могут быть либо 
||   предопределенными, либо построены из годподобъектов и т. п. В конечном счете 
||   любой объект либо к:.:сет предопределенный тип , либо строится из объектов 
||   предопределение1..; типов с помощью, быть может неоднократного, применения 
||   различных способов конструирования. 

    86	ГЛ. 1. НАЧАЛА ПРОГРАММИРОВАНИЯ 

    Способы конструирования объектов и типов будут изложены в следующем 
разделе. Предопределенными типами являются следующие: 

    — Q (да/нет), 
    — S (символ),    
    — Z (целое), 
    — Z+  (неотрицательное целое), 
    — R (действительное число или просто число). 

    Значки Q, S, Z, Z+, R и слова в скобках являются синонимами, т, е. запись 
«объекты: N : число» эквивалентна записи «объекты : N : R». Таким образом, 
существует всего пять предопределенных типов. Опишем их. 
    Множество значений для каждого из типов Z, Z+, R ясно следует из названия 
типа. Объект типа да/нет может принимать лишь одно из двух значений — либо да, 
либо нет. Значением объекта типа символ является символ: либо буква, либо 
цифра, либо специальный значок (например, "+", "—" и т. п.). 
Существует также символ " ", который называется пробелом и используется для 
разделения слов в последовательности символов. Множество различных символов 
содержит всего 256 элементов и некоторым образом упорядочено. Этот порядок 
сохраняет порядок букв в алфавите |"а"<"b"<"с") и порядок цифр ("0"<"1",<"2")
    Объект любого типа может иметь значение неопр (т. е. быть неопределенным). 
В множество значений любого упорядоченного типа (S, Z, Z+, R) входят, кроме 
того, два идеальных значения —оо и +оо, которые могут использоваться только в 
операторе присваивания и в операциях сравнения. 
    Операции. Над объектами любого предопределенного типа допустимы операции 
присваивания ( := ), сравнения на равенство ( = ) и неравенство (!=). Если тип 
упорядоченный (S, Z, Z+, R). то допустимы также сравнения на <, <=, >,>=. В 
операциях сравнения для упорядоченных типов наряду с обычными могут 
участвовать и идеальные значения —оо и +оо. Значение "неопр" может участвовать 
только в операциях присваивания, сравнения на равенство и неравенство. 
    Объекты и различные функции от них могут входить в арифметические и 
логические выражения, которые подчиняются общепринятым правилам записи. В 
число функций входят максимум, минимум, остаток, знак, модуль (абсолютная 
величина) и др. (см. приложение 1). При записи арифметических выражений знак — 
означает вычитание, + — сложение, * — умножение, / — деление и ** — возведение 
в степень. 
    Если в операторе присваивания слева стоит имя объекта типа Z «ли Z+, а в 
результате вычисления значения выражения в правой 

    ОБЪЕКТЫ,  ПАРАМЕТРЫ,  ТИПЫ 87 

части получилось нецелое число, то присваивается целая часть полученного 
значения. При попытке присвоить объекту типа Z+ отрицательное число 
происходит отказ. 
    Наконец, имеется некоторое количество других операций, например операции 
увеличить на и уменьшить на для числовых типов, операции следующий и 
предыдущий для упорядоченных дискретных типов и т. п. Мы будем вводить их по 
мере надобности. 

    Пусть есть объекты:

    q : Q 
    s : S 
    n : Z+ 
    z,A,B,C,D : Z 
    r : R 

    Приведем несколько примеров фрагментов программ с использова-. нием этих 
объектов, арифметических и логических выражений! 

    q := нет 
    s: = "а" 
    n:=0 
    z::= -137 
    r := 2.71828 
    q := (n = 3 или r >= z ) 
    если s = " " или не q то ... 
    если "a" < s < "я" или 
    "0" < s < "9" то  ....
    цикл пока s != " "    выполнять 
    А := 7 
    В := - 49 
    С := (А + 5)/15 — В 
    если А + В < 4*С — 1 < D то 
    D := максимум (А, В) + частное (В + 3,С) 

    Описания типов. Как мы видели, тип локальных и глобальных объектов можно 
указать в разделе объекты, расположенном соответственно в программе или в 
исполнителе, в заголовке программы можно указать тип формальных, а в вызове — 
тип фактических параметров. Описание типа всюду можно опускать, тогда тип 
будет определен по контексту. 
    Кроме этого, тип любого объекта можно указать в дано/получить или в 
утверждении. Программу (**), например, можно записать в виде: 

    программа идти до препятствия {вых : расстояние) 
    .  дано        : | Путник где-то в квадранте 
    .  подучить: | расстояние: Z+ | расстояние до препятствия 


    88 ГЛ. 1. НАЧАЛА ПРОГРАММИРОВАНИЯ 


    .                 | (число сделанных Путником шагов прямо) 
    .                 |  Путник прошагал прямо до упора 
    .  ----------------
    .    расстояние := 0 
    .    цикл 
    .    .   утв   : | расстояние = число сделанных Путником шагов 
    .    .   пока Путник.впереди свободно 
    .    .   выполнять 
    .    .     Путник.сделать шаг 
    .    .     расстояние.увеличить на 1 
    .    конец цикла 
    конец программы 

    Таким образом, на запись «расстояние: Z+» можно смотреть как на 
утверждение о типе объекта. Таких утверждений, естественно, может быть много, 
т. е. тип объекта «расстояние» можно указать и в заголовке программы, и в 
дано/получить, и в утверждениях внутри программы. УВ лишь контролирует 
непротиворечивость таких описаний и их соответствие использованию объекта 
(например, из строки «расстояние := 0» следует, что «расстояние» — объект 
числового типа). Хотя описания типа всюду можно опускать, в программе должно 
быть достаточно информации для определения типа по контексту, поэтому тип 
каких-то объектов где-то описывать надо. Мы обычно будем описывать тип 
глобальных объектов исполнителя и тип формальных параметров программ (в 
заголовке или в дано/получить). Наоборот, тип локальных объектов программ, как 
правило, описываться не будет. 
    Описания типов в дано/получить, вызовах и утверждениях являются как 
контекстом, исходя из которого УВ может определить тип объекта, так и 
средством контроля, уменьшающим вероятность ошибки в программе. Кроме того, 
они могут быть использованы для того, чтобы сделать программу более понятной и 
легче читаемой. 
    Примеры программ, использующих объекты предопределенных типов. 

    программа число корней квадратного уравнения (вх: P,Q): Z+ 
    .  дано        : P,Q : число | коэффициенты уравнения 
                          х**2 + P*x+Q = 0 
    .  получить: | число действительных корней этого уравнения 
    . -----------------
    .  D :=P*P — 4*Q 
    .  выбор 
    .  .  при D > 0 ==> ответ := 2 
    .  .  при D = 0 ==> ответ := 1 


    6. ОБЪЕКТЫ.   ПАРАМЕТРЫ,  ТИПЫ     89 


    .  .   при D <0 ==> ответ := 0 
    .  конец выбора 
    конец программы 

    программа   переставить   циклически   влево   <вх/вых : А, В, С : число>
    .  дано        :     
    .  получить: | значения А,В,С циклически сдвинуты влево 
    . -----------------
    .  R := A 
    .  А := В 
    .  В := С 
    .  C := R 
    конец программы 

    программа число различных (вх! А,В,С: число): Z+ 
    .  дано        : | три действительных числа 
    .  получить:  | количество различных среди них 
    . ---------------- 
    .    выбор 
    .   .   при А = B = C             ==>     ответ := 1 
    .   .   при A != B != C != A  ==>     ответ := 2
    .   .	иначе                    ==>     ответ := 3
    .   конец выбора 
    конец программы 

    Обратите внимание на условие «А = В = С». Это условие в более развернутой 
форме можно записать так: «А = В и В = С». Аналогично «А != В != С != А» означает 
«А != В и В != С и С != А», «а =< х  =< b» означает «a =< х и х =< b» и т. д. 

   программа старшая цифра (ex:n0):Z+ 
   .  дано        : n0 : Z+ | неотрицательное целое число 
   .  получить :             | старшую цифру десятичного разложения п0
    .   п := п0 
    .   цикл пока п >= 10 выполнять 
    .   .    п := целое (п/10) 
    .   конец цикла 
    .   ответ := п 
    конец программы 

    При выполнении этой программы с п0 = 3271 объект п будет последовательно 
принимать состояния 3271, 327, 32, 3. Последнее вначение и будет присвоено 
ответу (т. е. выработано в качестве значения программы). Стандартная функция 
«целое» получает целую часть аргумента, в данном случае выражения п/10. 

    90 ГЛ.  I. НАЧАЛА ПРОГРАММИРОВАНИЯ 

    программа: две старшие цифры < вх : п0 , вых : с1,с2 > 
    .  дано : ri0 : Z+              | неотрицательное целое число 
    .  получить : c1,c2 : Z + | две старшие цифры числа n0. Если n0
    .                                        | однозначное, то c1 должно быть равно 0,
    .                                        | а с2 = п0
    .---------------------------------- 
    .  n := п0 
    .  цикл пока n >= 100 выполнять 
    .  .  п := целое (п/10) 
    .  конец цикла 
    .  c1 := целое (п/10) 
    .  с2 := остаток (п,10) 
    конец программы 

    Схема вычисления значения инвариантной функции. В разд. 4 были описаны 
базисные схемы обработки информации «рекурсия», «итерация» и «проектирование 
цикла с помощью инварианта». Сейчас мы приведем еще одну базисную схему — 
схему вычисления инвариантной функции. Пусть М — некоторое множество, 
F : M -> Y — заданная функция и требуется определить значение F(x0) функции F 
в некоторой точке х0 из М. 
    Рассмотрим предикат Р : М -> {да, нет} , заданный следующим образом: 

    Р (х) = да <==> F (х) легко вычислить. 

    Если существует преобразование Т : М \ Р --> М такое, что F, является 
Т-инвариантной функцией ( т. е. F( T( x ) ) = F( x ) для любого х из М \ Р ), то можно 
применить метод итераций (разд. 4) и, получив Р(х)=да, вычислить F(x) вместо F(x0): 

    х := х0 
    цикл пока не   Р (х) 
    .  выполнять 
    .   применить к <х> преобразование Т 
    конец цикла 
    ответ  := F(x) 

    Графически это изображено на рис. 6.1, где 

   I = {х из М : F (х) = F(х0) } 

  Т-инвариантность F обеспечивает постоянство значений функции на траектории 
{ х из М : х = Tn(x0), n из Z+ }. Именно это и позволяет вычислять значение функции 
не в точке х0, а в любой точке х этой траектории. 
    Рассмотрим пример. Пусть требуется определить наименьший общий делитель 
двух чисел а и b, где a, b из Z+, a + b > 0. Рас-

    6. ОБЪЕКТЫ.   ПАРАМЕТРЫ,  ТИПЫ 91 

смотрим эту задачу как задачу вычисления значения функции F : M --> Y. Тогда 
М = Z+*Z+ \ { 0 , 0 }, a Y = N (множество натуральных чисел). 
    Сформулируем предикат Р, т.е. опишем   множество   пар {а, b) из М,  для  которых   
НОД  вычисляется   легко. Очевидно,  что 


    Рис. 6.1. Схема  вычисления  инвариантной функции 


если   а = 0,   то   НОД (а, b) = b,   и,   наоборот,   если   b = 0,   то 
НОД (а, b) = а. Поэтому положим 

    Р( а , b ) = (а = 0 или b = 0). 

    Таким образом, если Р( а, b ) = да, то НОД (а, b) = а + b. 

    Осталось придумать преобразование Т, которое бы сохраняло НОД и 
«приближало» к множеству { х из М : Р(х) = да }. Так как нужно сохранять НОД, то 
посмотрим на его свойства. Поскольку 

    НОД (а, b) == НОД (а - b,b) = НОД (а, b - а), 

    определим  преобразование  Т : М \ Р --> М  следующим   образом: 

    T(a,b)   = (a - b, b ) , если a >= b >0 ,
    T(a,b)   = (a , b - a ) , если b >= a >0 ,

    Очевидно, что для любого х0 из М существует n из Z+ такое, что Р(х)=да, где 
х = Тn (х0). Итак,решение задачи можно записать в виде 

    программа НОД (вх: а0, b0 : Z+) : Z+ 
    .  дано       : а0 + b0 > 0 
    .  получить: ответ > 0 | ответ = НОД (а0, b0 ) 
    . ----------------
    .   а := а0 ; b := b0   
    .   цикл 


    92 ГЛ. 1. НАЧАЛА ПРОГРАММИРОВАНИЯ 


    .  .   инв : | НОД(а,b) = НОД(а0, b0) 
    .  .    пока а > 0 и b >0 
    .  .   выполнять 
    .  .     выбор 
    .  .    .   при a >= b => a := a —b 
    .  .    .   при b >= a => b := b — a 
    .  .    конец выбора 
    .  конец цикла 
    .      утв: а = 0 или b = 0 | и НОД (а,b) = НОД (а0. b0 ) 
    .  ответ := а + b 
    конец программы 

    ЗАДАЧИ И УПРАЖНЕНИЯ 

    В задачах  1—13 напишите программы, которые находят: 
     1. Количество максимальных чисел среди А, В, С, 
     2. Количество разных чисел среди А, В, С. 
     3. Количество цифр в десятичной записи числа п. 
     4. Количество цифр 7 в десятичной записи числа п. 
     5. Сумму цифр в десятичной записи числа п. 
     6. Первую цифру дробной части  положительного числа п, 
     7. Количество корней биквадратного уравнения х4 + Рх2 + Q = 0. 
     8. Количество    целых    чисел,    удовлетворяющих   неравенству 
         x**2 + Ах + В < 0. 
     9. Количество целых точек в круге (х — а)**2 + (у — b)**2 =< г**2. 
    10. Длину интервала отрицательности функции 
          f(x)== максимум (а — х , b — 2х , х + с). 
    11. sin (sin (... sin(x) ...)) —всего N раз. 
    12. a*b*a*b*a*b* ... — всего N знаков умножения. 
    13. Расстояние от  точки плоскости с  координатами х0,  у0 до 
         а) круга радиусом г > 0 с центром в точке x1, y1; 
         б) прямой у = ах + b; 
         в) отрезка с концами в точках (ах, ау) и (bx, by). 
    14. Напишите программу, которая определяет, пересекаются ли два отрезка на 
плоскости, заданные координатами своих концов, 
    15. С помощью схемы вычисления инвариантной функции напишите программу, 
находящую НОД двух чисел на основе тождества НОД(2х, 2у+1) = НОД(х, 2у+1). 
    16. С помощью схемы, проектирования цикла с помощью инварианта напишите 
программу, которая находит сумму ряда для sin(x) с заданной точностью. 
    17. С помощью схемы проектирования цикла с помощью инварианта напишите 
программу, которая находит n-е число Фибоначчи.
