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

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

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

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

                       К О Р Р Е К Т О Р

Глава 2. Язык программирования Корректора

                              И стал он  галчонка учить разгова-
                              ривать. Целыми днями  сидел  около
                              него и говорил:
                              - Кто там? Кто там? Кто там?
                                                     Э.Успенский

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

2.1. Процедурное программирование

     Папа. Начнем нашу  работу с такой задачи: на ленте Коррек-
тора записан один символ, и  он  виден  через окошко. Требуется
записать рядом с ним еще пять  символов, последовательно идущих
за данным в алфавите исполнителя.
   Вася. Значит, если на ленте записан символ 0,  то нужно напи-
сать еще символы 1,2,3,4,5.
   Петя. А  если на ленте  записан символ 8, то новыми символами
будут 9, а, б, в, г.
   Папа. Вы правильно поняли условие. Давайте  сначала решим бо-
лее простую задачу: пусть требуется записать на ленту не пять, а
только один новый символ по тому же правилу. Как ее решить?
   Петя. Я думаю надо скопировать  символ  в  соседнюю ячейку и
применить к копии команду ПЛЮС.
   Папа. А как скопировать символ?
   Петя. В  среде Корректора кроме  ленты есть ящик - эта ячейка
памяти вполне подходит для наших целей.
   Вася. Мне все ясно! Вот мое решение:

ЭТО Следующий_символ
 ЯЩИК+   // ┌───────────────────┐
 ВПРАВО  // │Копирование символа│
 ЯЩИК-   // └───────────────────┘
 ПЛЮС    // Заменить символ на следующий
КОНЕЦ

   Папа. Очень хорошо! Ну, теперь я думаю, несложно решить зада-
чу в начальной постановке.
   Петя. Ничего нет проще. Нужно просто повторить процедуру Сле-
дующий_символ пять раз.
   Вася. Получается длинная программа... В ней 20 команд:
ЭТО Символы_по_порядку
 ЯЩИК+
 ВПРАВО
 ЯЩИК-
 ПЛЮС

 ЯЩИК+
 ВПРАВО
 ЯЩИК-
 ПЛЮС

 ЯЩИК+
 ВПРАВО
 ЯЩИК-
 ПЛЮС

 ЯЩИК+
 ВПРАВО
 ЯЩИК-
 ПЛЮС

 ЯЩИК+
 ВПРАВО
 ЯЩИК-
 ПЛЮС
КОНЕЦ
     Петя. Запись  можно существенно сократить, используя в ка-
честве команды вызов процедуры Следующий_символ.
     Вася. Да, конечно, мы так делали, программируя Кукарачу. Я
помню могущество  процедур! Их вызов можно использовать многок-
ратно, и это  здорово экономит усилия программиста! Вот мое но-
вое решение:

ЭТО Символы_по_порядку
 Следующий_символ
 Следующий_символ
 Следующий_символ
 Следующий_символ
 Следующий_символ
КОНЕЦ

   Петя. Преимущество процедурного программирования еще и в том,
что  программы  становятся более простыми и наглядными, так  как
раскладываются  на  множество  маленьких  процедур,  описывающих
простые и короткие действия.
   Вася. Процедуры как  бы  расширяют СКИ, "дополняя" его новыми
командами.
   Петя. Эта одна точка  зрения.  А можно, наоборот, считать ко-
манды из СКИ специальными стандартными процедурами, понятные ин-
терпретатору программ без описаний.
   Вася. Напомните мне, пожалуйста, что такое интерпретатор.
   Петя. Я готов.  Исполнитель  понимает и выполняет только ко-
манды из  своей СКИ, такие, как  ВПРАВО, ВЛЕВО, ПЛЮС.  Мы пишем
команду Следующий_символ, а ее нет в СКИ. Тем  не менее, испол-
нитель прекрасно работает  и  не выдает сообщения "Не понимаю".
Почему?
   Вася. Мы пишем для него программу.
   Петя. И что, он ее выполняет?
   Вася. Конечно,  ты же сам видел, как он забавно  трудился над
лентой и ящиком.
   Петя. И Корректор выполнял команду Следующий_символ, она ведь
не входит в его СКИ?
   Вася. Ну, не знаю.
   Петя. На самом деле  программу  выполняет не Корректор, а ин-
терпретатор. Он  читает твою программу  и переводит ее в СКИ ис-
полнителя.
   Вася.  Кажется, я понимаю. Когда интерпретатор читает в  моей
программе команду  Следующий_символ,  он  передает исполнителю 5
команд из его СКИ.
   Петя. Точно, интерпретатор - это переводчик. Он позволяет ис-
пользовать язык программирования, а это здорово облегчает управ-
ление роботом.
   Вася. А как выглядит интерпретатор на экране компьютера?
   Петя. Никак. Интерпретатор - это одна  из процедур программы,
моделирующей исполнителя на компьютере, и  он не имеет на экране
никакого внешнего отображения.

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

2.2. Циклы

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

                      ПОВТОРИ число команда

   ПОВТОРИ - это ключевое слово языка, "число" - это целое поло-
жительное число,  обозначающее число повторений, "команда" - это
любая команда языка (только одна!), которая подлежит повторению.
   Вася. Вот новый  вариант нашей программы. С командой цикла он
выглядит гораздо веселее.

ЭТО Следующий_символ
 ЯЩИК+   // ┌───────────────────┐
 ВПРАВО  // │Копирование символа│
 ЯЩИК-   // └───────────────────┘
 ПЛЮС    // Заменить символ на следующий
КОНЕЦ

ЭТО Символы_по_порядку
 ПОВТОРИ 5 Следующий_символ
КОНЕЦ

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

ЭТО Символы_по_порядку
 ПОВТОРИ 5
 {
   ЯЩИК+
   ВПРАВО
   ЯЩИК-
   ПЛЮС
 }
КОНЕЦ

   Папа. Так, конечно, сделать можно. Составная команда позволя-
ет объединять несколько команд  в  одну при помощи фигурных ско-
бок. Но, на мой  взгляд,  последняя программа чуть хуже предыду-
щей, так как она менее наглядная.

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

                      ПОКА условие команда

Работает цикл так:
     - сначала проверяется условие;
     - если условие ложно, выполнение команды повторения закан-
чивается;
     - если условие истинно,  выполняется "команда", записанная
после условия,  и  все начинается сначала: проверяется условие,
выполняется команда и так далее.
   Петя. Верно! Заметь,  что если условие ложно с самого начала,
то "команда", записанная после условия, не выполнится ни разу.
   Папа. Осталось рассказать, как записывается и проверяется ус-
ловие.
   Петя. Обычно  в качестве условия записывают символ. Интерпре-
татор будет сравнивать  его с тем символом, который Корректор ви-
дит через окошко на ленте. Если они совпадают, условие считается
выполненным, если отличаются - условие ложно.
   Папа. Для обозначения пробела и пустого места можно использо-
вать ключевые слова ПРОБЕЛ и ПУСТО. Эти же  ключевые слова можно
применять и в команде ПИШИ.
   Петя. Еще одна важная деталь.  При  записи  условия можно ис-
пользовать ключевое слово НЕ. Это слово  означает, что интерпре-
татор программ  будет проверять условие "наоборот": когда символ
на ленте не совпадает с указанным после слова ПОКА, условие счи-
тается выполненным.
   Вася. Сейчас ключевое  слово НЕ, я думаю, нам не потребуется.
Ведь Корректор должен перемещать окно на  ленте (например, впра-
во) пока в  нем  ПУСТО. Как только в  окошке  появится не пустой
символ, работа его заканчивается:

 ЭТО Поиск_символа
   ПОКА ПУСТО ВПРАВО
 КОНЕЦ

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

 ЭТО Поиск_пробела
   ПОКА НЕ ПРОБЕЛ ВПРАВО
 КОНЕЦ

   Петя. В инструкции указано еще несколько разновидностей усло-
вия. Они связаны со сравнением символа в оконной  ячейке ленты с
символом, расположенным в ящике:
   Я=Л - условие истинно, если символ в ящике совпадает с симво-
   лом в оконной ячейке ленты;
   Я#Л - условие истинно, если символ в ящике отличается от сим-
   вола в оконной ячейке ленты;
   Я>Л - условие истинно, если символ в ящике  имеет больший по-
рядковый номер в алфавите  Корректора  по сравнению с символом в
оконной ячейке ленты;
   Я<Л - условие истинно, если символ в ящике  имеет меньший по-
рядковый номер в алфавите  Корректора  по сравнению с символом в
оконной ячейке ленты.
   Папа. Ну  вот еще одна  задача, где пригодятся эти типы усло-
вия: на  ленте записан текст  и окошко установлено на первый его
символ. Известно, что первый символ  встречается  в  тексте  еще
несколько раз. Найти первое его повторение.
   Вася. Если бы у  Корректора не было ящика, я бы не  знал, как
решить эту  задачу. Ну, а с ящиком все  очень просто: сначала мы
поместим в него первый  символ  текста, а затем будем перемещать
окно вдоль текста, пока символ в ящике и на ленте отличаются:

 ЭТО Поиск_повтора
   ЯЩИК+
   ПОКА Я#Л ВПРАВО
 КОНЕЦ

   Петя. И еще,  в  качестве условия можно использовать ключевое
слово ЦИФРА. Оно принимает  истинное  значение, если в окошке на
ленте записан любой из символов 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
   Папа. Простая  задача  на  использование  этого типа условия:
найти в тексте на ленте  первое  вхождение  цифры (установить на
нее окно). Если в тексте цифр нет, установить окно на первый пус-
той символ справа. В начальный момент окно установлено на начало
тевста.
   Вася. Вот мое решение:

 ЭТО Поиск_цифры
   ПОКА НЕ ЦИФРА ВПРАВО
 КОНЕЦ

   Задача 2. Текст на ленте, возможно,  начинается серией пробе-
лов. Стереть все  начальные пробелы, если перед работой окно ус-
тановлено на начало текста.

┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
│░│░│░║ ║ │ │т│е│к│с│т│ │н│а│ │л│е│н│т│е│░│░│░│░│░│░│░│░│░│░│
┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴

2.3. Развилки
   Вася. Решая задачи Кукарачи, мы использовали еще одну команду
языка программирования - команду ветвления.
   Петя. И ты помнишь, как ее записывать?
   Вася. Помню,  команда ветвления содержит ключевые слова ЕСЛИ,
ТО, ИНАЧЕ. Вот как она выглядит:
                 ЕСЛИ условие
                   ТО    команда1
                 ИНАЧЕ команда2
   Слова ЕСЛИ, ТО, ИНАЧЕ здесь ключевые слова языка программиро-
вания. Они как цемент связывают команду ветвления воедино. Рабо-
тает новая команда так: интерпретатор программ проверяет условие
и, если  оно верное, выполняет команду  1, если условие  ложно -
выполняет команду 2.  В любом случае работает только одна коман-
да: либо команда 1, либо команда 2. Условие  в команде ветвления
записывается и проверяется точно так же, как в команде цикла ПО-
КА.
   Петя. Правильно! Покажи, как она работает на примере решения
следующей задачи: на ленте записано  целое  число  больше 9, но
меньше 90. Увеличить его на один, если в начальный момент в ок-
но виден последний символ числа.
   Вася. Но такая задача решалась нами без всяких ветвлений од-
ной командой ПЛЮС!
   Петя. Не торопись. А если число оканчивается на цифру девять?
Вася. Да... Тогда по команде ПЛЮС  на  место  девятки  запишется
буква "а". Я понял! Тут,  действительно,  без  развилки не обой-
тись. Сначала надо проверить последнюю  цифру.  Если  она не де-
вять, применить команду ПЛЮС, а если  девять, обработать отдель-
но: вместо девятки  записать  ноль, сместиться влево и применить
команду ПЛЮС к первой цифре числа: этот ПЛЮС  сработает всегда -
ведь по условию первая цифра не может быть девяткой. Вот мое ре-
шение:

ЭТО Плюс1
 ЕСЛИ 9
  ТО    Девять // Особый случай
  ИНАЧЕ ПЛЮС
КОНЕЦ

ЭТО Девять
 ПИШИ 0
 ВЛЕВО
 ПЛЮС
КОНЕЦ

   Задача 3. Зачем в условии задачи сказано, что число на ленте
должно быть больше 9?

   Папа. Обращаю еще раз ваше внимание на то, что после  слов ТО
и ИНАЧЕ можно писать только одну  команду.  Кроме  того,  запись
"ИНАЧЕ команда2"  может отсутствовать, и тогда команда принимает
вид:
                 ЕСЛИ условие
                   ТО  команда1
   Эта запись равнозначна следующей:
                 ЕСЛИ условие
                   ТО  команда1
                   ИНАЧЕ СТОЯТЬ
   Команда  СТОЯТЬ  из СКИ - пустая, выполняя  ее  Корректор  не
предпринимает никаких действий.
   Вот  вам  еще  одна  "развилочная" задача: на  ленте  записан
текст, в котором злоумышленник заменил все буквы "л" на "к". Из-
вестно, что в исходном тексте не было букв "к". Восстановить ис-
ходный вид текста. В начальный момент в окно виден первый символ
записи.
   Вася. Какой текст мне записать на ленту?
   Папа. Ну, давай запишем текст "киса на кугу"  и пусть Коррек-
тор его расшифрует.

   Вася вошел в редактор среды,  записал  на  ленту эту забавную
фразу и стал думать, как написать решение.

   ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
   │░│░│░│░║к║и│с│а│ │н│а│ │к│у│г│у│░│░│░│░│░│░│░│░│░│░│░│░│
   ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴

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

  ЭТО Шифр
   ПОКА НЕ ПУСТО
   {
     Проверка
     Шаг
   }
  КОНЕЦ

   Петя. Неплохо! Мне кажется, занятия с Кукарачей не прошли для
тебя даром.

   Вася, довольный похвалой брата, продолжал свои рассуждения.

   Вася. Проверка должна содержать команду ветвления: если в окне
видна буква "к", то ее нужно заменить на букву "л":

ЭТО Проверка
 ЕСЛИ к ТО ПИШИ л
КОНЕЦ

   Ну, а процедура Шаг совсем проста: она просто перемещает окно
на одну клетку влево:

ЭТО Шаг
 ВЛЕВО
КОНЕЦ

Я думаю, можно записать мою программу в виде одной процедуры.

   Папа. Конечно, можно, но это хуже. Если все-таки это сделать,
просто необходимо использовать комментарии, так как содержатель-
ные имена процедур Проверка и Шаг исчезают:

  ЭТО Шифр
   ПОКА НЕ ПУСТО
   {
     ЕСЛИ к ТО ПИШИ л  // Проверка и замена, если нужно
     ВЛЕВО             // Шаг к следующему символу
   }
  КОНЕЦ

Задача 4.
   ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
   │░│░│░│░║с║а│в│а│у│░│░│░│░│░│░│░│░│░│░│░│░│░│░│░│░│░│░│░│
   ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴

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

ЭТО Сава
 ПОВТОРИ 5
 {
   ЕСЛИ а
    ТО    ПОВТОРИ 14 ПЛЮС
    ИНАЧЕ МИНУС
    ВПРАВО
 }

   Задача 5. На ленте  в  соседних ячейках записаны два символа.
Упорядочить их по возрастанию порядковых номеров в алфавите Кор-
ректора. В начальный момент окно установлено на первый символ.

2.4. Рекурсия
   Петя. Мы еще не рассматривали такой  важный прием программи-
рования, как рекурсия.
   Вася. По работе с  Кукарачей  этот прием мне хорошо известен.
Если написать такую программу:

ЭТО Поход
 ВПРАВО
 Поход
КОНЕЦ

то Корректор  как  заводная игрушка будет безостановочно переме-
щать окно вдоль ленты, пока мы не выключим компьютер, ведь лента
склеена в кольцо!
   Петя. Выключать компьютер  не надо, в любой момент можно пре-
вать работу программы нажав на  клавиатуре  клавишу  Pause, а в
остальном ты конечно прав. Такая программа называется РЕКУРСИВ-
НОЙ. Рекурсия - это способ программирования,  при котором прог-
рамма вызывает сама  себя.  Рекурсия, которая не имеет проверки
на окончание, как в твоей программе, называется БЕСКОНЕЧНОЙ.
   Папа. Попробуйте переписать программу Шифр в рекурсивном вари-
анте.

   Вася и Петя немного поспорили, но потом пришли к единому мне-
нию и показали папе свое решение:

  ЭТО Шифр
     ЕСЛИ к ТО ПИШИ л  // Проверка и замена, если нужно
     ВЛЕВО             // Шаг к следующему символу
     ЕСЛИ НЕ ПУСТО     // Проверка на окончание
      ТО Шифр          // Рекурсивный вызов
   }
  КОНЕЦ


   Задача 6. На ленте записан некоторый  текст. Проверить, есть
ли в нем многоточие (три и более подряд идущих знака  "."). Ус-
тановить  окно  на начало первого многоточия, если они  присут-
ствуют в  тексте или на  первый пустой символ за концом текста,
если  многоточие  отсутствует. В начальный момент в окно  виден
первый символ текста.
