Задача 8. (15 баллов) Ханойская башня.
Написать программу, которая решает на поле исполнителя задачу о
Ханойской башне.

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

п р о в е р к а  к у р а т о р а
Выставляя на конкурс эту задачу (и даже не решая ее сам) я думал, что
Первушин Данил не будет Первушиным Данилом, если ее не решит. Мои надежды
блестяще оправдались!

Команда 3115
------------
.\15\15.txt
.\15\1581.coc

Оценка: 15

Автор решения 1581 Первушин Данила
Описание алгоритма:
   Чтобы решить Ханой для одного кольца,
надо просто перенести кольцо с первого столбца на третий.
А если колец больше, тогда нужно N-1 кольцо 
(N-начальное количество колец) перенести с первого столбца на второй,
оставшееся кольцо перенести с первого столбца на третий, а затем N-1 кольцо 
со второго столбца на третий. Тосно также, чтобы перенести N-1 кольцо
со второго столбца на третий нужно: перенести N-2 кольца с второго столбца
на первый, оставшееся на втором столбце кольцо перенести на третий
и N-2 кольца с первого столбца перенести на третий.
   Невооружённым взглядом можно заметить, что задача
рекурсивная. Но одной рекурсивной подпрограммы не хватает, поэтому их 6 
(каждой из двух видов: Ханой и Кольцо), потому что существует по 6 вариантов 
переноса кольца и башни с одного стержня на другой.
   Я решил для удобства кольцо обозначать кубиком, причем чем выше кубик - 
тем меньше кольцо, и не менять положения колец по вертикали.
   Перед началом выполнения программы "Башня" из кубиков находится
во втором столбце поля, а Кукарача должен находится слева от нижнего кубика.
Выше и ниже столбца из "колец" должна оставаться хотя бы одна пустая строка.


//-------------------------------------
// описание
ЭТО Ханойская_башня                    
 ВПРАВО                                
 ЕСЛИ НЕ ПУСТО                         
  ТО Ханой1-3                          
КОНЕЦ // Ханойская_башня               
//-------------------------------------
// описание                            
ЭТО Шаг                                
 ВЛЕВО                                 
 ВВЕРХ                                 
 ВПРАВО                                
КОНЕЦ // Шаг                           
//-------------------------------------
// описание                            
ЭТО Ханой1-3                           
 Шаг                                   
 ЕСЛИ НЕ ПУСТО                         
  ТО
   {                                   
    Ханой1-2                           
    ПОВТОРИ 2 ВЛЕВО
    Ищи_верхнее
    ВЛЕВО                              
    Кольцо1-3                          
    ВПРАВО                             
    Ханой2-3                           
   }                                   
 ИНАЧЕ                                 
  {                                    
   Поправка                            
   Кольцо1-3                           
  }                                    
КОНЕЦ // Ханой1-3                      
//-------------------------------------
// описание
ЭТО Ханой1-2                           
 Шаг                                   
 ЕСЛИ НЕ ПУСТО                         
  ТО                                   
   {
    Ханой1-3                           
    ПОВТОРИ 2 ВЛЕВО                    
    Ищи_верхнее
    ВЛЕВО
    Кольцо1-2                          
    ПОВТОРИ 4 ВПРАВО                   
    Ханой3-2                           
   }                                   
 ИНАЧЕ                                 
  {                                    
   Поправка                            
   Кольцо1-2                           
  }                                    
КОНЕЦ // Ханой1-2                      
//-------------------------------------
// описание                            
ЭТО Ханой2-3
 Шаг                                   
 ЕСЛИ НЕ ПУСТО                         
  ТО                                   
   {                                   
    Ханой2-1
    ВПРАВО                             
    Ищи_верхнее                        
    ВЛЕВО
    Кольцо2-3
    ВНИЗ                               
    ПОВТОРИ 3 ВЛЕВО                    
    ВВЕРХ                              
    ВПРАВО                             
    Ханой1-3                           
   }                                   
 ИНАЧЕ                                 
  {                                    
   Поправка                            
   Кольцо2-3                           
  }                                    
КОНЕЦ // Ханой2-3                      
//-------------------------------------
// описание                            
ЭТО Ханой3-1                           
 Шаг                                   
 ЕСЛИ НЕ ПУСТО                         
  ТО
   {                                   
    Ханой3-2                           
    ПОВТОРИ 4 ВПРАВО
    Ищи_верхнее
    ВВЕРХ                              
    ПОВТОРИ 2 ВПРАВО                   
    ВНИЗ                               
    ВЛЕВО                              
    Кольцо3-1                          
    ВПРАВО                             
    Ханой2-1                           
   }                                   
 ИНАЧЕ                                 
  {                                    
   Поправка                            
   ВВЕРХ                               
   ПОВТОРИ 2 ВПРАВО
   ВНИЗ                                
   Кольцо3-1                           
  }                                    
КОНЕЦ // Ханой3-1                      
//-------------------------------------
// описание                            
ЭТО Ханой3-2                           
 Шаг
 ЕСЛИ НЕ ПУСТО
  ТО                                   
   {                                   
    Ханой3-1                           
    ПОВТОРИ 4 ВПРАВО                   
    Ищи_верхнее                        
    ВВЕРХ                              
    ПОВТОРИ 2 ВПРАВО                   
    ВНИЗ                               
    ВЛЕВО                              
    Кольцо3-2                          
    ВНИЗ                               
    ПОВТОРИ 3 ВЛЕВО                    
    ВВЕРХ
    ВПРАВО                             
    Ханой1-2                           
   }                                   
 ИНАЧЕ                                 
  {
   Поправка                            
   ВВЕРХ                               
   ПОВТОРИ 2 ВПРАВО
   ВНИЗ
   Кольцо3-2                           
  }                                    
КОНЕЦ // Ханой3-2                      
//-------------------------------------
// описание                            
ЭТО Ханой2-1                           
 Шаг                                   
 ЕСЛИ НЕ ПУСТО                         
  ТО                                   
   {                                   
    Ханой2-3                           
    ВПРАВО                             
    Ищи_верхнее
    ВВЕРХ                              
    ПОВТОРИ 2 ВПРАВО                   
    ВНИЗ                               
    ВЛЕВО                              
    Кольцо2-1
    ПОВТОРИ 4 ВПРАВО                   
    Ханой3-1                           
   }
 ИНАЧЕ
  {                                    
   Поправка                            
   ВВЕРХ                               
   ПОВТОРИ 2 ВПРАВО                    
   ВНИЗ                                
   Кольцо2-1                           
  }                                    
                                       
КОНЕЦ // Ханой2-1                      
//-------------------------------------
// описание                            
ЭТО Кольцо1-2                          
 ПОВТОРИ 3 ВПРАВО
 ВВЕРХ                                 
КОНЕЦ // Кольцо1-2                     
//-------------------------------------
// описание                            
ЭТО Кольцо1-3
 ПОВТОРИ 6 ВПРАВО                      
 ПОВТОРИ 3 ВЛЕВО                       
 ВВЕРХ
КОНЕЦ // Кольцо1-3
//-------------------------------------
// описание                            
ЭТО Кольцо2-1                          
 ПОВТОРИ 3 ВЛЕВО                       
 ВПРАВО                                
 ВВЕРХ                                 
КОНЕЦ // Кольцо2-1                     
//-------------------------------------
// описание                            
ЭТО Кольцо3-1                          
 ПОВТОРИ 6 ВЛЕВО                       
 ВПРАВО                                
 ВВЕРХ
КОНЕЦ // Кольцо3-1                     
//-------------------------------------
// описание                            
ЭТО Кольцо2-3                          
 ПОВТОРИ 3 ВПРАВО
 ПОВТОРИ 3 ВЛЕВО                       
 ВВЕРХ                                 
КОНЕЦ // Кольцо2-3
//-------------------------------------
// описание                            
ЭТО Кольцо3-2                          
 ПОВТОРИ 3 ВЛЕВО                       
 ВВЕРХ                                 
 ПОВТОРИ 2 ВЛЕВО                       
КОНЕЦ // Кольцо3-2                     
//-------------------------------------
// описание                            
ЭТО Поправка                           
  ВПРАВО                               
  Сдвигай                              
КОНЕЦ // Поправка                      
//-------------------------------------
// описание                            
ЭТО Сдвигай                            
 ВПРАВО                                
 ВНИЗ                                  
 ВЛЕВО
 ЕСЛИ НЕ ПУСТО                         
  ТО { Сдвигай ВВЕРХ }                 
 ИНАЧЕ ПОВТОРИ 2 ВЛЕВО
КОНЕЦ // Сдвигай
//-------------------------------------
// описание                            
ЭТО Ищи_верхнее                        
 ПОКА ПУСТО                            
  {                                    
   ВЛЕВО                               
   ВНИЗ                                
   ВПРАВО                              
  }                                    
КОНЕЦ // Ищи_верхнее                   


к о м м е н т а р и й  к у р а т о р а

Данил, прими мои поздравления! Заставить Кукарачу решать Ханойскую
башню -- такого еще не было в истории программирования!

Твое решение двигать диски, не смещая их по вертикали -- очень
эффективный продуманный программисткий ход (хотя он и снижает внешнюю
наглядность).

