Поиск по сайту:

Ханойская башня — алгоритм и реализация на Java

Ханойская башня — классическая задача в мире программирования. Постановка задачи состоит из трех стержней/штифтов и n дисков.

Диски можно переставлять с одного стержня на другой. n дисков разного размера.

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

Настройка Ханойской башни по умолчанию

Любопытный факт: эту игру изобрел французский математик Эдуард Лука в 19 веке. Это связано с легендой об индуистском храме, где головоломка якобы использовалась для повышения умственной дисциплины молодых священников.

Постановка задачи

Move all the disks stacked on the first tower over to the last tower using a helper tower in the middle. While moving the disks, certain rules must be followed. These are : 

1. Only one disk can be moved.

2. A larger disk can not be placed on a smaller disk.

Итак, вам нужно переместить все диски из первой башни в последнюю. Вы можете перемещать только один диск за раз и никогда не размещать меньший диск поверх большего.

Для этого у вас есть дополнительная башня, она называется вспомогательной/вспомогательной башней.

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

Теоретическое решение проблемы Ханойской башни

Назовем башни A,B,C, а диски 1,2,3.

Решим этот вопрос с помощью простой рекурсии. Чтобы доставить три диска к финальной башне, вам нужно:

  1. Отнесите диски номер 1 и 2 в башню B.
  2. Переместите диск номер 3 в башню C.
  3. Возьмите диски 1 и 2 из B в C.

Конечно, вы не можете сделать это так из-за ограничений. Однако мы можем использовать это для создания функции, которая делает это рекурсивно.

В функции, которую мы пишем, мы будем печатать движение дисков.

Реализация решения для Ханойской башни на Java

Давайте начнем с понимания двух основных частей кода для решения задачи о Ханойской башне.

1. Базовый случай

Базовый случай в нашем коде — это когда у нас есть только один диск. То есть n=1.

 if (n == 1)
        {
            System.out.println("Take disk 1 from rod " +  from_rod + " to rod " + to_rod);
            return;
        }

2. Рекурсивные вызовы

Рекурсивные вызовы для решения Ханойской башни следующие:

 towerOfHanoi(n-1, from_rod, helper_rod, to_rod);
        System.out.println("Take disk " + n + " from rod " +  from_rod + " to rod " + to_rod);
        towerOfHanoi(n-1, helper_rod, to_rod, from_rod);
    }

Они эквивалентны:

  1. Переместите верхние n-1 дисков во вспомогательную башню.
  2. Переместите 1 диск с исходного стержня на целевой.
  3. Перенесите n-1 дисков со вспомогательного диска на целевой стержень.

Полная Java-реализация Ханойской башни

package com.JournalDev;
public class Main {
    static void towerOfHanoi(int n, char from_rod, char to_rod, char helper_rod)
    {
        if (n == 1)
        {
            System.out.println("Take disk 1 from rod " +  from_rod + " to rod " + to_rod);
            return;
        }
        towerOfHanoi(n-1, from_rod, helper_rod, to_rod);
        System.out.println("Take disk " + n + " from rod " +  from_rod + " to rod " + to_rod);
        towerOfHanoi(n-1, helper_rod, to_rod, from_rod);
    }

    public static void main(String args[])
    {
        int n = 5;
        towerOfHanoi(n,'A','C', 'B');
    }

}

Вывод для кода:

Take disk 1 from rod A to rod C
Take disk 2 from rod A to rod B
Take disk 1 from rod C to rod B
Take disk 3 from rod A to rod C
Take disk 1 from rod B to rod A
Take disk 2 from rod B to rod C
Take disk 1 from rod A to rod C

Мы можем понять этот процесс, используя следующую иллюстрацию. Вы можете запустить код для любого количества дисков.

Выход для n=5:

Take disk 1 from rod A to rod C
Take disk 2 from rod A to rod B
Take disk 1 from rod C to rod B
Take disk 3 from rod A to rod C
Take disk 1 from rod B to rod A
Take disk 2 from rod B to rod C
Take disk 1 from rod A to rod C
Take disk 4 from rod A to rod B
Take disk 1 from rod C to rod B
Take disk 2 from rod C to rod A
Take disk 1 from rod B to rod A
Take disk 3 from rod C to rod B
Take disk 1 from rod A to rod C
Take disk 2 from rod A to rod B
Take disk 1 from rod C to rod B
Take disk 5 from rod A to rod C
Take disk 1 from rod B to rod A
Take disk 2 from rod B to rod C
Take disk 1 from rod A to rod C
Take disk 3 from rod B to rod A
Take disk 1 from rod C to rod B
Take disk 2 from rod C to rod A
Take disk 1 from rod B to rod A
Take disk 4 from rod B to rod C
Take disk 1 from rod A to rod C
Take disk 2 from rod A to rod B
Take disk 1 from rod C to rod B
Take disk 3 from rod A to rod C
Take disk 1 from rod B to rod A
Take disk 2 from rod B to rod C
Take disk 1 from rod A to rod C

Формула для расчета количества шагов для n дисков:

(2^n)-1

Заключение

Вот как вы решаете Ханойскую башню, используя рекурсию. Надеюсь, вам было интересно учиться вместе с нами!