Задача b (10 баллов) Исполнитель Кроха.

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

Определение
-----------
<программа>   := <команда>|<программа><команда>
<команда>     := л|п

Среда Крохи -- пятая строка поля Кукарачи без первой клетки. Кроха
отображается кубиком с надписью "К". В начальный момент Кроха может
быть в любом месте своей среды.

Напишите интерпретатор команд Крохи. Интерпретатор должен выполнять
программы, написанные для Крохи. В начальный момент Кукарача
расположен перед программой в клетке (3,1).


   1 2 3 4 5 6 7 8 9 10
  ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
1 │ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
2 │ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
3 │¤│п│р│о│г│р│а│м│м│а│
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
4 │ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
5 │ │К│ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
6 │ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
7 │ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼

С е м а н т и к а  к о м а н д
л - на одну клетку влево
п - на одну клетку вправо


п р о в е р к а  к у р а т о р а

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

Оказывается недостаток памяти можно компенсировать условными командами
и рекурсиями! Это ли не чудо!

Чудо в этом конкурсе исполнил для нас Гуреев Денис.

Команда 3115
------------
.\15\15.txt
.\15\15b1.coc
Автор решения 15b1: Гуреев Денис

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

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

 Решение задачи:
ЭТО Анализатор
 ВНИЗ                                  
 ВПРАВО                                
 ВВЕРХ                                 
 ЕСЛИ НЕ ПУСТО           
  ТО                     
   {                     
    ЕСЛИ п               
     ТО Анализатор       
     ИНАЧЕ ЕСЛИ л        
             ТО Анализатор
             ИНАЧЕ Ошибка
   }
  ИНАЧЕ                                
   {
    ВВЕРХ                              
    Интерпретатор                      
   }                                   
КОНЕЦ // Анализатор                    
//-------------------------------------
ЭТО Интерпретатор                      
 ВВЕРХ                                 
 ВЛЕВО                                 
 ВНИЗ                                  
 ЕСЛИ НЕ ПУСТО                         
  ТО {                                 
      ЕСЛИ п                           
        ТО {                           
            Интерпретатор              
            Кроха_вправо               
           }                           
        ИНАЧЕ                          
           {                           
            Интерпретатор
            Кроха_влево
           }                           
     }
 ИНАЧЕ Поиск_Крохи                     
КОНЕЦ // Интерпретатор                 
//-------------------------------------
ЭТО Поиск_Крохи                        
 ПОВТОРИ 3 ВНИЗ                        
 ПОКА ПУСТО                            
  {                                    
   ВВЕРХ
   ВПРАВО                              
   ВНИЗ                                
  }                                    
 ВЛЕВО                                 
 ПОВТОРИ 2 ВНИЗ                        
 ВПРАВО                                
 ВВЕРХ                                 
КОНЕЦ // Поиск_Крохи                   
//-------------------------------------
ЭТО Кроха_влево                        
 ВПРАВО
 ВВЕРХ
 ВЛЕВО                                 
 ВНИЗ
 ВЛЕВО                                 
КОНЕЦ // Кроха_влево                   
//------------------ -------------------
ЭТО Кроха_вправо                        
 ВЛЕВО                                 
 ВВЕРХ                                 
 ВПРАВО                                
 ВНИЗ
 ВПРАВО                                
КОНЕЦ // Кроха_вправо                  
//-------------------------------------
ЭТО Ошибка           
 ВНИЗ                
 ВПРАВО              
 ВВЕРХ               
 ЕСЛИ НЕ ПУСТО       
  ТО Ошибка          
 ВЛЕВО               
КОНЕЦ // Ошибка                       

Оценка: 10

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