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

1. Рекурсивное решение.
   Рекурсивный подход к решению проблемы Ханойских башен элегантен и интуитивно понятен. Он следует принципу разбиения более крупной проблемы на более мелкие подзадачи. Вот реализация Python:

def hanoi_recursive(n, source, target, auxiliary):
    if n > 0:
        # Move n-1 disks from source to auxiliary peg
        hanoi_recursive(n - 1, source, auxiliary, target)

        # Move the nth disk from source to target peg
        print(f"Move disk {n} from {source} to {target}")

        # Move the n-1 disks from auxiliary peg to target peg
        hanoi_recursive(n - 1, auxiliary, target, source)
# Example usage
hanoi_recursive(3, 'A', 'C', 'B')

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

class StackItem:
    def __init__(self, n, source, target, auxiliary):
        self.n = n
        self.source = source
        self.target = target
        self.auxiliary = auxiliary
def hanoi_iterative(n, source, target, auxiliary):
    stack = []
    stack.append(StackItem(n, source, target, auxiliary))

    while len(stack) > 0:
        item = stack.pop()
        if item.n > 0:
            # Push the subproblems onto the stack
            stack.append(StackItem(item.n - 1, item.auxiliary, item.target, item.source))
            stack.append(StackItem(1, item.source, item.target, item.auxiliary))
            stack.append(StackItem(item.n - 1, item.source, item.auxiliary, item.target))
        else:
            # Move disk from source to target peg
            print(f"Move disk {item.n} from {item.source} to {item.target}")
# Example usage
hanoi_iterative(3, 'A', 'C', 'B')

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

Не забудьте адаптировать решение к конкретному языку программирования, который вы используете, и соответствующим образом скорректировать код. Задача «Ханойские башни» — отличное упражнение для развития алгоритмического мышления и навыков решения задач.