    4. Процесс разработки программ. Рекурсия, итерация, проектирование 
цикла с помощью инварианта 

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

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

являются прямым результатом труда программиста. Результатом труда 
программиста является программа — текст R(Резчик сита, Резчик металла). 
    Естественно программист — «поставщик» этого текста — должен гарантировать 
его качество, в частности гарантировать, что изготовленный с его помощью 
Резчик сита будет резать то, что надо. Но это не единственное требование к 
качеству текста R (А, Е). Другими требованиями являются понятность текста для 
человека (в частности, возможность быстро убедиться в ёго правильности), а 
также возможность его модификации. Последнее требование вызвано тем что на 
практике редко удается ограничиться написанием одного варианта R (А, Е). Рано 
или поздно оказывается, что требования к А изменились. Для Резчика сита 
несколько возможных изменений описаны в упражнении 3 предыдущего раздела. 
Конечно, можно для каждого нового варианта задачи создавать R(A, E) заново с 
нуля. Однако, если новый вариант близок к старому, выгоднее взять старый текст 
R (A, E) и изменить его. Необходимость изменения внешнего описания или 
реализации исполнителя часто возникает и по внутренним причинам. В процессе 
решения задачи мы можем, например, придумать промежуточного исполнителя X, 
реализовать его на базе Y, а в дальнейшем по каким-то соображениям решить, что 
надо было использовать не X, а близкий к нему исполнитель X'. Тогда придется 
изменить R(X, Y) и все реализации, использующие X. 
    Таким образом, программа как минимум должна быть правильной, понятной и 
легко изменяемой. Методам эффективного создания таких программ посвящена вся 
эта книга. Разработка программы «в целом» описана в предыдущем разделе 
(технология «сверху вниз»). В этом разделе мы займемся более узкой задачей — 
реализацией одной отдельно взятой программы. 
    Разбиение задачи на подзадачи. При работе по технологии «Сверху вниз» к 
моменту реализации программы уже известны ее имя и дано/получить. Задача 
состоит в написании текста, который из любых условий, удовлетворяющих дано, 
переводит каких-то исполнителей в состояния, удовлетворяющие "получить". 
    Обычно реализация одной программы — это не очень длинный текст (20—30 
строк). Было бы замечательно, если бы можно было придумать и записать этот 
текст единым махом, в результате некоего «озарения». Было бы также 
замечательно, если бы уже написанный текст можно было мгновенно понять. На 
практике этого обычно, увы, не происходит: мы придумываем, записываем и 
понимаем текст программы не сразу, а по частям, в результате целенаправленной 
деятельности. Качество текста программы во многом определяется тем, в какой 
степени ключевые моменты нашего обду-

    4. ПРОЦЕСС РАЗРАБОТКИ ПРОГРАММ 45 

мывания находят отражение (пусть неполное) в окончательном тексте программы. 
    Рассмотрим еще раз задачу написания программы «в левый верхний угол 
металла». Самая первая идея решения состояла в том, чтобы сначала перевести 
резак в левый верхний угол стола, а затем уже попадать в левый верхний угол металла. 
    Фраза «сначала перевести резак в левый верхний угол стола, а затем...», 
однако, относится к процессу выполнения программы, а не к ее тексту. Если 
рассуждать в терминах текста программы, то нужно говорить так: программа 
будет состоять из двух фрагментов — А и Б. Фрагмент А будет обладать следующим 
свойством: если перед выполнением фрагмента будут выполнены условия, 
указанные в дано, то после его выполнения будет выполнено условие «резак в 
левом верхнем углу стола». Фрагмент Б будет обладать (тем свойством, что если 
перед его выполнением выполнено условие «резак в левом верхнем углу стола», то 
после будет выполнено условие, записанное в "получить":

    программа в левый верхний угол металла 
    . дано       : | на столе Резчика есть металл, резак поднят 
    . получить: | резак в левом верхнем углу листа металла 
    .   фрагмент А 
    .      утв: РМ.резак у левого края стола и 
    .	РМ.резак у верхнего края стола 
    .	| т. е. резак в левом верхнем углу стола 
    .   фрагмент Б 
    конец программы 

    Тем самым исходная задача реализации программы «в левый верхний угол 
металла» оказалась разбитой на две подзадачи — реализации фрагментов А и Б. 
Для каждой подзадачи (фрагмента программы) условие, которое должно быть 
достигнуто после выполнения фрагмента, называется постусловием, а условие, 
которое известно до выполнения, — предусловием. Таким образом, для фрагмента 
программы А выписанное выше утверждение является пост условием, а 
дано.— предусловием. Для фрагмента программы Б "получить" является 
постусловием, а утверждение — предусловием. Если всю программу рассмотреть как 
единый фрагмент, то ее постусловием является получить, а предусловием—дано.	; 
Фрагменты А и Б можно теперь обдумывать и реализовывать независимо, по 
очереди. Само разбиение на фрагменты А и Б зафиксировано в тексте программы 
в виде строк 

    46 ГЛ. I. НАЧАЛА ПРОГРАММИРОВАНИЯ 
    1. ПРОЦЕСС РАЗРАБОТКИ ПРОГРАММ 

    утв: РМ.резак у левого края стола и 
           РМ.резак у верхнего края стола 
    | т. е. резак в левом верхнем углу стола 

    Это утверждение имеет двоякое назначение. Во-первых, при чтении программы 
человеком оно дает представление об общем ходе решения, описывает состояние 
резака, которое будет к этому моменту получено. Во-вторых, формальная часть 
этого утверждения будет проверяться всякий раз после выполнения фрагмента А. 
Если фрагмент А реализован неправильно и в какой-то ситуации утверждение 
окажется невыполненным, то Универсальный Выполнитель немедленно прекратит 
выполнение программы и сообщит об ошибке. Итак, первый вывод состоит в том, 
что при разработке программы ее следует разбить на основные этапы (подзадачи) 
и сформулировать условия, которым будут удовлетворять промежуточные между 
подзадачами положения. Эти условия затем надо рассматривать как пост- и 
предусловия при разработке частей (фрагментов) программы. Другими словами, 
разработка программы в целом состоит в разработке последовательности 
утверждений (начиная с дано и кончая получить), служащих пост- и предусловиями 
ее частей. 
    К реализации каждого из фрагментов можно, в свою очередь, применить тот же 
подход, т. е. разбить их на подподзадачи и т. п. Разумеется, процесс разбиения 
на подзадачи должен заканчиваться. Решение очередной подзадачи при этом 
записывается либо в виде вызова какой-то другой программы, либо 
непосредственно с помощью управляющих конструкций и иных возможностей 
Универсального Выполнителя. 
    Правильность программы в целом зависит от 1) корректности сведения 
программы к подзадачам и 2) правильности реализации подзадач. Этими вопросами 
можно заниматься независимо: при сведении задачи к подзадачам можно не думать 
об их реализации, при проверке реализаций можно не думать, как они используются. 

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

    Вызовы программ и дано/получить. В случае, есля подзадачу Ф с известными 
пост- и предусловиями можно решить с помощью вызова уже существующей программы 
или предписания П, то фрагмент Ф сводится к одной строчке—вызову этой 
программы. Слова «можно решить» означают, что программа П обладает следующими 
двумя свойствами (назовем их «условия корректности вызова») :
    1) предусловие Ф => дано П, т. е. П применима в ситуации, когда выполнено 
предусловие П; 
    2) получить П ==>  постусловие Ф, т, е. выполнение П гарантирует постусловие. 
    Возможен, однако, случай, когда для решения подзадачи Ф готовой программы 
нет, но желательно ее создать. Такое выделение подзадачи в отдельную 
программу обычно происходит, если подзадача: а) достаточно сложна; б) 
используется при решении нескольких задач; в) естественно относится к 
какому-то исполнителю (например, любую программу, оперирующую с рядами ячеек 
в целом, разумно отнести к Обработчику рядов). В этом случае надо не только 
записать вызов программы, но и придумать ее имя и дано/получить. Рассмотрим, 
как это делается на примере фрагмента Б. 
    Выбор имени. Прежде всего для этой программы нужно придумать имя, коротко 
описывающее назначение и условия применения программы. Проблема выбора имени 
тем, актуальнее, чем больше размер программы. Если имена предписаний 
промежуточных исполнителей не будут достаточно полно отражать их назначение, 
то придется постоянно перечитывать их дано/получить, и мы не сможем эффективно 
создавать и модифицировать тексты программ. Посмотрите, например, как будет 
выглядеть программа «в левый верхний угол стола» (разд. 2), если заменить все 
имена на однобуквенные и убрать все комментарии: 

    программа А 
    .  дано      :
    .  получить: 
    .  цикл пока Х.не В выполнять 
    .  .  Х.С 
    .  конец цикла 
    .  утв: Х.В 
    .  цикл пока Х.не D выполнять 
    .  .  Х.Е 
    .  конец цикла 
    .  утв: Х.В и X.D 
    конец программы 

    Поэтому выбираемое имя должно довтаточао точно описывать программу. 
Назовем, например, программу, решающую подзадачу Б, 

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

    «из левого верхнего угла стола в левый верхний угол металла». 
    Формулировка дано/получить.  Программа, решающая подзадачу Б, должна 
удовлетворять условиям 
    1) предусловие Б ==> дано, 
    2) получить ==> постусловие Б. 
    Поэтому проще всего взять в качестве дано/получить пред- и постусловия Б, 
после чего мы придем к задаче реализации программы с известными 
дано/получить: 

.программа из левого верхнего угла стола 
.	    в левый верхний угол металла 
.  дано        : РМ.резак у левого края стола и 
                     РМ.резак у верхнего края стола 
                   | на столе у Резчика есть металл 
. получить: РМ.резак над металлом | в левом верхнем углу листа 

    Обычно, однако, одна и та же программа П вызывается в разных местах для 
решения, вообще говоря, разных подзадач Ф, Ф' и Ф" и т. д. Условия 
корректности должны выполняться для всех вызовов. Даже если программа П 
используется в одном месте, то при изменениях в программе может понадобиться 
использовать ее где-то в другом. Об этом тоже лучше позаботиться заранее. 
Наконец, попадем ли мы при решении подзадачи Ф в ситуацию, когда подходящая 
программа уже есть, или в ситуацию, когда ее надо создать, решающим образом 
зависит от дано/получить уже существующих программ. 
    Тем самым желательно, чтобы одна и та же программа Я была применима для 
решения возможно большего числа подзадач — как и тех, которые уже возникли, 
так и тех, которые гипотетически могут возникнуть потом. Для этого нужно, 
чтобы дано П следовало из как можно большего числа различных предусловий, а из 
получить П следовало как можно большее число различных постусловий. Или, 
говоря математическим языком, надо максимально ослабить дано и максимально 
усилить получить. 
    Замечание. Для того чтобы человеку было удобно работать с программой, ее 
дано/получить должны быть возможно более общими, естественными и легко 
запоминающимися. Как правило, ослабление упрощает, а усиление усложняет 
условие. Кроме того, на практике одна и та же программа обычно используется 
для решения подзадач с совпадающими (или почти совпадающими) постусловиями, но 
с довольно различными предусловиями. Поэтому усиление "получить" разумно лишь до 
тех пор. пока это не приводит к появлению и нагромождению деталей.

    4. ПРОЦЕСС РАЗРАБОТКИ ПРОГРАММ 49 

    Резюме. Выделив решение подзадачи Ф в отдельную программу, придумав ей имя 
и сформулировав черновой вариант ее дано/получить (дано = предусловие Ф, 
получить = постусловие Ф), надо попробовать максимально ослабить дано и, быть 
может, усилить "получить" так, чтобы программа была применима при возможно 
более общих, естественных и легко запоминающихся условиях. Образно говоря, 
программа должна давать максимум отдачи при минимуме затрат. 

    Пример. Пусть возникла следующая подзадача Ф: 

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

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

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

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

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

    Естественно, что ослаблять дано, усиливать получить и придумывать имя 
программы можно по-разному. В той же самой подзадаче 

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

Ф, например, можно было оставить в дано только информацию о расположении 
Путника относительно препятствия: 

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

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

    Рассмотрим пример. Пусть надо написать следующую программу

    программа расстояние до препятствия 
   .  дано        : | Путник где-то, лицом на восток 
   .  получить : | Путник там же, лицом на запад, в Счетчике — 
                         | расстояние от Путника до ближайшего препятствия 
                         | на восток (т. е. число свободных клеток между 
                         | Путником и препятствием восточнее него) 

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

    Счетчик.установить в нуль 
    Путник.повернуться на запад 

    Если же клетка восточнее Путника свободна, то можно сделать шаг на восток 
после чего искомое в задаче расстояние можно

    4. ПРОЦЕСС РАЗРАБОТКИ ПРОГРАММ 61 

вычислить как расстояние от нового положения Путника, увеличенное на 1. 
Таким образом, в этом случае мы можем написать: 

    Путник, сделать шаг 
         утв: (Путник на шаг восточнее,  лицом на восток 
    фрагмент А 
        утв: | Путник там же, лицом на запад, в Счетчике —* 
               | расстояние до препятствия 
    Путник.сделать шаг 
       утв: | Путник в исходном положении, лицом на запад 
    Счетчик. увеличить на единицу 
       утв: | в Счетчике — расстояние от исходного положения 
               | до препятствия на востоке	

    Обратите внимание на подзадачу А. Мы можем решать эту подзадачу с помощью 
вызова другой программы — с уже сформулированными дано/получить. Такая 
программа есть, и это программа «расстояние до препятствия». Действительно, 
так как предусловие А ==> дано этой программы, а получить ==> постусловие А, 
то вызов программы «расстояние до препятствия» для решения подзадачи А 
является корректным: 

    программа расстояние до препятствия 
    . дано :        | Путник где-то, лицом на восток 
    . получить: | Путник там же, лицом на запад, в Счетчике — 
    .                   | расстояние от Путника до ближайшего препятствия 
    .	     | на восток (т, е. число свободных клеток между 
    .                  | Путником и препятствием восточнее него) 
    .  если Путник, впереди занято 
    .  .  то 
    .  .    Счетчик.установить в нуль 
    .  .    Путник, повернуться на запад 
    .  .  иначе 
    .  .    Путник, сделать шаг 
    .  .       утв: | Путник на шаг восточнее, лицом на восток 
    .  .    расстояние до препятствия 
    .  .        утв: | Путник там же, лицом на запад, в Счетчике — 
    .  .	      | расстояние до препятствия 
    .  .   Путник, сделать шаг 
    .  .       утв: | Путник в исходном положении, лицом на запад 
    .  .    Счетчик.увеличить на единицу 
    .  .       утв: | в Счетчике  — расстояние от исходного 
    .  .	    | положения до препятствия на востоке 
    .  конец если 
    конец программы 
  

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

    Эта программа корректна. Но является ли она правильной? Как мы знаем, 
корректная программа П является правильной, если все вызываемые из нее 
программы правильны. Но в данном случае среди вызываемых есть и сама 
программа П. Как же узнать, правильна она или нет? 
    Рассмотрим работу Универсального Выполнителя при вызове программы В из 
программы А. Если каждую программу представлять себе записанной на отдельном 
листке бумаги, то работа УВ состоит в том, что он помечает на листке А точку 
(место) приостановки, откладывает листок А в сторону и начинает выполнять 
программу В. Если в В встречается вызов программы С, то УВ помечает точку 
приостановки на листке В, кладет его сверху на листок А и начинает выполнять 
программу С и т. д. При завершении выполнения очередной программы, например 
программы С, УВ берет верхний листок из стопки отложенных и продолжает 
выполнение записанной на нем программы (в данном случае программы В), 
начиная с помеченной точки. При завершении выполнения программы В из стопки 
берется листок с программой П и т. д. до тех пор, пока вся стопка не 
исчерпается. Таким образом, стопка листков с приостановленными программами 
образует стек. 
    В случае рекурсивного вызова программой X себя УВ также помечает точку 
приостановки и кладет листок с программой Х  в стек приостановленных программ. 
После этого он берет другой точно такой же листок (мы будем говорить— другой 
экземпляр программы X) и начинает выполнять то, что на нем написано, т. е. 
программу X с начала. При следующем рекурсивном вызове УВ положит второй 
экземпляр X в стек и начнет выполнять третий и т. д. до тех пор, пока при 
завершении выполнения очередной программы не окажется, что стек уже пуст. 
    Объяснение работы УВ в терминах стека листков с приостановленными 
программами, впрочем, не совсем точно. Реально нет необходимости помещать в 
стек программы целиком или переписывать их на новые листки при рекурсивных 
вызовах — достаточно запоминать в стеке лишь имена приостановленных программ 
и точки их приостановки. 
    Посмотрим теперь, что происходит при выполнении программы «расстояние до 
препятствия», если в начальный момент Путник находится за две клетки до 
препятствия (рис, 4.1). 
    Каждый раз программа вызывается с другими исходными данными (другим 
положением Путника). Вопрос о правильности работы программы при конкретных 
исходных данных сводится к вопросу о правильности работы программы при других 
исходных данных и т. д. вплоть до правильности работы программы в ситуации, 
когда препятствие находится непосредственно перед Путником.
 
    4. ПРОЦЕСС РАЗРАБОТКИ ПРОГРАММ 53 

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


    Рис. 4.1 

    Таким образом, единственная опасность рекурсивной реализации состоит в 
том, что программа потенциально может вызывать себя бесконечно. Чтобы этого не 
произошло, нужно придумать какое-то рассуждение, гарантирующее, что выполнение 
программы рано или поздно закончится. В данном случае каждый новый вызов 
происходит ближе к препятствию, чем предыдущий 
    Так как расстояние до препятствия конечно, то рано или поздно выполнение 
программы завершится. 
    Обратите внимание, что мы запрограммировали некоторый повторяющийся 
процесс, т. в, рекурсия является еще одним (наряду с циклами) средством 
программирования повторяющихся процессов. 
    Конструкции циклов. Программирование повторяющихся процессов, когда 
короткая программа описывает длинную последовательность действий, требует 
особого и пристального внимания. При возникновении такой задачи разумно 
попытаться свести ее к какой-нибудь из базисных схем обработки информации. 
одна из таких схем — рекурсия — была описана выше. Сейчас мы приведем еще 
две: итерацию и схему проектирования цикла с помощью инварианта. 
Другие схёмы — схема вычисления инвариантной функции и схема индуктивного 
вычисления функции на пространстве последовательностей— будут изложены в 
разд. 6 и 8. 

    Итерация. Изложение метода итераций начнем с математической модели. 
    Пусть М. — некоторое множество, 
    Р: М --> {да, нет}—предикат на М, т. е. отображение М в множество из двух 
элементов: да и нет, 
    М \ Р = { х из М : Р (х) = нет} — множество тех элементов х из М, для которых 
Р(х) = нет.	; 
    Требуется найти элемент х из М такой, что Р (х) = да. 

    Метод итераций (дословно — повторений) состоит в том, что строится 
некоторое преобразование (отображение) Т: М \ Р --> М и это преобразование 
последовательно применяется, начиная с какого-то х0 из М: 

    x1 = T(x0), x2 = T(x1),   ... хn =Т(хn — 1) .... 


    54 ГЛ. !, НАЧАЛА ПРОГРАММИРОВАНИЯ 

до тех пор, пока мы впервые не получим xi такое, что Р(хi)=да 
(естественно, должна быть уверенность, что рано или поздно такое xi найдется). 
    Графически метод представлен на рис. 4.2. 
    С программистской точки зрения, если в цикле меняются К объ-ектов, то М = 
m1*m2* ... *mK, где mi—множество состояний i-ro объекта, а знак * означает 
прямое (декартово) произведение множеств. Соответственно х0, x1, ,,,, хn, ... 
—это какие-то конкретные наборы состояний объектов, а Р— описание состояния, 
которого мы хотим достичь (наша цель). 
    Конечно в такой формулировке в терминах метода итераций можно описать 
любой цикл: всегда есть какие-то объекты (х), 

    Рис. 4.2. Метод   итераций 

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

     цикл пока Путник.впереди свободно
         выполнять	


    4. ПРОЦЕСС РАЗРАБОТКИ ПРОГРАММ 55 


       Путник, сделать шаг      
    конец цикла 

    Пример 2. Пусть в прямоугольном квадранте произвольным образом расположены 
препятствия любой формы и есть хотя бы одна свободная клетка. Свободную клетку 
будем называть угловой, если в ней можно расположить Путника так, что впереди 
и справа от него будут две занятые клетки. Требуется написать программу, 
которая переводит Путника из произвольной свободной клетки в угловую. 
    Приведем два решения этой задачи методом итераций с разными М, Р и Т. 
    Решение 1. В качестве М возьмем множество всех свободных клеток квадранта. 
Для клетки m из М положим Р(m)=да тогда и только тогда, когда клетки севернее и 
восточнее m заняты. Таким образом, из Р(m) следует, что клетка m является 
угловой, Преобразование Т: М \ Р --> М определим так: 

   T(m) =    ( клетка севернее m, если она свободна, 
                  ( клетка восточяее m в противном случае. 

    Если теперь отождествить клетку m из М с положением Путника в этой клетке 
с ориентацией на север, то предикат Р можно записать в виде «Путник.впереди 
занято и Путник.справа занято»; получение какой-нибудь точки m0 из М — в виде 
«Путник.повернуться на север>; а преобразование Т — в виде: 

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

    Программа в целом, таким образом, запишется так:

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

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

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

    Завершение этой программы за конечное число шагов гарантируется тем, 
что сумма расстояний от Путника до северной и восточной стен квадранта 
уменьшается на 1 при каждом выполнении тела цикла. 
    Решение2. В качестве М возьмем множество таких свободных клеток, севернее 
или восточнее которых есть занятая клетка. Предикат Р (нашу цель) оставим 
таким же, как в предыдущей задаче. Клетку m из М отождествим с положением 
Путника в этой клетке (независимо от ориентации). Преобразование Т зададим так:

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

    Получение m0 из М можно записать так:

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

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

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

    М — некоторое множество, 
    Р: М --> {да, нет} — предикат на М, т. е. отображение М в множество из двух 
элементов: да и нет, 
    М \ Р = { х из М: Р(х) = нет} — множество тех элементов х из М, для которых 
Р(х)=. нет, 
    Т: М \ P --> M - некоторое преобразование. 


    4. ПРОЦЕСС РАЗРАБОТКИ ПРОГРАММ 57 

    И пусть существуют отображения  (предикаты) 

    I : М --> {да, нет}  (инвариант), 
   Q: М --> {да, нет} (условие окончания) 

такие, что 

    1) I(х) и Q(x) ==> P(x), 
    2) I(х0) = да {инвариант выполнен для начального состояния объектов), 
    3) I(х)= да ==-> I(Т(х)) = да (инвариант сохраняется при преобразовании Т), 
    Тогда в методе итераций в качестве условия окончания вместо Р(х) можно 
взять Q(x). 
    Графически эта схема представлена на рис. 4.3. 
    На практике решение задачи с заданными пост- и предусловиями по схеме 
проектирования цикла с помощью инварианта состоит 

    Рис. 4.3. Схема проектирования  цикла  с  помощью  инварианта 

в следующем. Прежде всего надо придумать общую стратегию решения задачи, 
т. е. неформально решить, что будет происходить в цикле, а также описать 
объект или объекты, которые будут меняться при его выполнении. Далее надо: 
   1) сформулировать условие окончания Q — условие, при выполнении которого цикл 
должен закончиться; 
    2) попытаться описать взаимосвязи между изменяющимися в ходе выполнения 
цикла объектами в виде неизменного условия — инварианта I. 
    Если это удалось, то решение задачи можно записать в виде: 

      утв: предусловие 
   фрагмент А  
   цикл
   .  инв: I 

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

    .  пока не Q
    .  выполнять 
    .    фрагмент Б 
    конец цикла 
    фрагмент В 
       утв: постусловие 

    После чего останется: 
    A) обеспечить  выполнение   инварианта   перед  началом   цикла;
    Б) придумать тело цикла, сохраняющее инвариант, и убедиться, что цикл рано или 
поздно закончится; 
    B) обеспечить выполнение постусловия после окончания цикла. 
    (Запись  инв   между   цикл   и   пока   является   синонимом   утв и 
означает, что утверждение I будет проверяться каждый раз перед 

    Рис.   4.4 

проверкой условия в пока, т. е. что I выполнено перед и после каждого шага 
цикла, включая первый и последний.) 
    Пример. Пусть известно (это предусловие), что Путник находится у западного 
края квадранта, лицом на восток, и что горизонтальный ряд клеток, в котором 
находится Путник, свободен от препятствий (рис. 4.4). 
    Над Путником находится полоса препятствий, т. е. несколько прямоугольных 
препятствий одинаковой высоты, но, быть может, 
    
    Рис.   4.5 

разной ширины. Препятствия могут прилегать, а могут и не прилегать к 
западной и восточной стенам квадранта. В полосе может и не быть ни одного 
препятствия или, наоборот, не быть ни одного прохода. 
    Надо (это постусловие), чтобы Путник оказался у восточной стены, а в 
Счетчике получилось число препятствий в полосе (в ситуации, изображенной на 
рис. 4.5, в Счетчике должно быть число 5). 
---------------------------------------------------------------------------------------------------------------------
    Остановитесь на минутку и, прежде чем читать дальше, попробуйте решить 
эту задачу самостоятельно, сначала как-нибудь, а 

    4. ПРОЦЕСС РАЗРАБОТКИ ПРОГРАММ 59 

    затем применив схему проектирования цикла с помощью инварианта. Достаточно 
будет, если Вы сделаете это в уме, прикинув, какое у Вас будет условие 
окончания цикла, каково будет начальное, конечное и промежуточные положения 
Путника и т. д. Напомним, что пользоваться можно только управляющими 
конструкциями разд. 2 в предписаниями Путника и Счетчика. 
------------------------------------------------------------------------------------------------------------------------
    Применим схему проектирования цикла с помощью инварианта. Первое, что надо 
сделать, это сформулировать общую стратегию и описать меняющиеся объекты. 
Общая стратегия очевидна — идти на восток и «по дороге» считать число 
пройденных препятствий. Оставим стратегию пока в таком виде, никак ее не 
уточняя, и опишем меняющиеся объекты. Таких объектов два: положение Путника и 
значение Счетчика. 
    Второе — надо попытаться описать цикл в терминах условия окончания Q и 
инварианта I. С условием окончания просто — остановиться надо у восточной 
стены квадранта, т. е. как только клетка впереди Путника окажется занятой. 
Обратите внимание, что мы не только сформулировали условие окончания, но и 
формально выразили его через предписания Путника. Если бы это оказалось 
невозможным, то от этого условия окончания пришлось бы отказаться и 
придумывать другое. 
    Итак, дело за инвариантом. Как связаны между собой положение Путника и 
значение Счетчика? Стратегия подсказывает; в Счетчике должно быть число 
препятствий в пройденной части полосы. Но включать или нет в пройденную часть 
клетку над Путником? Для решения этого вопроса надо посмотреть на конечное 
состояние (рис. 4.5). В этот момент в Счетчике должно оказаться общее число 
препятствий в полосе, и потому клетку над Путником в пройденвую часть включать надо. 
    Мы сформулировали I и Q. Легко видеть, что в данном случав 
постусловие =  ( I и Q), и решение задачи можно записать в виде:

       утв: предусловие 
   фрагмент А 
   цикл
   .   инв: | в Счетчике число препятствий в пройденной 
   .           |части полосы 
   .  пока Путник, впереди свободно 
   .  выполнять                                 
   .  фрагмент Б 
    конец цикла 
    утв: | в Счетчике число препятствий в пройденной 
            | части полосы и вся полоса пройдена 

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

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

единичную ширину? И что значат эти состояния, если препятствие В полосе 
вообще нет? 
    Система предписаний Путника такова, что условием окончания цикла может 
быть только одно — «впереди занято», т. е. Путник в клетке у восточной стены. 
Препятствие над ним в этот момент может быть, а может и не быть — конечное 
положение вообще никак не связано с препятствиями. Значит, решение двигаться 
от препятствия к препятствию является неверным 
    Попробуем двигаться просто от клетки к клетке. Тогда начальное положение 
Путника — у западной стены, конечное —у восточной, а промежуточные — 
последовательно по всем клеткам слева направо (с запада на восток). 
    Подзадача А становится тривиальной — надо поместить в Счетчик число 
препятствий в пройденной части полосы, т, е, 

    Счетчик, установить в нуль	
    если Путник.слева занято 
    .  то 
    .    Счетчик.увеличить на единицу 
    конец если 

    Внутри цикла надо переместить Путника на шаг вправо и при этом сохранить 
инвариант. Посмотрим, когда при таком перемещении число препятствий в 
пройденной части полосы изменяется. Это происходит в единственном случае —если 
после шага Путник оказывается под первой (левой) клеткой нового препятствия, 
т. е. ,если до шага слева было свободно, а после шага — занято. Так как наши
действия зависят от, того, было ли до шага слева занято или

    4. ПРОЦЕСС РАЗРАБОТКИ ПРОГРАММ 61 

свободно, то надо решать эту задачу с помощью конструкции выбора: 

    выбор 
    .    при Путник.слева занято ==> фрагмент Б1 
    .    при Путник.слева свободно => фрагмент Б2 
    конец выбора 

    Мы получили две новые подзадачи: Б1—переместить Путника на шаг вправо и 
сохранить инвариант при условии, что до шага слева было занято, и Б2 — то же 
самое, но при условии, что до шага слева было свободно. 
    Решаем задачу Б1. Если до шага было занято, то число препятствий в 
пройденной части полосы после шага измениться не может. Таким образом, Б1 это просто 

    Путник.сделать шаг 

    В задаче Б2 число препятствий может увеличиться на 1, если после шага 
Путник окажется под первой клеткой нового препятствия, т. е. если слева 
окажется занято. Таким образом, задача Б2 решается так: 

    Путник.сделать шаг 
    если Путник.слева занято 
    .  то 
    .    Счетчик, увеличить на единицу 
    конец если 

    Окончательное решение задачи выглядит так: 

    Счетчик.установить в нуль 
    если Путник.слева занято 
    .  то 
    .   Счетчик.увеличить на единицу 
    конец если 
    цикл 
    .  инв: | в Счетчике — число препятствий в пройденной 
               |части полосы 
    .  пока Путник, впереди свободно 
    .  выполнять 
    .  выбор 
    .  .   при Путник.слева занято => Путник, сделать шаг 
    .  .   при Путник.слева свободно =>
    .  .	Путник.сделать шаг 
    .  .          если Путник.слева занято 
    .  .          то

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

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

    Замечание I. Выше описано, как примерно должен думать человек при 
создании программы и какой текст при этом он должен писать. Нужно понимать, 
что цель при этом преследуется сугубо практическая — научиться писать 
несложные программы быстро и без ошибок, а более сложные с минимальным 
количеством ошибок. При применении изложенной выше методики на практике не 
следует впадать в крайности и доказывать очевидные вещи или разбивать задачу 
на мельчайшие подзадачи. Если промежуточные утверждения, инварианты циклов и 
прочее помогают писать программу быстро и без ошибок, их следует применять. 
Если же они только загромождают текст программы и ничего не проясняют, надо 
обходиться без них. По мере накопления опыта многие вещи начинают делаться в 
уме, и это совсем не плохо. Вместе с тем даже в самых простых задачах часто 
обнаруживается масса «подводных камней». Поэтому при малейших сомнениях в 
правильности программы следует пытаться взглянуть на нее с более фррмальцых, 
чем обычно, позиций.. 
    Замечание 2. Выписываемые в программе дано/получить, инварианты и 
утверждения, как правило, являются неполными. Какие-то детали всегда считаются 
известными. При учете всех деталей утверждения становятся громоздкими, плохо 
понимаемыми и начинают не помогать, а мешать. 
    Замечание 3. В конструкциях дано, получить и утверждение записываются как 
комментарии, предназначенные для человека, так и формальные условия, 
проверяемые Универсальным Выполнителем при выполнении программы. Включение 
формальных условий в текст программы сильно снижает вероятность того, что 
программа с ошибками покажется работающей правильно. Поэтому формальные 
условия включают в программу часто даже в ущерб краткости и ясности текста, 

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

    Придумайте название и напишите программу со следующими дано/получить: 
    1 дано         : | Путник в северо-западном углу квадранта, 
    			   | в квадранте одно прямоугольное препятствие, 
                     | это препятствие не прилегает к стенам квадранта 
    получить      :  | B Счетчике - ширина препятствия 

    4. ПРОЦЕСС РАЗРАБОТКИ ПРОГРАММ 63 

    2. даио        : | Путник в северо-западном углу квадрата, 
                     | в квадранте одно прямоугольное препятствие, 
                     | это препятствие не прилегает к стенам квадранта 
      получить    :  | в Счетчике ~ периметр препятствия 
    3. дано       :  | в квадранте одно прямоугольное препятствие 
      получить    :  | в Счетчике — число препятствий, прилегающих к стенам квадранта 
    4. дано       :  | в квадранте два одноклеточных препятствия 
         получить :  | в Счетчике — периметр их объединения 
    5. дано       :  | в квадранте несколько прямоугольных препятствий, все они прилегают 
                     | к южной стене квадранта и не прилегают друг к другу и к другим стенам 
                     | квадранта	
        получить :   | в Счетчике — число препятствий
    6. дано	     :   | в квадранте несколько прямоугольных препятствий, все  они   
                     | прилегают  к   южной   стене  квадранта   и не   прилегают   
                     | друг   к   другу и к другим стенам квадранта 
       получить :    | в Счетчике — сумма ширин всех препятствий 
    7. дано     :    | в квадранте несколько прямоугольных препятствий, все 
                     | они прилегают к южной стене квадранта и не 
                     | прилегают друг к другу и к другим стенам квадранта 
       получить :    | в Счетчике — сумма высот всех препятствий 
    8. дано	    :    | в квадранте одно прямоугольное препятствие, не 
                     | прилегающее к стенам квадранта, Путник над его северным краем 
      получить  :    | Путник в той же клетке, в Счетчике — ширина препятствия 
    9. дано     :    | в квадранте одно прямоугольное препятствие, не 
                     | прилегающее к стенам квадранта, Путник у западной стороны 
                     | препятствия лицом на север 
      получить  :    | Путник на той же горизонтали у восточной стороны препятствия лицом 
                     | на юг 
    10. дано    :    | в квадранте несколько прямоугольных препятствий, не 
                     | прилегающих друг к другу и к стенам квадранта 
    получить    :    | в Счетчике — число препятствий, пересекающих горизонтальный 
                     | отрезок из клеток от Путника до восточной стены квадранта 
    Будем   называть  препятствие   шарообразным,  если   при   обходе 
его по часовой стрелке начиная с положения над северным краем препятствия 
сначала надо идти только на восток и на юг, потом 

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

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