Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 12.4 Задача о Ханойской башне

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

Question

Даны три стержня, обозначенные как `A` , `B` и `C` . В начальном состоянии на стержне `A` находятся \(n\) дисков, расположенных сверху вниз в порядке от меньшего к большему. Нужно переместить эти \(n\) дисков на стержень `C` , сохранив их исходный порядок (как показано на рисунке 12-10). Во время перемещения дисков необходимо соблюдать следующие правила.

1. Диск можно снять только с вершины одного стержня и положить только на вершину другого стержня.
2. За один раз можно перемещать только один диск.
3. Меньший диск всегда должен лежать на большем.

Рисунок 12-10 Пример задачи о Ханойской башне

Обозначим задачу о Ханойской башне размера \(i\) как \(f(i)\) . Например, \(f(3)\) означает задачу перемещения 3 дисков со стержня `A` на стержень `C` .

### 1. Рассмотрим базовые случаи

Как показано на рисунке 12-11, для задачи \(f(1)\) , то есть когда имеется только один диск, достаточно просто переместить его напрямую со стержня `A` на стержень `C` .

<1><2>

Рисунок 12-11 Решение задачи размера 1

Как показано на рисунке 12-12, для задачи \(f(2)\) , то есть когда есть два диска, поскольку меньший диск все время должен лежать на большем, приходится использовать `B` как вспомогательный стержень.

1. Сначала переместить верхний маленький диск с `A` на `B` .
2. Затем переместить большой диск с `A` на `C` .
3. Наконец, переместить маленький диск с `B` на `C` .

<1><2><3><4>

Рисунок 12-12 Решение задачи размера 2

Процесс решения задачи \(f(2)\) можно кратко описать так: переместить два диска с `A` на `C` с помощью `B` . Здесь `C` называется целевым стержнем, а `B` - буферным стержнем.

### 2. Разбиение на подзадачи

Для задачи \(f(3)\) , то есть когда имеется три диска, ситуация становится сложнее.

Поскольку решения \(f(1)\) и \(f(2)\) уже известны, можно подойти к задаче с точки зрения стратегии «разделяй и властвуй» и рассматривать два верхних диска на `A` как единое целое, выполняя шаги, показанные на рисунке 12-13. Так три диска успешно перемещаются с `A` на `C` .

1. Сделать `B` целевым стержнем, а `C` буферным, и переместить два диска с `A` на `B` .
2. Переместить оставшийся один диск с `A` напрямую на `C` .
3. Сделать `C` целевым стержнем, а `A` буферным, и переместить два диска с `B` на `C` .

<1><2><3><4>

Рисунок 12-13 Решение задачи размера 3

Иначе говоря, мы разбиваем задачу \(f(3)\) на две подзадачи \(f(2)\) и одну подзадачу \(f(1)\) . Если последовательно решить эти три подзадачи, исходная задача тоже будет решена. Это показывает, что подзадачи независимы и что их решения можно объединить.

Таким образом, можно сформулировать показанную на рисунке 12-14 стратегию «разделяй и властвуй» для задачи о Ханойской башне: исходная задача \(f(n)\) разбивается на две подзадачи \(f(n-1)\) и одну подзадачу \(f(1)\) , которые затем решаются в следующем порядке.

1. Переместить \(n-1\) дисков с `A` на `B` с помощью `C` .
2. Переместить оставшийся \(1\) диск напрямую с `A` на `C` .
3. Переместить \(n-1\) дисков с `B` на `C` с помощью `A` .

Для двух подзадач \(f(n-1)\) можно применять тот же способ рекурсивного разбиения, пока не будет достигнута наименьшая подзадача \(f(1)\) . А решение для \(f(1)\) уже известно и требует всего одного перемещения.

Рисунок 12-14 Стратегия разделяй и властвуй для решения задачи о Ханойской башне

### 3. Реализация кода

В коде мы объявляем рекурсивную функцию `dfs(i, src, buf, tar)` , которая перемещает \(i\) верхних дисков со стержня `src` на целевой стержень `tar` с помощью буферного стержня `buf` :

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
hanota.py

    def move(src: list[int], tar: list[int]):
        """Переместить один диск"""
        # Снять диск с вершины src
        pan = src.pop()
        # Положить диск на вершину tar
        tar.append(pan)

    def dfs(i: int, src: list[int], buf: list[int], tar: list[int]):
        """Решить задачу Ханойской башни f(i)"""
        # Если в src остался только один диск, сразу переместить его в tar
        if i == 1:
            move(src, tar)
            return
        # Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar
        dfs(i - 1, src, tar, buf)
        # Подзадача f(1): переместить оставшийся один диск из src в tar
        move(src, tar)
        # Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src
        dfs(i - 1, buf, src, tar)

    def solve_hanota(A: list[int], B: list[int], C: list[int]):
        """Решить задачу Ханойской башни"""
        n = len(A)
        # Переместить верхние n дисков из A в C с помощью B
        dfs(n, A, B, C)

hanota.cpp

    /* Переместить один диск */
    void move(vector<int> &src, vector<int> &tar) {
        // Снять диск с вершины src
        int pan = src.back();
        src.pop_back();
        // Положить диск на вершину tar
        tar.push_back(pan);
    }

    /* Решить задачу Ханойской башни f(i) */
    void dfs(int i, vector<int> &src, vector<int> &buf, vector<int> &tar) {
        // Если в src остался только один диск, сразу переместить его в tar
        if (i == 1) {
            move(src, tar);
            return;
        }
        // Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar
        dfs(i - 1, src, tar, buf);
        // Подзадача f(1): переместить оставшийся один диск из src в tar
        move(src, tar);
        // Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src
        dfs(i - 1, buf, src, tar);
    }

    /* Решить задачу Ханойской башни */
    void solveHanota(vector<int> &A, vector<int> &B, vector<int> &C) {
        int n = A.size();
        // Переместить верхние n дисков из A в C с помощью B
        dfs(n, A, B, C);
    }

hanota.java

    /* Переместить один диск */
    void move(List<Integer> src, List<Integer> tar) {
        // Снять диск с вершины src
        Integer pan = src.remove(src.size() - 1);
        // Положить диск на вершину tar
        tar.add(pan);
    }

    /* Решить задачу Ханойской башни f(i) */
    void dfs(int i, List<Integer> src, List<Integer> buf, List<Integer> tar) {
        // Если в src остался только один диск, сразу переместить его в tar
        if (i == 1) {
            move(src, tar);
            return;
        }
        // Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar
        dfs(i - 1, src, tar, buf);
        // Подзадача f(1): переместить оставшийся один диск из src в tar
        move(src, tar);
        // Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src
        dfs(i - 1, buf, src, tar);
    }

    /* Решить задачу Ханойской башни */
    void solveHanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        int n = A.size();
        // Переместить верхние n дисков из A в C с помощью B
        dfs(n, A, B, C);
    }

hanota.cs

    /* Переместить один диск */
    void Move(List<int> src, List<int> tar) {
        // Снять диск с вершины src
        int pan = src[^1];
        src.RemoveAt(src.Count - 1);
        // Положить диск на вершину tar
        tar.Add(pan);
    }

    /* Решить задачу Ханойской башни f(i) */
    void DFS(int i, List<int> src, List<int> buf, List<int> tar) {
        // Если в src остался только один диск, сразу переместить его в tar
        if (i == 1) {
            Move(src, tar);
            return;
        }
        // Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar
        DFS(i - 1, src, tar, buf);
        // Подзадача f(1): переместить оставшийся один диск из src в tar
        Move(src, tar);
        // Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src
        DFS(i - 1, buf, src, tar);
    }

    /* Решить задачу Ханойской башни */
    void SolveHanota(List<int> A, List<int> B, List<int> C) {
        int n = A.Count;
        // Переместить верхние n дисков из A в C с помощью B
        DFS(n, A, B, C);
    }

hanota.go

    /* Переместить один диск */
    func move(src, tar *list.List) {
        // Снять диск с вершины src
        pan := src.Back()
        // Положить диск на вершину tar
        tar.PushBack(pan.Value)
        // Убрать верхний диск из src
        src.Remove(pan)
    }

    /* Решить задачу Ханойской башни f(i) */
    func dfsHanota(i int, src, buf, tar *list.List) {
        // Если в src остался только один диск, сразу переместить его в tar
        if i == 1 {
            move(src, tar)
            return
        }
        // Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar
        dfsHanota(i-1, src, tar, buf)
        // Подзадача f(1): переместить оставшийся один диск из src в tar
        move(src, tar)
        // Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src
        dfsHanota(i-1, buf, src, tar)
    }

    /* Решить задачу Ханойской башни */
    func solveHanota(A, B, C *list.List) {
        n := A.Len()
        // Переместить верхние n дисков из A в C с помощью B
        dfsHanota(n, A, B, C)
    }

hanota.swift

    /* Переместить один диск */
    func move(src: inout [Int], tar: inout [Int]) {
        // Снять диск с вершины src
        let pan = src.popLast()!
        // Положить диск на вершину tar
        tar.append(pan)
    }

    /* Решить задачу Ханойской башни f(i) */
    func dfs(i: Int, src: inout [Int], buf: inout [Int], tar: inout [Int]) {
        // Если в src остался только один диск, сразу переместить его в tar
        if i == 1 {
            move(src: &src, tar: &tar)
            return
        }
        // Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar
        dfs(i: i - 1, src: &src, buf: &tar, tar: &buf)
        // Подзадача f(1): переместить оставшийся один диск из src в tar
        move(src: &src, tar: &tar)
        // Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src
        dfs(i: i - 1, src: &buf, buf: &src, tar: &tar)
    }

    /* Решить задачу Ханойской башни */
    func solveHanota(A: inout [Int], B: inout [Int], C: inout [Int]) {
        let n = A.count
        // Хвост списка соответствует вершине столбца
        // Переместить верхние n дисков из src в C с помощью B
        dfs(i: n, src: &A, buf: &B, tar: &C)
    }

hanota.js

    /* Переместить один диск */
    function move(src, tar) {
        // Снять диск с вершины src
        const pan = src.pop();
        // Положить диск на вершину tar
        tar.push(pan);
    }

    /* Решить задачу Ханойской башни f(i) */
    function dfs(i, src, buf, tar) {
        // Если в src остался только один диск, сразу переместить его в tar
        if (i === 1) {
            move(src, tar);
            return;
        }
        // Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar
        dfs(i - 1, src, tar, buf);
        // Подзадача f(1): переместить оставшийся один диск из src в tar
        move(src, tar);
        // Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src
        dfs(i - 1, buf, src, tar);
    }

    /* Решить задачу Ханойской башни */
    function solveHanota(A, B, C) {
        const n = A.length;
        // Переместить верхние n дисков из A в C с помощью B
        dfs(n, A, B, C);
    }

hanota.ts

    /* Переместить один диск */
    function move(src: number[], tar: number[]): void {
        // Снять диск с вершины src
        const pan = src.pop();
        // Положить диск на вершину tar
        tar.push(pan);
    }

    /* Решить задачу Ханойской башни f(i) */
    function dfs(i: number, src: number[], buf: number[], tar: number[]): void {
        // Если в src остался только один диск, сразу переместить его в tar
        if (i === 1) {
            move(src, tar);
            return;
        }
        // Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar
        dfs(i - 1, src, tar, buf);
        // Подзадача f(1): переместить оставшийся один диск из src в tar
        move(src, tar);
        // Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src
        dfs(i - 1, buf, src, tar);
    }

    /* Решить задачу Ханойской башни */
    function solveHanota(A: number[], B: number[], C: number[]): void {
        const n = A.length;
        // Переместить верхние n дисков из A в C с помощью B
        dfs(n, A, B, C);
    }

hanota.dart

    /* Переместить один диск */
    void move(List<int> src, List<int> tar) {
      // Снять диск с вершины src
      int pan = src.removeLast();
      // Положить диск на вершину tar
      tar.add(pan);
    }

    /* Решить задачу Ханойской башни f(i) */
    void dfs(int i, List<int> src, List<int> buf, List<int> tar) {
      // Если в src остался только один диск, сразу переместить его в tar
      if (i == 1) {
        move(src, tar);
        return;
      }
      // Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar
      dfs(i - 1, src, tar, buf);
      // Подзадача f(1): переместить оставшийся один диск из src в tar
      move(src, tar);
      // Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src
      dfs(i - 1, buf, src, tar);
    }

    /* Решить задачу Ханойской башни */
    void solveHanota(List<int> A, List<int> B, List<int> C) {
      int n = A.length;
      // Переместить верхние n дисков из A в C с помощью B
      dfs(n, A, B, C);
    }

hanota.rs

    /* Переместить один диск */
    fn move_pan(src: &mut Vec<i32>, tar: &mut Vec<i32>) {
        // Снять диск с вершины src
        let pan = src.pop().unwrap();
        // Положить диск на вершину tar
        tar.push(pan);
    }

    /* Решить задачу Ханойской башни f(i) */
    fn dfs(i: i32, src: &mut Vec<i32>, buf: &mut Vec<i32>, tar: &mut Vec<i32>) {
        // Если в src остался только один диск, сразу переместить его в tar
        if i == 1 {
            move_pan(src, tar);
            return;
        }
        // Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar
        dfs(i - 1, src, tar, buf);
        // Подзадача f(1): переместить оставшийся один диск из src в tar
        move_pan(src, tar);
        // Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src
        dfs(i - 1, buf, src, tar);
    }

    /* Решить задачу Ханойской башни */
    fn solve_hanota(A: &mut Vec<i32>, B: &mut Vec<i32>, C: &mut Vec<i32>) {
        let n = A.len() as i32;
        // Переместить верхние n дисков из A в C с помощью B
        dfs(n, A, B, C);
    }

hanota.c

    /* Переместить один диск */
    void move(int *src, int *srcSize, int *tar, int *tarSize) {
        // Снять диск с вершины src
        int pan = src[*srcSize - 1];
        src[*srcSize - 1] = 0;
        (*srcSize)--;
        // Положить диск на вершину tar
        tar[*tarSize] = pan;
        (*tarSize)++;
    }

    /* Решить задачу Ханойской башни f(i) */
    void dfs(int i, int *src, int *srcSize, int *buf, int *bufSize, int *tar, int *tarSize) {
        // Если в src остался только один диск, сразу переместить его в tar
        if (i == 1) {
            move(src, srcSize, tar, tarSize);
            return;
        }
        // Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar
        dfs(i - 1, src, srcSize, tar, tarSize, buf, bufSize);
        // Подзадача f(1): переместить оставшийся один диск из src в tar
        move(src, srcSize, tar, tarSize);
        // Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src
        dfs(i - 1, buf, bufSize, src, srcSize, tar, tarSize);
    }

    /* Решить задачу Ханойской башни */
    void solveHanota(int *A, int *ASize, int *B, int *BSize, int *C, int *CSize) {
        // Переместить верхние n дисков из A в C с помощью B
        dfs(*ASize, A, ASize, B, BSize, C, CSize);
    }

hanota.kt

    /* Переместить один диск */
    fun move(src: MutableList<Int>, tar: MutableList<Int>) {
        // Снять диск с вершины src
        val pan = src.removeAt(src.size - 1)
        // Положить диск на вершину tar
        tar.add(pan)
    }

    /* Решить задачу Ханойской башни f(i) */
    fun dfs(i: Int, src: MutableList<Int>, buf: MutableList<Int>, tar: MutableList<Int>) {
        // Если в src остался только один диск, сразу переместить его в tar
        if (i == 1) {
            move(src, tar)
            return
        }
        // Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar
        dfs(i - 1, src, tar, buf)
        // Подзадача f(1): переместить оставшийся один диск из src в tar
        move(src, tar)
        // Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src
        dfs(i - 1, buf, src, tar)
    }

    /* Решить задачу Ханойской башни */
    fun solveHanota(A: MutableList<Int>, B: MutableList<Int>, C: MutableList<Int>) {
        val n = A.size
        // Переместить верхние n дисков из A в C с помощью B
        dfs(n, A, B, C)
    }

hanota.rb

    ### Переместить один диск ###
    def move(src, tar)
      # Снять диск с вершины src
      pan = src.pop
      # Положить диск на вершину tar
      tar << pan
    end

    ### Решить задачу Ханойской башни f(i) ###
    def dfs(i, src, buf, tar)
      # Если в src остался только один диск, сразу переместить его в tar
      if i == 1
        move(src, tar)
        return
      end

      # Подзадача f(i-1): переместить верхние i-1 дисков из src в buf с помощью tar
      dfs(i - 1, src, tar, buf)
      # Подзадача f(1): переместить оставшийся один диск из src в tar
      move(src, tar)
      # Подзадача f(i-1): переместить верхние i-1 дисков из buf в tar с помощью src
      dfs(i - 1, buf, src, tar)
    end

    ### Решить задачу Ханойской башни ###
    def solve_hanota(_A, _B, _C)
      n = _A.length
      # Переместить верхние n дисков из A в C с помощью B
      dfs(n, _A, _B, _C)
    end

Визуализация кода

Во весь экран >

Как показано на рисунке 12-15, задача о Ханойской башне формирует дерево рекурсии высоты \(n\) , в котором каждый узел представляет подзадачу и соответствует одному открытому вызову `dfs()`. Поэтому временная сложность равна \(O(2^n)\) , а пространственная сложность равна \(O(n)\) .

Рисунок 12-15 Дерево рекурсии задачи о Ханойской башне

Quote

Задача о Ханойской башне происходит из древней легенды. В одном из храмов древней Индии монахи имели три высоких алмазных стержня и \(64\) золотых диска разного размера. Монахи непрерывно перекладывали диски и верили, что в тот момент, когда последний диск будет правильно перенесен, мир подойдет к концу.

Однако даже если бы монахи перемещали по одному диску в секунду, им понадобилось бы примерно \(2^{64} \approx 1.84×10^{19}\) секунд, то есть около \(585\) миллиардов лет, что намного превышает текущую оценку возраста Вселенной. Поэтому, если легенда и верна, нам, вероятно, пока не о чем беспокоиться.

##### Оставляйте свои идеи, вопросы и предложения в комментариях