Решение ханойских башен java

Towers of Hanoi

The ‘Towers of Hanoi’ is a classical problem used to illustrate the power of recursion. The puzzle goes as follows.

There are three poles and 64 discs of different sizes. Initially, all the discs are placed on the first pole with the largest disc at the bottom and the smallest one at the top. We need to move all the discs from the first pole to the third pole, with the smallest disc at the top and the largest at the bottom. We can move only one disc at a time (which should be the topmost disc) and at any point of time, a larger disc cannot be placed over a smaller one i.e. all the discs on a pole must be placed in such a way that the smallest is at the top and the largest at the bottom. The second pole can be used as an intermediate pole to help us in transferring the discs.

This puzzle can be solved using recursion. For a moment, assume that there are just two discs (disc 1 and 2; disc 2 being the larger one) on the first pole. The solution consists of three steps.

Step 1: Move disc 1 from pole 1 to pole 2.
Step 2: Move disc 2 from pole 1 to pole 3.
Step 3: Move disc 1 from pole 1 to pole 3.

Now, assume that disc 1 is not a single disc but a collection of discs. The procedure would be similar to the above three steps, but steps 1 and 3 would be a collection of steps. Step 1 would be to move the n-1 discs (assuming that there were a total of n discs) from pole 1 to pole 2. For moving these (n -1) discs, we again follow the same strategy of considering them as 1 disc plus a set of n-2 discs. Step 3 would also be similar. This gives us the recursive solution.

Recursive Algorithm

The recursive solution to move n discs from the start pole to the end pole using an auxiliary pole is given below.

Recursive Case – When n > 1
Step 1: Move (n-1) discs from start pole to auxiliary pole.
Step 2: Move the last disc from start pole to end pole.
Step 3: Move the (n-1) discs from auxiliary pole to end pole.
Steps 1 and 3 are recursive invocations of the same procedure.

Java Program

Public void solve(int n, String start, String auxiliary, String end) if (n == 1) System.out.println(start + ” -> ” + end);
> else solve(n – 1, start, end, auxiliary);
System.out.println(start + ” -> ” + end);
solve(n – 1, auxiliary, start, end);
>
>

Public static void main(String[] args) TowersOfHanoi towersOfHanoi = new TowersOfHanoi();
System.out.print(“Enter number of discs: “);
Scanner scanner = new Scanner(System.in);
int discs = scanner.nextInt();
towersOfHanoi.solve(discs, “A”, “B”, “C”);
>
>

n – the number of discs in the puzzle
start, auxiliary, end -the names of the three poles which will be used for printing the solution

We first check if the number of poles, n is equal to one. If so, the base case solution will be used which consists of moving a disc from the start peg to the end peg. If not, the recursive solution is used which consists of two recursive calls to the same procedure solve(). When we need to move n-1 discs from the start pole to the auxiliary pole, the auxiliary pole becomes the end pole and the end pole becomes the auxiliary pole. That is why we have written

Next we print ‘ start -> end ‘ which corresponds to moving the largest disc at the bottom from the start peg to the end peg.

Finally, we have recursive invocation of solve(). Here, the auxiliary peg becomes the start peg and the start peg becomes the auxiliary peg.

Источник

6.3. Java примеры – Как использовать метод для решения задачи о Ханойской башне

Как использовать метод для решения задачи о Ханойской башне в Java?

Решение

В этом примере показано, как использовать метод для решения задачи о Ханойской башне (для 3 дисков).

public class MainClass < public static void main(String[] args) < int nDisks = 3; doTowers(nDisks, 'A', 'B', 'C'); >public static void doTowers(int topN, char from, char inter, char to) < if (topN == 1) < System.out.println("Диск 1 от " + from + " до " + to); >else < doTowers(topN - 1, from, to, inter); System.out.println("Диск " + topN + " от " + from + " до " + to); doTowers(topN - 1, inter, from, to); >> > 

Результат

Вышеприведенный пример кода даст следующий результат:

Диск 1 от A до C Диск 2 от A до B Диск 1 от C до B Диск 3 от A до C Диск 1 от B до A Диск 2 от B до C Диск 1 от A до C 

Ниже приведен еще один пример Ханойской башни.

public class TowersOfHanoi < public static void move(int n, int startPole, int endPole) < if (n == 0) < return; >int intermediatePole = 6 - startPole - endPole; move(n-1, startPole, intermediatePole); System.out.println("Переместить " +n + " из " + startPole + " в " +endPole); move(n-1, intermediatePole, endPole); > public static void main(String[] args) < move(5, 1, 3); >> 

Результат

Вышеприведенный пример кода даст следующий результат:

Переместить 1 из 1 в 3 Переместить 2 из 1 в 2 Переместить 1 из 3 в 2 Переместить 3 из 1 в 3 Переместить 1 из 2 в 1 Переместить 2 из 2 в 3 Переместить 1 из 1 в 3 Переместить 4 из 1 в 2 Переместить 1 из 3 в 2 Переместить 2 из 3 в 1 Переместить 1 из 2 в 1 Переместить 3 из 3 в 2 Переместить 1 из 1 в 3 Переместить 2 из 1 в 2 Переместить 1 из 3 в 2 Переместить 5 из 1 в 3 Переместить 1 из 2 в 1 Переместить 2 из 2 в 3 Переместить 1 из 1 в 3 Переместить 3 из 2 в 1 Переместить 1 из 3 в 2 Переместить 2 из 3 в 1 Переместить 1 из 2 в 1 Переместить 4 из 2 в 3 Переместить 1 из 1 в 3 Переместить 2 из 1 в 2 Переместить 1 из 3 в 2 Переместить 3 из 1 в 3 Переместить 1 из 2 в 1 Переместить 2 из 2 в 3 Переместить 1 из 1 в 3 

Оглавление

• 1. Java примеры – Использование кода на практике
• 2. Java примеры – Окружающая среда
• 2.1. Java примеры – Скомпилировать файл
• 2.2. Java примеры – Установить путь к нескольким классам
• 2.3. Java примеры – Отладка java-файла
• 2.4. Java примеры – Установить путь к классу
• 2.5. Java примеры – Просмотреть текущий путь класса
• 2.6. Java примеры – Установить назначение файла класса
• 2.7. Java примеры – Запустить скомпилированный java-файл класса
• 2.8. Java примеры – Узнать версию Java
• 2.9. Java примеры – Установить путь к классу в .jar-файле или .zip-файле
• 3. Java примеры – Строки
• 3.1. Java примеры – Сравнить две строки
• 3.2. Java примеры – Найти последнее вхождение подстроки внутри подстроки
• 3.3. Java примеры – Удалить нужный символ из строки
• 3.4. Java примеры – Заменить символ в строке
• 3.5. Java примеры – Вывод в обратном порядке
• 3.6. Java примеры – Нахождение символа или слова в строке
• 3.7. Java примеры – Разбиение строки на слова и символы
• 3.8. Java примеры – Преобразование строки в верхний регистр
• 3.9. Java примеры – Найти слово в строке
• 3.10. Java примеры – Сравнить производительность создания строки
• 3.11. Java примеры – Оптимизировать создание строк
• 3.12. Java примеры – Форматирование строк
• 3.13. Java примеры – Конкатенация строк
• 3.14. Java примеры – Определить код Юникода символа в строке
• 3.15. Java примеры – Буферизация строк
• 4. Java примеры – Массивы
• 4.1. Java примеры – Сортировка массива и поиск элемента
• 4.2. Java примеры – Метод сортировки массива, вставить элемент в массив
• 4.3. Java примеры – Размер двумерного массива
• 4.4. Java примеры – Обратный порядок массива, переворачиваем массив
• 4.5. Java примеры – Как выводить массивы и двумерные массивы в консоль
• 4.6. Java примеры – Найти максимальный и минимальный элемент массива
• 4.7. Java примеры – Соединить два массива в один
• 4.8. Java примеры – Как заполнить массив числами
• 4.9. Java примеры – Увеличить массив после инициализации
• 4.10. Java примеры – Сравнение двух массивов
• 4.11. Java примеры – Удаление элемента из массива
• 4.12. Java примеры – Удаление массива из другого массива
• 4.13. Java примеры – Одинаковые элементы массивов
• 4.14. Java примеры – Поиск в массиве
• 4.15. Java примеры – Равенство двух массивов
• 4.16. Java примеры – Сравнить массивы
• 5. Java примеры – Дата и время
• 5.1. Java примеры – Форматирование времени в формате AM-PM
• 5.2. Java примеры – Получение названия и номера текущего месяца
• 5.3. Java примеры – Получить текущее время в часах и минутах
• 5.4. Java примеры – Вывести текущее время и дату
• 5.5. Java примеры – Вывести текущее время в 24-часовом формате
• 5.6. Java примеры – Получить текущий месяц
• 5.7. Java примеры – Получить текущие секунды
• 5.8. Java примеры – Получить короткое название месяца
• 5.9. Java примеры – Получить день недели
• 5.10. Java примеры – Добавление времени к дате
• 5.11. Java примеры – Отображение времени в формате другой страны
• 5.12. Java примеры – Отображение времени на разных языках
• 5.13. Java примеры – Прокрутить часы и месяцы
• 5.14. Java примеры – Получить номер недели и месяц в году
• 5.15. Java примеры – Форматы текущей даты
• 6. Java примеры – Методы
• 6.1. Java примеры – Перезагрузка методов
• 6.2. Java примеры – Вывод массива с использованием метода
• 6.3. Java примеры – Решение Ханойской башни
• 6.4. Java примеры – Последовательность чисел Фибоначчи
• 6.5. Java примеры – Вычисление факториала числа
• 6.6. Java примеры – Переопределение метода
• 6.7. Java примеры – Вывод массива с использованием метода
• 6.8. Java примеры – Использование оператора break
• 6.9. Java примеры – Использование оператора continue
• 6.10. Java примеры – Использование метки в методе
• 6.11. Java примеры – Использование операторов enum и switch
• 6.12. Java примеры – Использование конструктора enum

Источник

Проблема с Ханойской башней

Ханойская башня — это математическая головоломка, состоящая из трех стержней и n диски разных размеров, которые могут надвигаться на любой стержень.

Головоломка начинается с аккуратной stack дисков в порядке возрастания размера на одном стержне, самый маленький вверху, образуя коническую форму. Цель головоломки — переместить всю стопку на другой стержень, соблюдая следующие простые правила:

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

Минимальное количество ходов, необходимое для решения головоломки Ханойской башни, равно 2 n -1 , куда n это общее количество дисков.

Анимированное решение головоломки Ханойская башня для n = 4 можно увидеть здесь. Ниже приведены шаги, которые были предприняты предлагаемым решением:

• Переместить диск 1 с 1 на 2
• Переместить диск 2 с 1 на 3
• Переместите диск 1 со 2 на 3
• Переместить диск 3 с 1 на 2
• Переместить диск 1 с 3 на 1
• Переместите диск 2 с 3 на 2
• Переместить диск 1 с 1 на 2
• Переместить диск 4 с 1 на 3
• Переместите диск 1 со 2 на 3
• Переместить диск 2 с 2 на 1
• Переместить диск 1 с 3 на 1
• Переместите диск 3 со 2 на 3
• Переместить диск 1 с 1 на 2
• Переместить диск 2 с 1 на 3
• Переместите диск 1 со 2 на 3

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

Двигаться n диски от полюса 1 до полюса 3:

• Шаг n-1 диски с 1 по 2. Это оставляет диск n один на 1 полюсе.
• Переместить диск n от 1 до 3.
• Шаг n-1 диски со 2 по 3, поэтому они сидят на диске n .

Алгоритм может быть реализован следующим образом на C++, Java и Python:

Источник