Ханойская башня

Задача про ханойскую башню, применение

Задача Ханойской башни является одной из самых известных головоломок Дальнего Востока. Задача состоит в том чтобы переместить все кольца, нанизанные на один из стержней на другой стержень за наименьшее число ходов. За один ход можно переносить только одно кольцо. Кольца расположены в виде пирамиды от большего к меньшему, и при перемещении колец нельзя класть большее кольцо на меньшее.

Задача легко решается с помощью рекурсии, рассмотрим подробнее реализацию класса.  В общем виде алгоритм решения задачи выглядит так,  где n — количество колец:

   public class HanoiTower
   {
      int numRings; // число колец
 
     public HanoiTower( int rings )
     {
       numRings = rings;
     } 

     // применение рекурсии в методе класса HanoiTower  
                             
     public void solveHanoi( int rings, int sourceBar, int destinationBar,
        int tempBar )                                                      
    {   
        // частный случай -- есть только одно кольцо
                                   
       if ( rings == 1 )                                                  
        {                                                                  
           System.out.printf( "\n%d --> %d", sourceBar, destinationBar );  
           return;                                                         
        } // end if 
                                                       
          // применение рекурсии - переместить кольцо на временный стержень, 
          // затем на нужный 
       
        solveHanoi( rings - 1, sourceBar, tempBar, destinationBar );    
        
         // перместить последнее кольцо с исходного стержня на нужный стержень                                                                              
        System.out.printf( "\n%d --> %d", sourceBar, destinationBar ); 
        
         // переместить ( rings - 1 ) колец с временного стержня на нужный стержень                                                                     
        solveHanoi( rings - 1, tempBar, destinationBar, sourceBar );      
     } // конец метода solveHanoi                                           
  } // конец класса HanoiTower

Следующий код тестирует решение задачи, на строке 12 создается объект класса HanoiTower, в качестве параметра передается число колец, которые необходимо переместить с одного кольца на другое. На строке 15  вызывается рекурсивный метод solveHanoi, который выводит на экран шаги решения задачи.

  
   // Тестируем решение задачи Ханойской башни.
 
   public class HanoiTest
   {
      public static void main( String args[] )
      {
        int startBar = 1;   // первому стержню присваиваем значение 1
        int endBar = 3;     // конечному стержню присваиваем значение 1
        int tempBar = 2;    // временному стержню присваиваем значение 1
        int totalRings = 3; // число колец
        HanoiTower towersOfHanoi = new HanoiTower( totalRings );

        // нерекурсивный вызов метода: переместить все кольца
        towersOfHanoi.solveHanoi( totalRings, startBar, endBar, tempBar );
     } // конец main
  } // конец класса HanoiTest

Результат выполнения программы:

1 --> 3
1 --> 2
3 --> 2
1 --> 3
2 --> 1
2 --> 3
1 --> 3