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


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


Команда 3104
------------
.\04\04.txt
Оценка: 0

Команда 3106
------------
.\06\06.txt
Оценка: 4
Автор решения: Лавыгин Сергей
Ганиев Женя, Докадин Ваня

Алгоритм
--------
Сначала записываем последовательность переноса одного кольца на
различные стержни, затем двух колец, разбивая перенос на два переноса
по одному кольцу. Если надо перенести три, разбиваем на перенос одного
и двух, четыре- на одного и трех и т.д.
Описание переходов в именах процедур. Д_3_2 означает перенос
двух колец с третьего стержня на второй, С_2_1- семи со второго на
первый,О-одного, Т-трех, Ч-четырех, П-пяти, Ш-шести.

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

ЭТО Вход
  ВПРАВО
  ЕСЛИ 1 ТО О  // Если первая цифра 1, то процедура О
     ИНАЧЕ
    ЕСЛИ 2 ТО Д
        ИНАЧЕ
       ЕСЛИ 3 ТО Т
          ИНАЧЕ
          ЕСЛИ 4 ТО Ч
              ИНАЧЕ
              ЕСЛИ 5 ТО П
                ИНАЧЕ
                  ЕСЛИ 6 ТО Ш
                    ИНАЧЕ
                      ЕСЛИ 7 ТО С
КОНЕЦ
....

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


Команда 3107
------------
.\07\07.txt
.\07\turb.kor
Оценка: 10

// Задача b
// Ханойские башни                     
// Автор решения: Евглевич С.          
//                                     
// Алгоритм решения состоит из трех    
// шагов:                              
// 1. Перенос (n-1) кольца на промежу- 
//    точную подставку.                
// 2. Перенос нижнего кольца на конеч- 
//    ную подставку                    
// 3. Перенос (n-1) кольца с промежу-  
//    точной на конечную подставку     
// 1-й и 3-й шаги приводят к переносу  
// 1 кольца в результате сложной       
// косвенной рекурсии между програм-   
// мами Ханойij, где i - номер началь- 
// ной, а j - номер конечной подставки
//
ЭТО вход                               
 ЯЩИК+  // Записываем в яшик число
        // дисков в начале
 ВПРАВО  //  Считываем номер начальной 
         // подставки                  
 ЕСЛИ 1  //                            
  ТО     //
   {      //                           
   ВПРАВО  // и номер конечной         
           // подставки                
   ЕСЛИ 2      // и определяем         
     ТО        // имя главной          
       Ханой12 // программы            
     ИНАЧЕ     //                      
       Ханой13 //                      
    }                                  
  ИНАЧЕ                                
    {                                  
    ЕСЛИ 2
     ТО                                
      {
      ВПРАВО
      ЕСЛИ 1                           
       ТО
         Ханой21
       ИНАЧЕ                           
         Ханой23                       
       }                               
    ИНАЧЕ
     {                                 
     ВПРАВО                            
     ЕСЛИ 1                            
      ТО                               
        Ханой31
      ИНАЧЕ                            
        Ханой32                        
      }                                
    }                                  
КОНЕЦ                                  
//-------------------------------------
// Программа переноса с 1 на 2 под-
// ставку (комментарии к остальным     
// программам аналогичные)
//
ЭТО Ханой12                            
ОБМЕН              // Считываем
 ЕСЛИ 1 ТО         // кол-во дисков
  {                                    
  ОБМЕН          // Восстан. записи    
  ВПРАВО ПИШИ ПРОБЕЛ // Записываем     
  ВПРАВО ПИШИ 1      //  ход 1-2
  ВПРАВО ПИШИ 2      // переноса 1 д.  
  }                                    
 ИНАЧЕ                                 
  {                                    
  МИНУС             // Уменьшаем
                      // кол-во дисков 
                      // на единицу    
  ОБМЕН        // восст. записи        
  Ханой13       // перенос (n-1)       
                 // диска с 1 на 3     
  ВПРАВО ПИШИ ПРОБЕЛ  // Перенос 1 д.  
  ВПРАВО ПИШИ 1       // с 1 на 2
  ВПРАВО ПИШИ 2       //               
  Ханой32        // перенос (n-1)
                  // диска с 3 на 2
  ОБМЕН ПЛЮС ОБМЕН // восстановление   
  }                 // счетчика дисков
КОНЕЦ
//-------------------------------------
// Перенос с 1 на 3                    
ЭТО Ханой13                            
ОБМЕН
 ЕСЛИ 1 ТО                             
  {                                    
   ОБМЕН                               
   ВПРАВО ПИШИ ПРОБЕЛ                  
   ВПРАВО ПИШИ 1
   ВПРАВО ПИШИ 3                       
                                       
  }                                    
  ИНАЧЕ                                
  {                                    
  МИНУС                                
  ОБМЕН
  Ханой12                              
  ВПРАВО ПИШИ ПРОБЕЛ
  ВПРАВО ПИШИ 1
  ВПРАВО ПИШИ 3                        
  Ханой23
   ОБМЕН ПЛЮС ОБМЕН
  }                                    
КОНЕЦ                                  
//-------------------------------------
// Перенос со 2 на 1
ЭТО Ханой21                            
ОБМЕН                                  
 ЕСЛИ 1 ТО                             
 {                                     
   ОБМЕН
   ВПРАВО ПИШИ ПРОБЕЛ                  
   ВПРАВО ПИШИ 2                       
   ВПРАВО ПИШИ 1                       
 }                                     
  ИНАЧЕ                                
{                                      
   МИНУС
   ОБМЕН                               
 Ханой23
  ВПРАВО ПИШИ ПРОБЕЛ
  ВПРАВО ПИШИ 2                        
  ВПРАВО ПИШИ 1
  Ханой31
   ОБМЕН ПЛЮС ОБМЕН                    
  }                                    
                                       
КОНЕЦ
//-------------------------------------
// Перенос с 2 на 3                    
ЭТО Ханой23                            
ОБМЕН                                  
 ЕСЛИ 1 ТО
   {                                   
    ОБМЕН                              
   ВПРАВО ПИШИ ПРОБЕЛ                  
   ВПРАВО ПИШИ 2                       
   ВПРАВО ПИШИ 3                       
   }                                   
  ИНАЧЕ
  {                                    
      МИНУС
  ОБМЕН
  Ханой21                              
  ВПРАВО ПИШИ ПРОБЕЛ
  ВПРАВО ПИШИ 2
  ВПРАВО ПИШИ 3                        
  Ханой13                              
   ОБМЕН ПЛЮС ОБМЕН                    
   }
КОНЕЦ                                  
//-------------------------------------
// Перенос с 3 на 1                    
ЭТО Ханой31                            
ОБМЕН
 ЕСЛИ 1 ТО                             
    {                                  
     ОБМЕН                             
   ВПРАВО ПИШИ ПРОБЕЛ                  
   ВПРАВО ПИШИ 3                       
   ВПРАВО ПИШИ 1                       
    }
  ИНАЧЕ                                
   {
     МИНУС
     ОБМЕН                             
    Ханой32
    ВПРАВО ПИШИ ПРОБЕЛ
    ВПРАВО ПИШИ 3                      
    ВПРАВО ПИШИ 1                      
    Ханой21                            
   ОБМЕН ПЛЮС ОБМЕН // ВОССТ. СЧ.
    }                                  
КОНЕЦ                                  
//-------------------------------------
// Перенос с 3 на 2                    
ЭТО Ханой32
ОБМЕН                                  
 ЕСЛИ 1 ТО                             
     {                                 
    ОБМЕН                              
   ВПРАВО ПИШИ ПРОБЕЛ                  
   ВПРАВО ПИШИ 3                       
   ВПРАВО ПИШИ 2
    }                                  
 ИНАЧЕ
   {
    МИНУС                              
    ОБМЕН
    Ханой31
   ВПРАВО ПИШИ ПРОБЕЛ
   ВПРАВО ПИШИ 3                       
   ВПРАВО ПИШИ 2                       
    Ханой12
   ОБМЕН ПЛЮС ОБМЕН                    
    }                                  
КОНЕЦ                                  
//-------------------------------------

к о м м е н т а р и й  к у р а т о р а
Просто великолепно! Реализован классический рекурсивный алгоритм.
Евглевич С. (эх, жаль нет полного имени, ведь страна должна знать
своих героев!) сумел упаковать эту двойную рекурсию в среду Корректора,
не испугавшись "крутых" рекурсивных последствий.

Команда 3108
------------
.\08\08.txt
Оценка: 0

Команда 3110
------------
.\10\10.txt
.\10\1011.kor
Оценка: 0

Команда 3113
------------
.\13\13.txt
.\13\1321.kor
Оценка: 0

Команда 3114
------------
.\14\14.txt
.\14\1421.kor
Оценка: 0


Команда 3115
------------
.\15\15.txt
Оценка: 0

Автор решения Первушин Данил

Описание алгоритма:
   Чтобы решить Ханой для одного кольца, надо просто перенести кольцо
с первого столбца на третий(см. ниже *). А если колец больше,
тогда нужно N-1 кольцо (N-начальное количество колец) перенести
с первого стержня на второй (**), оставшееся кольцо перенести с первого
стержня на третий, а затем N-1 кольцо со второго стержня на третий (***).
Точно также, чтобы перенести N-1 кольцо со второго столбца
на третий (****), нужно: перенести N-2 кольца со второго
на первый, оставшееся на втором стержне кольцо перенести на третий
и N-2 кольца с первого стержня перенести на третий и т.д. .
   Взгляд программиста может сразу заметить, что задача
рекурсивная:
     ЭТО Ханой (N колец, с 1 на 3 стержень)
      ЕСЛИ N НЕ = 1
       ТО
        {
         Ханой  (N-1 кольцо, с 1 на 2 стержень)  **
         Кольцо (с 1 на 3 стержень)              ***
         Ханой  (N-1 кольцо, с 2 на 3 стержень)  ****
        }
       ИНАЧЕ Кольцо (с 1 на 3 стержень)           *
     КОНЕЦ
                         (алг1)


   Но одной рекурсивной процедуры не хватает, поэтому их по 6
(каждой из двух видов: Ханой и Кольцо), потому что существует по 6
вариантов переноса башни и кольца с одного стержня на другой.

   Казалось бы все очень просто, но оказывается не очень.
Надо ещё переделать это на корректоровский лад, чтобы при рекурсивном
запуске процедур в окошке было правильное число колец. Отсюда и
все "прибамбасы" типа: МИНУС, ЯЩИК+, ЯЩИК- и пр.

   Если вы посмотрите Ханой1-3 или любой другой Ханой в коде программы,
то непременно обнаружите, что по сравнению  с алг1 добавились три строчки:

1) МИНУС (см. в коде #)при закручивании рекурсивной пружины для перехода
   от N колец к N-1
2) ЯЩИК- (##)выкладываем значение из ящика для того чтобы 
   подготовить к следующему Ханою
3) ЯЩИК- ПЛЮС ЯЩИК+ (###)перед "возвращением" на "предыдущий" уровень
   увеличиваем на один количество колец для предыдущего Ханоя 
   (предыдущего по ходу закручивания рекурсии)

После того, как все переносы записаны, окно возвращается к началу записи,
попутно подсчитывая в ящике количество переносов (этот сервис нормально
работает при числе колец от 1 до 6).


Программа, описание программы:
На входе - в окошке символ из алфавита Корректора, номер которого
представляет из себя количество колец в башне.
Предполагается, что башня переносится с 1-го стержня на 3-й. 


//─────────────────────────────────────┐
// описание                            │
ЭТО Вход                               │
 Ханой1-3                              │
 ПИШИ 0                                │
 ОБМЕН                                 │
 ВЛЕВО                                 │
 ПОКА НЕ ПУСТО                         │ возвращение
  {                                    │ на начало записи 
   ЕСЛИ ПРОБЕЛ ТО                      │ и подсчет
    { ОБМЕН ПЛЮС ОБМЕН }               │ числа переносов
   ВЛЕВО                               │
  }                                    │
КОНЕЦ                                  │
//─────────────────────────────────────┤
// описание                            │
ЭТО Ханой1-3                           │
 ЕСЛИ НЕ 1                             │
  ТО                                   │
   {                                   │
    МИНУС                              │ (#) уменьшаем кол-во колец
    Ханой1-2                           │
    Кольцо1-3                          │
    ЯЩИК-                              │ (##)
    Ханой2-3                           │
    ЯЩИК- ПЛЮС ЯЩИК+                   │ (###) увеличиваем кол-во колец
   }                                   │
 ИНАЧЕ { ЯЩИК+ Кольцо1-3 }             │
КОНЕЦ                                  │
//─────────────────────────────────────┤
// описание                            │
ЭТО Ханой1-2                           │
 ЕСЛИ НЕ 1                             │
  ТО                                   │
   {                                   │
    МИНУС                              │
    Ханой1-3                           │
    Кольцо1-2                          │
    ЯЩИК-                              │
    Ханой3-2                           │
    ЯЩИК- ПЛЮС ЯЩИК+                   │
   }                                   │
 ИНАЧЕ { ЯЩИК+ Кольцо1-2 }             │
КОНЕЦ                                  │
//─────────────────────────────────────┤
// описание                            │
ЭТО Ханой2-1                           │
 ЕСЛИ НЕ 1                             │
  ТО                                   │
   {                                   │
    МИНУС                              │
    Ханой2-3                           │
    Кольцо2-1                          │
    ЯЩИК-                              │
    Ханой3-1                           │
    ЯЩИК- ПЛЮС ЯЩИК+                   │
   }                                   │
 ИНАЧЕ { ЯЩИК+ Кольцо2-1 }             │
КОНЕЦ                                  │
//─────────────────────────────────────┤
// описание                            │
ЭТО Ханой2-3                           │
 ЕСЛИ НЕ 1                             │
  ТО                                   │
   {                                   │
    МИНУС                              │
    Ханой2-1                           │
    Кольцо2-3                          │
    ЯЩИК-                              │
    Ханой1-3                           │
    ЯЩИК- ПЛЮС ЯЩИК+                   │
   }                                   │
 ИНАЧЕ { ЯЩИК+ Кольцо2-3 }             │
КОНЕЦ                                  │
//─────────────────────────────────────┤
// описание                            │
ЭТО Ханой3-1                           │
 ЕСЛИ НЕ 1                             │
  ТО                                   │
   {                                   │
    МИНУС                              │
    Ханой3-2                           │
    Кольцо3-1                          │
    ЯЩИК-                              │
    Ханой2-1                           │
    ЯЩИК- ПЛЮС ЯЩИК+                   │
   }                                   │
 ИНАЧЕ { ЯЩИК+ Кольцо3-1 }             │
КОНЕЦ                                  │
//─────────────────────────────────────┤
// описание                            │
ЭТО Ханой3-2                           │
 ЕСЛИ НЕ 1                             │
  ТО                                   │
   {                                   │
    МИНУС                              │
    Ханой3-1                           │
    Кольцо3-2                          │
    ЯЩИК-                              │
    Ханой1-2                           │
    ЯЩИК- ПЛЮС ЯЩИК+                   │
   }                                   │
 ИНАЧЕ { ЯЩИК+ Кольцо3-2 }             │
КОНЕЦ                                  │
//─────────────────────────────────────┤
// описание                            │
ЭТО Кольцо1-3                          │
 ПИШИ 1 ВПРАВО ПИШИ 3 ВПРАВО           │
 ПИШИ ПРОБЕЛ ВПРАВО                    │
КОНЕЦ                                  │
//─────────────────────────────────────┤
// описание                            │
ЭТО Кольцо1-2                          │
 ПИШИ 1 ВПРАВО ПИШИ 2 ВПРАВО           │
 ПИШИ ПРОБЕЛ ВПРАВО                    │
КОНЕЦ                                  │
//─────────────────────────────────────┤
// описание                            │
ЭТО Кольцо2-1                          │
 ПИШИ 2 ВПРАВО ПИШИ 1 ВПРАВО           │
 ПИШИ ПРОБЕЛ ВПРАВО                    │
КОНЕЦ                                  │
//─────────────────────────────────────┤
// описание                            │
ЭТО Кольцо2-3                          │
 ПИШИ 2 ВПРАВО ПИШИ 3 ВПРАВО           │
 ПИШИ ПРОБЕЛ ВПРАВО                    │
КОНЕЦ                                  │
//─────────────────────────────────────┤
// описание                            │
ЭТО Кольцо3-1                          │
 ПИШИ 3 ВПРАВО ПИШИ 1 ВПРАВО           │
 ПИШИ ПРОБЕЛ ВПРАВО                    │
КОНЕЦ                                  │
//─────────────────────────────────────┤
// описание                            │
ЭТО Кольцо3-2                          │
 ПИШИ 3 ВПРАВО ПИШИ 2 ВПРАВО           │
 ПИШИ ПРОБЕЛ ВПРАВО                    │
КОНЕЦ                                  │
//─────────────────────────────────────┘

к о м м е н т а р и й  к у р а т о р а
В отличие от решения команды 3107, эта программа только для переноса с
1 на 3 (что не очень существенно), зато в программе есть
дополнительный сервис -- подсчет числа переносов.

Ну, что можно сказать: отлично! Просто, отлично Данил. Я верил, что ты
это сделаешь и оказался прав!
