Роботландский Университет 00/01
31 Азы программирования
Задачи турнира Корректора
-------------------------------


З А Д А Ч И
- - - - - -
март, 2001 (C) А.А.Дуванов

                На мой взгляд, суть программирования как ремесла
                заключается в создании и использовании уровней
                абстракции с целью навести мосты через пропасть,
                разделяющую физические возможности системы и
                желаемый логический результат. Эти зверски
                быстрые, но тупые как пни, компьютеры постоянно
                нуждаются в подсказке, что и как нужно делать на
                следующем шаге, и поэтому становятся тяжелым
                бременем для тех, кто их использует. В особенности
                -- для программистов. Абстракция как раз и
                является тем самым золотым ключиком, который
                помогает справиться со всеми этими головоломными
                сложностями.

                Лу Гринзоу "Философия программирования"


В конкурсе Корректора 2000/2001 года предлагается
11 задач по следующим (условным) темам:

-- Рекуррентные последовательности (задачи 1-6)
-- Лексический анализ выражений   (задача 9)
-- Классические алгоритмы (задачи 7, 8, a, b)

Будем считать, что лента Корректора достаточно длинная, и краевые
эффекты в решениях можно не учитывать (известно, что длина ленты при
необходимости настраивается в файле kor.ini).

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

При оценке решений будет учитываться:

-- наличие описания алгоритма и комментария программы
-- наличие диаграммы переходов в задаче 9
-- правильность алгоритма и программы (на всех допустимых данных)
-- эффективность алгоритма и эффективность программы
-- структурирование кода программы

В целях повышения удобочитаемости кода (что особенно важно при
перекрестных проверках) настоятельно рекомендуется:

-- Главную процедуру (с которой код начинает свою работу) именовать
   "вход".
-- Имена всех процедур записывать только в нижнем регистре (не
   "ПРОХОД1", а "проход1").
-- Использовать для процедур осмысленные имена, которые как-то
   документирует их работу ("фас!" -- это смешно, но "поиск_цифры"
   -- гораздо лучше).
-- В кодах использовать краткие, но содержательные комментарии.
   Комментарии должны пояснять логику, а не "физику" работы кода.
   Такой комментарий плох (пуст):

   ВПРАВО // сдвигаем окошко вправо

   Этот лучше:

   ВПРАВО // к следующему символу записи

   Для каждой важной процедуры записывайте комментарий в виде:

   // <назначение процедуры>
   // Вход:  <где окно, что в ящике и на ленте>
   // Выход: <где окно, что в ящике и на ленте>

   Уверен, что эти рекомендации помогут, в первую очередь самим
   разработчикам, поэтому не откладывайте комментирование
   на последние полчаса перед посылкой работы на конкурс (чтобы
   удовлетворить "причудам" куратора).

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


Успехов вам в конкурсе и приятных минут рождения красивого решения!



Задача 1 (2 балла)
--------
Первый член последовательности равен 1. Каждый следующий член
получается приписыванием справа единицы к записи предыдущего.

a  = 1
 1
a    = a 1
 i+1    i

Построить n-й член последовательности, если n кодируется порядковым
номером символа, который Корректор видит в начальный момент в своем
окошке. Считать, что символ "1" кодирует n=1, и в начальный момент на
ленте не могут быть записаны символы с меньшим порядковым номером.

Пример работы программы:

Начальное состояние            После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬        ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬
│░│░║2║░│░│░│░│░│░│░│░│  ─>    │░│░│1│1║░║░│░│░│░│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴        ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴


Задача 2 (3 балла)
--------
Первый член последовательности равен 1. Каждый следующий член
получается приписыванием справа 0, если последний символ записи
предыдущего члена равен 1, или приписыванием справа 1 в противном
случае.

a  = 1
 1
a  = 10
 2
a  = 101
 3
...

Построить n-й член последовательности, если n кодируется порядковым
номером символа, который Корректор видит в начальный момент в своем
окошке. Считать, что символ "1" кодирует n=1, и в начальный момент на
ленте не могут быть записаны символы с меньшим порядковым номером.

Пример работы программы:

Начальное состояние            После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬        ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬
│░│░║2║░│░│░│░│░│░│░│░│  ─>    │░│░│1│0║░║░│░│░│░│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴        ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴


Задача 3 (3 балла)
--------
Первый член последовательности равен 10. Каждый следующий член
получается приписыванием справа двух символов, получаемых
инвертированием последних двух знаков записи предыдущего члена.

a  = 10
 1
a  = 1001
 2
a  = 100110
 3
...

Построить n-й член последовательности, если n кодируется порядковым
номером символа, который Корректор видит в начальный момент в своем
окошке. Считать, что символ "1" кодирует n=1, и в начальный момент на
ленте не могут быть записаны символы с меньшим порядковым номером.

Пример работы программы:

Начальное состояние            После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬        ┬─┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬
│░│░║2║░│░│░│░│░│░│░│░│  ─>    │░│░│1│0│0│1║░║░│░│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴        ┴─┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴

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

a  = 110 (например)
 1
a  = 11001
 2
a  = 1100110
 3
...

Построить n-й член последовательности, если n кодируется порядковым
номером символа, который Корректор видит в начальный момент в своем
окошке. Считать, что символ "1" кодирует n=1, и в начальный момент на
ленте не могут быть записаны символы с меньшим порядковым номером.
Сразу справа от n на ленте записан первый член последовательности.

Пример работы программы:

Начальное состояние            После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬        ┬─┬─┬─┬─┬─┬─┬─╦═╦─┬─┬─┬
│░│░║2║1│0│1│░│░│░│░│░│  ─>    │░│░│1│0│1│1│0║░║░│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴        ┴─┴─┴─┴─┴─┴─┴─╩═╩─┴─┴─┴


Задача 5 (4 балла)
--------
Первый член последовательности представляет собой непустую
последовательность нулей и единиц. Каждый следующий член получается
приписыванием слева и справа к записи по одному знаку. Слева
приписывается первый инвертированный знак, а справа последний
инвертированный знак предыдущего члена.

a  = 110 (например)
 1
a  = 01101
 2
a  = 1011010
 3
...

Построить n-й член последовательности, если n кодируется порядковым
номером символа, который Корректор видит в начальный момент в своем
окошке. Считать, что символ "1" кодирует n=1, и в начальный момент на
ленте не могут быть записаны символы с меньшим порядковым номером.
Сразу справа от n на ленте записан первый член последовательности.

Пример работы программы:

Начальное состояние            После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬        ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
│░│░║2║1│0│1│░│░│░│░│░│  ─>    │░│░│0│1│0│1│0│░│░│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴        ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴


Задача 6 (6 баллов)
--------
Первый член последовательности представляет собой непустую
последовательность нулей и единиц. Каждый следующий член получается
приписыванием справа знака 0 или 1. Выбирается такой знак, чтобы число
единиц и число нулей в каждом члене последовательности не отличались
друг от друга больше, чем на 2.

Построить n-й член последовательности, если n кодируется порядковым
номером символа, который Корректор видит в начальный момент в своем
окошке. Считать, что символ "1" кодирует n=1, и в начальный момент на
ленте не могут быть записаны символы с меньшим порядковым номером.
Сразу справа от n на ленте записан первый правильный член
последовательности.

Задача 7 (7 баллов) НОД двух чисел.
--------
Написать программу для вычисления наибольшего общего делителя двух
чисел. Полагать, что числа по величине меньше длины алфавита
Корректора.


Задача 8 (8 баллов) Перевод в двоичную.
--------
Написать программу для перевода десятичного числа в двоичную систему
счисления. Полагать, что число по величине меньше длины алфавита
Корректора.


Задача 9 (6 баллов) Проверка программы.
--------

Определение
-----------
<программа>   := <команда>|<программа><команда>
<команда>     := <простая>|<цикл>
<простая>     := л|п|в|н
<цикл>        := ц<повторитель><команда>
<повторитель> := 4|5

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

┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬
│░│░║░║з│а│п│и│с│ь│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴

Если проверяемая запись -- программа, написать следом за ней сообщение
"ок":

┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
│░│░│░│з│а│п│и│с│ь│░│о│к│░│
┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴

Если запись -- не программа, записать следом за ней сообщение "ош" и
поставить окно на первый неверный символ:

┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬
│░│░│░│з│а║п║и│с│ь│░│о│ш│░│
┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴

Задача a (9 баллов) Самое длинное слово.
--------
На ленте записан текст, состоящий из слов. Каждое слово завершает один
пробел. Найти самое длинное слово в тексте. Известно, что:

-- в словах нет цифр (символов 0,1,2,3,4,5,6,7,8,9);
-- в тексте нет слов длиннее 10 символов.

Установить окошко Корректора на начало самого длинного слова.
В начальный момент окошко расположено перед текстом.

Пример работы программы:

Начальное состояние              После работы программы
╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬    ┬─╥─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬
║░║а│х│ │э│т│о│т│ │к│о│т│ │░│    │░║а│х│ ║э║т│о│т│ │к│о│т│ │░│
╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴    ┴─╨─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴


Задача b (10 баллов) Ханойская башня.
--------
Написать программу, которая выводит на ленту запись последовательности
переносов, решающих задачу (кто забыл постановку задачи, смотрите
конкурс Кукарачи).

Можно рекомендовать такую организацию работы программы.

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

Например:

713

Это означает, что кужно решить задачу о башне с 7 кольцами, перенеся
ее со стержня 1 на стержень 3.

Нужно получить на ленте запись последовательности переносов, которая
решает задачу. Каждый перенос можно кодировать, например, тремя
символами:

-- пробел
-- откуда
-- куда

Начальное состояние        После работы программы
┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬    ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
│░║3║1│3│░│░│░│░│░│░│░│ ─> │ │1│3│ │1│2│ │3│2│ │1│3│ │2│1│ │2│3│ │3│1│░│
┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴    ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴

                       * * *

НОД двух чисел
--------------
Наибольший общий делитель двух целых чисел a и b -- это наибольшее
целое число, которое делит их оба.

Например, НОД(12,18) = 6.

Заметьте, что НОД(0,n) = n, так как любое положительное число делит 0,
а n является наибольшим делителем самого себя. Величина НОД(0,0) не
определена.

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

Вот как описан алгоритм Евклида в книге Б.А.Трахтенброта "Алгоритмы и
машинное решение задач" (Москва, 1960 г.).

Нахождение НОД(a,b)
```````````````````
  Указание 1. Обозревай два числа: a,b. Переходи к следующему указанию.

  Указание 2. Сравни обозреваемые числа (a=b, или a<b, или a>b);
  переходи к следующему указанию.

  Указание 3. Если обозреваемые числа равны, то каждое из них дает
  искомый результат. Процесс вычисления остановить. Если нет, переходи к
  следующему указанию.

  Указание 4. Если первое обозреваемое число меньше второго
  обозреваемого числа, переставь их местами и продолжай обозревать их.
  Переходи к следующему указанию.

  Указание 5. Вычитай второе из обозреваемых чисел из первого и
  обозревай два числа: вычитаемое и остаток. Переходи к указанию 2.


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

Не удержавшись, привожу еще одну цитату из раздела "Введение" этой
книги.

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

Через 40 лет производительность настольного компьютера перевалила за
1 000 000 000 операций в секунду, то есть выросла в 50 000 раз, а
выражение "квалифицированный вычислитель, работающий на хорошем
клавишном арифмометре" многим теперь просто не понятно!

Позиционные системы счисления
-----------------------------
В позиционных системах счисления (к ним относится десятичная,
двоичная, троичная..., а не относится римская) число записывается в
виде цепочки конечного фиксированного набора знаков (цифр). При этом
значение каждой цифры зависит от ее положения (позиции) в записи.

Например, в привычной записи "23" цифра "3"означает три единицы,
а в записи "325" цифра "3" означает три сотни.

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

abc

обозначает число:
    2       1       0
a*10  + b*10  + c*10

т.е., при просмотре справа налево первая цифра означает единицы,
вторая -- десятки, третья -- сотни и так далее.

В двоичной системе всего две цифры: 0 и 1, а основанием служит число
2. Двоичная запись

abc

обозначает число:

   2     1     0
a*2 + b*2 + c*2

Например,

101 = (1*4+0*2+1*1) = 5
   2               10  10

(101 в двоичной означает 5 в десятичной).

Перевод из десятичной в двоичную
--------------------------------
В десятичной системе число разложено по степеням 10. Для перевода его
в двоичную систему, надо разложить его по степеням двойки. Понятно,
что при этом не обойтись без операции деления.

Пусть число x нужно перевести в двоичную систему счисления, то есть,
найти его запись:

    n         n-1             1       0
a *2  + a   *2    + ... + a *2  + a *2       (*)
 n       n-1               1       0

Здесь:

a , a   , ..., a , a  -- это двоичные цифры (0 или 1).
 n   n-1        1   0

Перепишем (*) в виде:


┌     n-1       n-2            ┐
│ a *2  + a   *2    + ... + a  │*2 + a   = x
│  n       n-1               1 │      0
└                              ┘

Заметим, что цифра a  есть остаток от деления x на 2, а
                    0

┌     n-1       n-2            ┐
│ a *2  + a   *2    + ... + a  │   (**)
│  n       n-1               1 │
└                              ┘

есть  целая часть от деления x на 2.


Иными словами, самая правая цифра двоичной записи равна остатку от
деления x на 2.

Видим из (**), что остаток от деления (**) на 2 даст нам вторую цифру
двоичной записи. И так далее. Эти наблюдения приводят к формулированию
следующего алгоритма.

Алгоритм перевода десятичного числа x в двоичное число
``````````````````````````````````````````````````````
сфомировать пустую запись n
ПОКА x>1
{
  d = остаток(x/2) // это очередная цифра справа
  n = d+n          // добавить d (найденную цифру) в начало записи
  x = целая_часть(x/2)
}
n = x+n            // добавить x (последнюю цифру справа) в начало записи


Прокрутка алгоритма для x=6
```````````````````````````
n = пусто
---------------вход в цикл
6>1
  d=0
  n=0
  x=3
3>1
  d=1
  n=10
  x=1
1>1
---------------выход из цикла
n=110
