    ГЛАВА 1 

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

    1. Основные понятия программирования, примеры исполнителей и простейших программ 

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

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

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

    Исполнитель «Резчик металла» (РМ). 

    Пример 1. Этот исполнитель представляет собой простейший станок с числовым 
программным управлением н состоит

    1. ОСНОВНЫЕ ПОНЯТИЯ ПРОГРАММИРОВАНИЯ      11 

из прямоугольного стола, на который можно класть листы металла, и резака, 
расположенного над столом. Резак можно поднимать, опускать и перемещать 
параллельно краям стола. Поскольку мы будем рисовать стол и металл на бумаге
(на доске), то будем говорить о перемещениях резака вправо, влево, вверх и 
вниз. При опускании резака и при движении в опущенном состоянии в листе 
металла под резаком образуется прорезь. 
    Будем считать, что резак имеет размер 0.5*0.5 мм и перемещается с шагом 
0.5 мм. Идеализируя ситуацию, можно считать стол Резчика металла клетчатым 
полем (с клетками размером 0.5*0.5 мм). Резак всегда находится в некоторой 
клетке этого поля: его можно перемещать в соседние клетки по горизонтали и по 
вертикали, но не по диагонали. При опускании или передвижения опущенного 
резака вырезается целиком вся клетка. 
    Резчик металла снабжен датчиками, которые позволяют анализировать, 
находится ли резак в клетке у верхнего, нижнего, левого или правого края 
стола и есть ли металл в клетке под резаком, 
    Система предписаний Резчика металла состоит из следующих предписаний: 

      1. начать работу 
      2. поднять резак 
      3. опустить резяк 
      4. шаг вправо 
      5. шаг влево 
      6. шаг вверх 
      7. шаг вниз 
      8. резак над металлом		: да/нет
      9. резак у верхнего края стола         	: да/нет 
    10. резак у нижнего края стола         	: да/нет 
    11. резак у правого края стола         	: да/нет 
    12. резак у левого края стола          	: да/нет 
    13. кончить работу 

    Запись «резак над металлом : да/нет» означает, что у предписания «резак 
над металлом» есть один выходной объект и этот объект может принимать одно из 
двух состояний: либо да, либо нет. (Можно считать, что в кнопку «резак над 
металлом» встроена лампочка, которая после нажатия на кнопку может либо 
загореться, либо не загореться.) Предписания такого вида мы будем называть 
вырабатывающими значение типа да/нет. 
    Более компактно систему предписаний Резчика металла можно записать в виде 

    1. начать работу 


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


    2. поднять/опустить резак 
    3. шаг вправо/влево/вверх/вниз 
    4. резак над металлом	: да/нет 
    5. резак у верхнего/нижнего/правого/левого края стола : да/нет 
    6. кончить работу 

    В дальнейшем мы будем пользоваться именно такой сжатой формой записи 
системы предписаний. Цифры слева в системе предписаний нумеруют строки 
(группы предписаний). 
    Поясним теперь, что происходит при выполнении отдельных предписаний 
Резчика металла (как принято говорить в программировании, поясним их 
семантику). По предписанию «начать работу» резак оказывается в левом верхнем 
углу стола в поднятом положении. При попытке сделать шаг вверх, когда резак 
уже наводится у верхнего края стола, возникает исключительная ситуация 
«отказ». Аналогично отказ происходит при попытке сделать шаг вправо, когда 
резак у правого края, и т. п. Предписания «поднять/опустить резак» переводят 
резак в требуемое положение независимо от того, был ли он поднят или опущен, и 
никогда не приводят к отказу. Резак можно двигать и в поднятом, и в опущенном 
состоянии независимо от того, есть под ним металл или нет. 

   Пример программы для исполнителя «Резчик металла»:

    программа прямоугольник 
    . дано       : | лист металла закрывает весь стол Резчика 
    . получить: | от левого верхнего угла отрезан прямоугольник 
    .________ | размером 2*3 шага Резчика металла 
    .	PM.начать работу 
    .	РМ.шаг  вниз 
    .	РМ.шаг  вниз 
    .	РМ.опустить резак 
    .	РМ.шаг вправо 
    .	РМ.шаг вправо 
    .	РМ.шаг вправо 
    .	РМ.шаг вверх 
    .	РМ.шаг вверх 
    .	РМ.поднять резак 
    .	РМ.кончить работу 
    конец программы 

    Эта программа описывает последовательность из 11 вызовов предписаний 
исполнителя «Резчик металла». По окончании ее выполнения в листе металла будут 
прорезаны клетки, заштрихованные на рис. 1.1. 

    1. ОСНОВНЫЕ ПОНЯТИЯ ПРОГРАММИРОВАНИЯ     13 

    Конец  примера   1.

    Напомним: программа — это формальное описание последовательности вызовов 
предписаний (в примере 1 — предписаний Резчика металла). Слово «формальное» 
означает, что описание должно проводиться в соответствии со строгими, вполне 
определенными правилами. Мы не будем сейчас перечислять их, однако заметим, 
что в эти правила входят наличие и порядок слов программа, дано, 

    Рис.  1.1 

получить, конец программы, составленная из точек вертикальная линия, 
соединяющая слово программа со словами конец программы, наличие отступа (т. е. 
сдвига имен предписаний вправо от вертикальной черты) и т. п. 
    Если в строке программы встречается знак |, то текст, начиная от этого 
знака и до конца строки, считается комментарием. Комментарий — это 
произвольный текст, который никак не влияет на последовательность вызовов 
предписаний при выполнении программы, а служит лишь для пояснения смысла 
программы при чтении ее человеком. Например, в программе «прямоугольник» 
комментарием является текст после слов дано и получить. 

    Исполнитель «Путник» (П). 

    Пример 2. Этого исполнителя следует представлять в виде лунохода, который 
находится где-то в далекой неизвестной местности (назовем ее квадрантом). 
Путником можно управлять (например, по радио) с помощью следующей системы 
предписаний: 

    1. начать работу 
    2. впереди/справа/слева свободно      : да/нет 
    3. впереди/справа/слева занято	: да/нет 
    4. сделать шаг 
    5. шагать до упора 
    6. повернуться направо/налево 
    7. повернуться на север/юг/запад/восток 
    8. кончить работу 

    Квадрант Путника является прямоугольным клетчатым полем неизвестных 
размеров. Некоторые клетки квадранта могут быть заняты препятствиями. По краю 
квадрант обнесен сплошной стеной. 

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

    По предписанию «начать работу» Путник оказывается в северо-западной 
(левой верхней) клетке квадранта, лицом на восток (рис, 1,2), 


    Рис,   1.2 

    На этом и следующих рисунках Путник изображается стрелкой, указывающей 
ориентацию. Например, стрелка  указывает ориентацию на восток, а стрелка 
на юг.
    По предписанию «слева свободно» Путник анализирует, что находится слева от 
него. Если слева стена или клетка препятствия, то он отвечает нет. Если же 
слева пустая клетка квадранта, то он отвечает да. Предписание «слева занято» 
выполняется аналогично. В состоянии, изображенном на рис. 1.2, в ответ на 
«слева занято» Путник ответит да, а на «слева свободно  - нет» .

    Рис.    1.3 

    Если клетка впереди Путника свободна, то он может переместиться в нее по 
предписанию «сделать шаг». Если же впереди стена или препятствие, то попытка 
выполнить предписание «сделать шаг» приведет к отказу. По предписанию «шагать 
до упора» Путник перемещается вперед до тех пор, пока не упрется в стену 
или в препятствие. Из состояния, изображенного на рис, 1.2, по предписанию 
«шагать до упора» Путник переместится в северо-восточную (правую верхнюю) 
клетку квадранта и остановится в ней лицом no-прежнему на восток (рис, 1,3), 

    I. ОСНОВНЫЕ ПОНЯТИЯ  ПРОГРАММИРОВАНИЯ	15 

    Если в этот момент Путник получит предписание «шагать до упора» еще раз, 
то он никуда не сместится, однако и отказа не возникнет. Таким образом, вызов 
предписания «шагать до упора» никогда не приводит к отказу. 
    Наконец, по предписанию «повернуться ....» Путник поворачивается. При этом 
ему говорится, либо куда он должен повернуться (налево — на 90° против часовой 
стрелки или направо — на 90° по часовой стрелке), либо в каком положении он 
должен оказаться (лицом на север, на запад и т. п.). 

    Два примера программ для Путника: 

    программа прогулка 
    . дано        : | препятствия не прилегают к стенам 
    . получить: | Путник обошел квадрант по периметру 
    .	Путник.начать работу 
    .	Путник.шагать до упора 
    .	Путник.повернуться направо 
    .	Путник.шагать до упора
    .	Путник.повернуться направо 
    .	Путник.шагать до упора                          
    .	Путник.повернуться направо 
    .	Путник.шагать до упора 
    .	Путник.повернуться направо 
    .	Путник.кончить работу 
    конец программы 

    программа назад до упора 
    . дано       :     | Путник где-то в квадранте 
    . получить:     | Путник сместился назад до упора, 
    .                       | ориентация Путника не изменилась 
    .-------------------
    .  Путник.повернуться налево 
    .  Путник.повернуться налево 
    .  Путник.шагать до упора ,   
    .  Путник.повернуться налево .   
    .  Путник.повернуться налево 
    конец программы 

    Конец  примера 2. 

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

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

    также принципом «последним пришел — первым ушел» или 
LIFO (Last In —First Out).   Примерами   стеков   могут   служить: 
    а) обыкновенная детская пирамидка (рис. 1.4, а): большое колечко, которое 
было надето раньше, нельзя снять, не сняв предварительно маленькое, которое 
было надето позже: 
    б) железнодорожный тупик (рис. 1.4,6): вагон Б нельзя выгнать из тупика, 
не выгнав предварительно вагон В, который был эагнан позже; 
    в) труба с одним запаянным концом, куда помещают разноцветные «бочонки» 
(рис, 1Л,в). Последний пример в наибольшей 

    Рис.  1.4.  а)  детская  пирамидка, б)  железнодорожный тупик, в)  труба с 
одним запаянным концом 

    степени соответствует программистскому понятию стека: заглядывая в трубу, 
мы можем видеть, что бочонков в трубе нет, или видеть цвет верхнего бочонка, 
но не можем видеть, есть ли бочонки под верхним, сколько их и каких они цветов, 
    Элемент стека, который в данный момент можно в.зять, T. e, самый 
«верхний» (верхнее колечко на пирамидке, последний зaгнанный вагон в тупике 
и т, п.), называется вершиной стека. Боли число элементов в стеке не может 
превышать некоторой величины, то стек называют ограниченным, а максимальное 
число элементов в нем — глубиной стека. Стек, в котором нет ни одного 
элемента, называется пустым. 

    Исполнитель «Стековый калькулятор» (СК.), 

    Пример 3. Система предписаний: 
    1. начать работу 
    2. добавить <вх: число> в стек 


    I. ОСНОВНЫЕ ПОНЯТИЯ ПРОГРАММИРОВАНИЯ     17 


    3. сложить/вычесть/умножить/разделить 
    4. показать результат 
    5. кончить работу 
    Запись «добавить <вх: число) в стек» означает, что это предписание 
имеет один входной объект (входной параметр), который является числом. 
    Исполнитель «Стековый калькулятор» имеет два глобальных объекта: стек 
чисел (т. е. стек, элементами которого являются числа) и табло, на котором по 
предписанию «показать результат» изображается вершина стека (сам стек при 
этом не меняется). 
    После вызова предписания «начать работу» стек калькулятора пуст, а на 
табло ничего не изображено. Предписание «добавить <вх: число> в стек» 
добавляет указанное при вызове число в стек. Предписание «показать результат» 
изображает на табло вершину стека. После этого табло не меняется до следующего 
вызова предписания «показать результат». При выполнении арифметических 
операций (сложить, вычесть, умножить, разделить) Стековый калькулятор достает 
из стека последовательно сначала правый, а затем левый аргументы операции, 
выполняет операцию и полученный результат помещает в стек (рис, 1.5), 


    Рис.    1.5 

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

    Пример программы для Стекового калькулятора: 

    программа вычисление 
    . дано       : 
    . получить: | значение формулы 5*(7 + 8) + 25 на табло СК
    .----------------
    .  СК.начать работу 
    .  СК.добавить <5> в стек 


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


    .  СК-добавить {7) в стек 
    .  СК-добавить (8) в стек 
    .  СК. сложить 
    .  СК. у множить 
    .  СК.добавить (25) в стек 
    .  СК. сложить 
    .  СК-показать результат 
    .  СК.кончить работу 
    конец программы 

    Последовательные  состояния  стека  при  выполнении  этой программы 
изображены на рис. 1.6. 


    Рис.    1.6 

    Конец примера 3. 

    Исполнитель «Счетчик», 

    П р и м е р 4. Система   предписаний: 

    1. начать работу 
    2. установить в нуль 
    3. увеличить на единицу 
    4. показать значение 
    5. кончить работу 

    Исполнитель имеет два глобальных объекта: внутренний, состоянием которого 
может быть неотрицательное целое число, и табло, на котором по предписанию 
«показать значение» это число изображается. Семантика предписаний очевидна из 
их названий, 
    Пример программы для исполнителя «Счетчик»: 
   
    программа три 
   . дано         :
   . получить : | на табло Счетчика число 3 
   .-----------------
   .  Счетчик.начать работу 
   .  Счетчик.установить в нуль 
   .  Счетчик.увеличить на единицу 
   .  Счетчик.увеличить на единицу 
   .  Счетчик.увеличить на единицу 
   .  Счетчик.показать значение 
   .  Счетчик.кончить работу 
    конец программы 

    Конец примера 4. 

    2. УПРАВЛЯЮЩИЕ КОНСТРУКЦИИ и УТВЕРЖДЕНИЯ  19

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

    1. Напишите программу для исполнителя «Резчик металла», вырезающую в листе 
металла номер Вашего дома. 
    2. Напишите программу для исполнителя «Стековый калькулятop», которая 
вычисляет значение формулы 5—(6 + 8/(7 — 5))+1, 
    3. Напишите программу для Стекового калькулятора, которая показывает на 
табло год Вашего рождения. 
    4. Решите задачу 3 при условии, что в программе в предписаниях 
«добавить <вх: число> в стек» можно использовать только однозначные числа от 0 
до 9. 
    5. Придумайте какого-нибудь исполнителя. Опишите его систему предписаний, 
глобальные объекты. Напишите две существенно разные программы для этого исполнителя, 
