ДРоботландский Университет 
2000/2001 учебный год
Курс 31 "Азы программирования"
Корректор
------------------------------------------------
     Р О Б О Т Л А Н Д С К О Е  П Р О Г Р А М М И Р О В А Н И Е

                                  (C) А.А. Дуванов

                                      Под редакцией
                                      Ю.А. Первина

                                      Пособие   распространяется
                                      только в рамках  Роботлан-
                                      дских  Курсов  и  является
                                      объектом авторского права.

                       К О Р Р Е К Т О Р


Глава 4. Приемы программирования Корректора

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

4.1. Как найти конец и начало.

   Папа. Итак, друзья, какой план работы у нас на сегодня?
   Петя.  У  меня есть несколько интересных идей, которые  могут
помочь в решении задач Корректора.
   Папа. Давай, послушаем.
   Петя. Часто при программировании Корректора приходится  уста-
навливать окно на начало или конец текста. Как это сделать?
   Папа. Что ты понимаешь под текстом?
   Петя. Ну,  как  всегда, это последовательность любых символов
на пустой ленте Корректора.
   Вася. А промежутки между словами тоже относятся к тексту?
   Петя. Да, название "текст" - это  условное обозначение произ-
вольной  последовательности символов  из  алфавита  исполнителя.
Среди символов,  составляющих  текст, не должно быть специальных
символов пустого места,  но могут быть пробелы, цифры или специ-
альные знаки, такие, как "+", "-", "%" или что-нибудь еще в этом
роде. Вот я нарисовал несколько примеров:
         ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
         │░│░│░│░│э│т│о│ │т│е│к│с│т│░│░│░│░│░│░│░│░│░│
         ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴
         ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
         │░│░│░│░│1│2│5│-│3│6│=│9│9│░│░│░│░│░│░│░│░│░│
         ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴
         ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
         │░│░│░│░│#│?│+│ │-│л│0│@│!│░│░│░│░│░│░│░│░│░│
         ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴

   Папа. Сформулируй задачу более четко.
   Петя. На  ленте записан некоторый текст. Требуется установить
окно на последний его символ. В начальный момент окно расположе-
но произвольно внутри текста.
   Вася. Понятно.  Решение  очень простое. Нужно перемещать окно
вправо, пока  в нем видны символы текста. Как  только в окне по-
явится пустая клетка - нужно переместить окно на одну ячейку на-
зад:
              ЭТО На_конец
               ПОКА НЕ ПУСТО ВПРАВО
               ВЛЕВО
              КОНЕЦ

   Петя. Верно. Это самое удачное решение, хотя можно предложить
и вариант с рекурсией:
              ЭТО На_конец
               ВПРАВО
               ЕСЛИ ПУСТО
                ТО ВЛЕВО
                ИНАЧЕ На_конец
              КОНЕЦ

   Вася. Это тоже понятно, но можно написать и по-другому:

              ЭТО На_конец
               ВПРАВО
               ЕСЛИ НЕ ПУСТО
                ТО На_конец
                ИНАЧЕ ВЛЕВО
              КОНЕЦ

4.2. Как вернуться в исходное место

   Папа. Вариант с рекурсией может помочь вернуть окно Корректо-
ра в исходное положение.
   Петя. Что ты имеешь в виду?
   Папа. Представьте себе такую задачу: на ленте записан текст и
окно установлено где-то внутри него. Требуется поставить в конце
текста точку и вернуть окно в  исходное  положение. Например, до
начала работы лента может выглядеть так:

         ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
         │░│░│░│░│я│ │-│ │р│о│б║о║т│░│░│░│░│░│░│░│░│░│
         ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴

   А после выполнения программы лента должна иметь вид:

         ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
         │░│░│░│░│я│ │-│ │р│о│б║о║т│.│░│░│░│░│░│░│░│░│
         ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴

   Вася. Я понимаю трудность. Поставить  в  конце  текста  точку
очень просто, но как вернуть  окно  назад? Ведь мы не знаем,  на
сколько клеток оно переместилось вправо. И я не  знаю, как здесь
может помочь рекурсия.
   Петя. Понятно! Можно использовать отложенную команду. Вспомни
наши занятия с Кукарачей: ему нужно было найти в столбце букву А
и вернуться в исходное положение.
   Вася. Честно говоря, я не помню.
   Петя. Ну, хорошо, оставим Кукарачу в покое. Вот решение нашей
задачи:
              // Поставить в конце текста
              // точку и вернуться назад
              ЭТО Точка
               ВПРАВО
               ЕСЛИ ПУСТО
                ТО ПИШИ .
                ИНАЧЕ Точка

               ВЛЕВО // Отложенная команда. Она
                     // выполнится столько раз, сколько
                     // выполнялась команда ВПРАВО.
              КОНЕЦ
   Вася. Мне кажется, что эта программа неверная. Точка действи-
тельно в конце текста будет поставлена, но окно  после этого пе-
реместится только на одну клетку влево и, конечно,  в общем слу-
чае, не вернется в исходное положение.

     Петя. Давай  разберемся не спеша... Первой выполняется ко-
манда ВПРАВО:

ЭТО Точка
┌───────┐
│ВПРАВО │                              ┬─┬─┬─┬─┬─┬─┬─┬─┬─╦═╦─┬─┬
└───────┘                              │░│я│ │-│ │р│о│б│о║т║░│░│
 ЕСЛИ ПУСТО                            ┴─┴─┴─┴─┴─┴─┴─┴─┴─╩═╩─┴─┴
  ТО ПИШИ .
  ИНАЧЕ Точка

 ВЛЕВО
КОНЕЦ

   Затем выполняется условная команда:

ЭТО Точка
┌───────┐
│ВПРАВО │
└──┬────┘
┌──┴──────────┐                        ┬─┬─┬─┬─┬─┬─┬─┬─┬─╦═╦─┬─┬
│ЕСЛИ ПУСТО   │                        │░│я│ │-│ │р│о│б│о║т║░│░│
│ ТО ПИШИ .   │                        ┴─┴─┴─┴─┴─┴─┴─┴─┴─╩═╩─┴─┴
│ ИНАЧЕ Точка │
└─────────────┘
 ВЛЕВО
КОНЕЦ

     Обрати внимание на  то,  что после выполнения условной ко-
манды должна выполняться команда, следующая за ней, то есть ко-
манда ВЛЕВО.
   Так   как   условие  ложно,   выполнение   условной   команды
равносильно выполнению  копии  процедуры Точка. Первая команда в
ней - перемещение окна вправо на клетку:

ЭТО Точка
┌───────┐
│ВПРАВО │                               ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─╦═╦─┬
└──┬────┘                               │░│я│ │-│ │р│о│б│о│т║░║░│
┌──┴──────────┐    ЭТО Точка            ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─╩═╩─┴
│ЕСЛИ ПУСТО   │   ┌─────────┐
│ ТО ПИШИ .   ├───┤ ВПРАВО  │
│ ИНАЧЕ Точка │   └─────────┘
└─────────────┘     ЕСЛИ ПУСТО
 ВЛЕВО               ТО ПИШИ .
КОНЕЦ                ИНАЧЕ Точка
                    ВЛЕВО
                   КОНЕЦ

   Далее интерпретатор анализирует условную команду. Так как ус-
ловие истинно, то выполнение условной команды равносильно выпол-
нению команды ПИШИ . из СКИ исполнителя:

ЭТО Точка
┌───────┐
│ВПРАВО │
└──┬────┘                               ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─╦═╦─┬
┌──┴──────────┐    ЭТО Точка            │░│я│ │-│ │р│о│б│о│т║.║░│
│ЕСЛИ ПУСТО   │   ┌─────────┐           ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─╩═╩─┴
│ ТО ПИШИ .   ├───┤ ВПРАВО  │
│ ИНАЧЕ Точка │   └──┬──────┘
└─────────────┘   ┌──┴──────────┐
 ВЛЕВО            │ ЕСЛИ ПУСТО  │
КОНЕЦ             │  ТО ПИШИ .  │
                  │  ИНАЧЕ Точка│
                  └─────────────┘
                    ВЛЕВО
                   КОНЕЦ

   Теперь выполняется команда ВЛЕВО, следующая за условной в ко-
пии процедуры Точка:

ЭТО Точка
┌───────┐
│ВПРАВО │
└──┬────┘                               ┬─┬─┬─┬─┬─┬─┬─┬─┬─╦═╦─┬─┬
┌──┴──────────┐    ЭТО Точка            │░│я│ │-│ │р│о│б│о║т║.│░│
│ЕСЛИ ПУСТО   │   ┌─────────┐           ┴─┴─┴─┴─┴─┴─┴─┴─┴─╩═╩─┴─┴
│ ТО ПИШИ .   ├───┤ ВПРАВО  │
│ ИНАЧЕ Точка │   └──┬──────┘
└─────────────┘   ┌──┴──────────┐
 ВЛЕВО            │ ЕСЛИ ПУСТО  │
КОНЕЦ             │  ТО ПИШИ .  │
                  │  ИНАЧЕ Точка│
                  └──┬──────────┘
                  ┌──┴───────┐
                  │ ВЛЕВО    │
                  └──────────┘
                   КОНЕЦ

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

ЭТО Точка
┌───────┐
│ВПРАВО │                               ┬─┬─┬─┬─┬─┬─┬─┬─╦═╦─┬─┬─┬
└──┬────┘                               │░│я│ │-│ │р│о│б║о║т│.│░│
┌──┴──────────┐    ЭТО Точка            ┴─┴─┴─┴─┴─┴─┴─┴─╩═╩─┴─┴─┴
│ЕСЛИ ПУСТО   │   ┌─────────┐
│ ТО ПИШИ .   ├───┤ ВПРАВО  │
│ ИНАЧЕ Точка │   └──┬──────┘
└─────────────┘   ┌──┴──────────┐
┌────────┐        │ ЕСЛИ ПУСТО  │
│ВЛЕВО   │<────┐  │  ТО ПИШИ .  │
└────────┘     │  │  ИНАЧЕ Точка│
КОНЕЦ          │  └──┬──────────┘
               │  ┌──┴───────┐
               └──┤ ВЛЕВО    │
                  └──────────┘
                   КОНЕЦ

   Вася. Вот теперь я, наконец, вспомнил этот головоломный прием
программирования, твои слова и схемы стали мне понятны.
   Петя. Я рад за тебя.
   Папа. А  я  рад  за вас обоих и немножко за себя - ведь я ваш
папа!

4.3. Специальные символы-флаги

   Петя. При  программировании  Корректора  часто приходится ис-
пользовать специальные  символы для для разных пометок, указате-
лей.  Я  называю такие символы флагами. Давайте решим  следующую
задачу:
   <<dubl1.txt, dubl2.txt>> Продублировать слово, записанное на
ленте. В начальный момент  окно  установлено на первый его сим-
вол.
   Вася. Точку в конце мы ставить умеем, но  можно записывать на
ленту не точку, а то что, находится в ящике!
   Папа. Хорошее рассуждение. Ты намекаешь на  то,  что  в  ящик
можно последовательно  копировать символы текста и переносить их
в конец?
   Вася. Конечно! Вот моя программа:

 ЭТО Дубль
  ПОКА НЕ ПУСТО
  {
    ЯЩИК+
    Перенести_символ
    ВПРАВО
  }
 КОНЕЦ

 // Эта процедура копирует символ из ящика
 // в конец текста и возвращает
 // окно в исходное положение
 ЭТО Перенести_символ
  ВПРАВО
  ЕСЛИ ПУСТО
   ТО    ЯЩИК-
   ИНАЧЕ Перенести_символ

   ВЛЕВО // Отложенная команда. Она
         // выполнится столько раз, сколько
         // выполнялась команда ВПРАВО.
 КОНЕЦ

   Папа.  Хорошая  задача. В ней без флага действительно  трудно
обойтись. Ведь твоя программа никогда не закончится!
   Вася. Почему?
   Папа. Копируя символы в конец, ты удлиняешь исходное слово, и
поэтому условие в цикле ПОКА никогда не будет ложным.
   Вася. Понимаю...
   Петя. Выход очень простой: поставить за исходным текстом спе-
циальный символ - флаг его конца.
   Папа. При этом приходится допускать, что такого символа-флага
в самом тексте нет.
   Петя. Ну,  я не думаю, что  это ограничение очень  сильное. В
качестве символа флага можно выбрать редко используемый символ и
честно  предупредить  пользователей  нашей программы, чтобы  они
этот символ не использовали для записи текста на ленту.
   Вася. Давайте в качестве флага использовать символ "|". Я во-
обще не знаю, для чего он нужен Корректору!
   Петя. Вот ты сам и нашел применение этому символу! Теперь алго-
ритм для решения нашей задачи примет следующий вид:

    Поставить флаг в конец слова
    Копировать слово за флаг
    Стереть флаг

   Вася. А вот как запишется главная процедура программы:

  ЭТО Дубль
   Поставить_флаг
   Копировать_слово
   Стереть_флаг
  КОНЕЦ

   Поставить флаг в конец текста и вернуться назад можно при по-
щи рекурсивной процедуры с отложенной командой ВПРАВО:

  ЭТО Поставить_флаг
   ВПРАВО
   ЕСЛИ ПУСТО
    ТО    ПИШИ |
    ИНАЧЕ Поставить_флаг
   ВЛЕВО
  КОНЕЦ

   Петя. Правильно, конечно, но  здесь  можно обойтись и без ре-
курсивных хитростей -  ведь положение окна нам известно: это на-
чало текста. Значит,  известно, куда надо вернуть окно после ус-
тановки флага.  Это  легко  программируется старым добрым циклом
ПОКА:

  ЭТО Поставить_флаг
   ПОКА НЕ ПУСТО ВПРАВО
   ПИШИ |
   ПОКА НЕ ПУСТО ВЛЕВО
   ВПРАВО
  КОНЕЦ

   Вася. Процедура Копировать_слово будет дублировать символы до
тех пор, пока в окошке не появится флаг:

  ЭТО Копировать_слово
   ПОКА НЕ |
   {
    ЯЩИК+
    Перенести_символ
    ВПРАВО
   }
  КОНЕЦ

   Для переноса символов годится моя процедура Перенести_символ,
а процедура Стереть_флаг до смешного проста:

ЭТО Стереть_флаг
 ПИШИ ПУСТО
КОНЕЦ

   Ведь цикл  по копированию символов заканчивается тогда, когда
в окошке появится флаг конца слова. Он-то и подлежит стиранию.

   Петя. Набери на комзьютере эту программу и проверь ее.

   Вася набрал в программном поле свой  текст, записывая коммен-
тарии в местах, которые считал особенно важными:

  // Программа дублирования текста
  ЭТО Дубль
   Поставить_флаг
   Копировать_слово
   Стереть_флаг
  КОНЕЦ

  ЭТО Поставить_флаг
   ПОКА НЕ ПУСТО ВПРАВО
   ПИШИ |
   ПОКА НЕ ПУСТО ВЛЕВО
   ВПРАВО
  КОНЕЦ

  ЭТО Копировать_слово
   ПОКА НЕ |
   {
    ЯЩИК+
    Перенести_символ
    ВПРАВО
   }
  КОНЕЦ

 // Эта процедура копирует символ из ящика
 // в конец текста и возвращает
 // окно в исходное положение
 ЭТО Перенести_символ
  ВПРАВО
  ЕСЛИ ПУСТО
   ТО    ЯЩИК-
   ИНАЧЕ Перенести_символ

   ВЛЕВО // Отложенная команда. Она
         // выполнится столько раз, сколько
         // выполнялась команда ВПРАВО.
 КОНЕЦ

ЭТО Стереть_флаг
 ПИШИ ПУСТО
КОНЕЦ

   Папа. А что если в качестве флага в нашей задаче использовать
символ пустого места?  Тогда мы бы сняли запрет на использование
символа-флага в слове.
   Петя. Мысль интересная и, я думаю, осуществимая.
   Вася. Я подумаю  над этим сюжетом из жизни флагов. Исполни-
тель должен переносить по  одному  символу, пока текст не закон-
чится, поэтому основная процедура будет такой:

  ЭТО Дубль
   ПОКА НЕ ПУСТО
   {
    ЯЩИК+    // Запомнить символ
    Перенос  // Скопировать символ на новое место
    ВПРАВО   // Переместиться к следующему символу
   }
  КОНЕЦ

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

 ЭТО Перенос
  ВПРАВО
  ЕСЛИ ПУСТО
   ТО    Установка
   ИНАЧЕ Перенос
  ВЛЕВО
 КОНЕЦ

   Папа. Хорошее рассуждение.
   Вася. Вторая процедура Установка будет вызвана тогда, когда в
окне виден пустой символ-флаг, расположенный между текстом и его
копией. В этой процедуре рекурсия не нужна: окно перемещается до
конца копии и символ копируется на ленту сразу за ней. Вернуться
назад к  флагу можно при  помощи цикла ПОКА. Перемещение окна от
флага к исходному  символу  в исходном слове выполнит отложенная
команда ВЛЕВО в процедуре Перенос.

 ЭТО Установка
  ВПРАВО
  ПОКА НЕ ПУСТО ВПРАВО
  ЯЩИК-
  ПОКА НЕ ПУСТО ВЛЕВО
 КОНЕЦ

Папа. Прекрасное решение, достойное Куков!

   Задача 1. На ленте записан некоторый текст. Найти  в нем пов-
торное вхождение первого символа. В начальный  момент окно уста-
новлено на первый символ текста.

   Задача 2. В тексте на ленте первый символ, возможно, повторя-
ется. Найти последнее  его вхождение в текст. В начальный момент
окно установлено на начало текста.
