Алгоритъм на Ханойската кула: Python, C++ Code

⚡ Умно обобщение

Алгоритъмът „Кулата на Ханой“ е класически рекурсивен пъзел, който мести купчина дискове между три колчета, без да поставя по-голям диск върху по-малък, илюстрирайки ясно принципа „разделяй и владей“.

🗼 Подготовка на пъзела: Три колчета и n диска, подредени с намаляващ размер върху изходното колче, чакащи да бъдат преместени към целевото колче чрез помощно колче.
📜 Правила: Само един диск се движи в даден момент, само горният диск на който и да е колче може да се движи и по-голям диск не може да лежи върху по-малък диск.
🔁 Рекурсивна идея: Преместете n-1 диска към помощния колче, преместете най-големия диск към целевия колче, след което преместете n-1 диска от помощния колче към целевия.
️ Времева сложност: Решаването на n диска изисква 2^n – 1 хода, което дава експоненциална времева сложност O(2^n), която нараства много бързо с увеличаване на n.
🧠 Космическа сложност: Рекурсионният стек побира до n кадъра едновременно, така че пространствената сложност на рекурсивното решение е O(n).
🛠️ Приложения: Преподаване на рекурсия, схеми за ротация на резервни копия, преместване на данни на базата на стек, секвениране на роботи и разбиране на дизайна на алгоритми „разделяй и владей“.

Прочетете повече

Какво представлява кулата на Ханой?

Ханойската кула е математически пъзел, състоящ се от три пръчки и купчина дискове с намаляващ размер, поставени един върху друг. Известна е още като Кулата на Брахма или Кулата на Лукас, тъй като френският математик Едуар Лукас я въвежда през 1883 г. Пъзелът е базиран на легенди за преместване на златни дискове между три пръчки.

Този пъзел има три пръчки и променлив брой подредени дискове. Пръчките са подредени като циклични кули, така че по-големите дискове са подредени отдолу, а по-малките дискове са подредени отгоре.

Първоначално ни са дадени три колчета или пръчки. Върху едното от тях (колче А в примера) са подредени всички дискове. Целта е да се премести целият куп от едното пръчче (А) на другото (В), като се спазват няколко специфични правила.

Ето първоначалната настройка на пъзела:

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

И това е крайната цел:

Правила на Ханойската кула

Ето основните правила за Кулата на Ханой:

В началното състояние на пъзела всички дискове са подредени върху прът номер едно.
В крайното състояние всички дискове от прът едно са подредени върху прът две или прът три.
Само един диск може да се движи от един прът на друг във всеки един момент.
Само най-горният диск на пръта може да бъде преместен.
Диск не може да се постави върху по-малък диск.

Оригиналната легенда е за преместването на 64 диска. Жреците са можели да местят по един диск наведнъж, съгласно правилата. Според легендата е имало пророчество, че светът ще свърши, ако успеят да завършат действието. В раздела за времевата сложност ще покажем, че Кулата на Ханой, поставена върху n диска, изисква 2^n – 1 хода.

Така че, ако на жреците им е била необходима 1 секунда, за да преместят един диск, общото време за решаване на пъзела би било 2^64 – 1 секунди, или приблизително 584 942 417 356 години, 26 дни, 7 часа и 15 секунди.

Алгоритъм за Ханойската кула

Най-разпространеният начин за решаване на Кулата на Ханой е рекурсивен алгоритъм. Първо, избираме два пръта като източник и дестинация; резервният кол действа като спомагателен или помощен елемент.

Ето стъпките за решаване на пъзела на Ханойската кула:

Преместете горните n-1 дискове от изходното колче към помощното колче.
Преместете n-тия диск от изходния колче към целевия колче.
Преместете останалите n-1 диска от помощния колче към целевия колче.

Забележка: Ако имаме един диск, можем да го преместим директно от източника към местоназначението.

Как да решите пъзела на Ханойската кула

Нека илюстрираме алгоритъма за три диска. Да разгледаме колче A като източник, колче B като помощник и колче C като дестинация.

Стъпка 1) Първоначално всички дискове са подредени върху колче А.

На този етап: Източник = Колче A, Дестинация = Колче C, Помощник = Колче B.

Сега трябва да преместим горните n-1 диска от източника към помощника.

Забележка: Въпреки че можем да местим само по един диск наведнъж, тази стъпка свежда проблема ни с 3 диска до проблем с 2 диска, който се обработва чрез рекурсивно извикване.

Стъпка 2) Когато правим рекурсивно извикване от peg A с peg B като дестинация, използваме peg C като помощник.

Обърнете внимание, че се връщаме на първи етап за същата задача с Кулата на Ханой, но сега за два диска. Преместваме n-1 (тоест един) диск от източника към помощника, което премества най-малкия диск от колче A към колче C.

На този етап: Източник = колче A, Дестинация = колче B, Помощник = колче C.

Стъпка 3) Според алгоритъма, n-тият (2-ри) диск вече се прехвърля към местоназначението, колче B.

На този етап: Източник = колче A, Дестинация = колче B, Помощник = колче C.

Стъпка 4) Сега преместваме n-1 диска (диск едно) от помощния колче C към целевия колче B, следвайки третия етап от алгоритъма.

На този етап: Източник = колче A, Дестинация = колче B, Помощник = колче C.

Стъпка 5) След завършване на рекурсивното извикване, се връщаме към предишната ни настройка от първия етап на алгоритъма.

Стъпка 6) Във втория етап преместваме диск 3 от изходния колче A към целевия колче C.

На този етап: Източник = колче A, Дестинация = колче C, Помощник = колче B.

Стъпка 7) Следващата задача е да преместим останалите дискове от помощния елемент (колче B) към местоназначението (колче C). Този път ще използваме оригиналния източник (колче A) като помощен елемент.

Стъпка 8) Тъй като не можем да преместим два диска едновременно, правим рекурсивно извикване за диск 1. Според нашето алгоритъм, дестинацията в тази стъпка е колче А.

На този етап: Източник = колче B, Дестинация = колче A, Помощник = колче C.

Стъпка 9) Рекурсивното ни извикване е завършено. Сега преместваме диск 2 от източника към местоназначението му.

На този етап: Източник = колче B, Дестинация = колче C, Помощник = колче A.

Стъпка 10) Завършваме, като преместваме останалия n-1 диск (диск 1) от помощния диск към местоназначението.

На този етап: Източник = колче A, Дестинация = колче C, Помощник = колче B.

Прякор Code за Ханойската кула

START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
    IF disk == 1 THEN
        move disk from source to dest
    ELSE
        Tower_Of_Hanoi(disk - 1, source, helper, dest)
        move disk from source to dest
        Tower_Of_Hanoi(disk - 1, helper, dest, source)
    END IF
END Procedure

Програмен код в C++

#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
    if (num == 1) {
        cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
        return;
    }
    tower_of_hanoi(num - 1, source, helper, dest);
    cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
    tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
    int num;
    cin >> num;
    printf("The sequence of moves :\n");
    tower_of_hanoi(num, "I", "III", "II");
    return 0;
}

Изход:

3
The sequence of moves :
Move disk 1 from tower I to tower III
Move disk 2 from tower I to tower II
Move disk 1 from tower III to tower II
Move disk 3 from tower I to tower III
Move disk 1 from tower II to tower I
Move disk 2 from tower II to tower III
Move disk 1 from tower I to tower III

Програмен код в Python

def tower_of_hanoi(n, source, destination, helper):
    if n == 1:
        print("Move disk 1 from peg", source, "to peg", destination)
        return
    tower_of_hanoi(n - 1, source, helper, destination)
    print("Move disk", n, "from peg", source, "to peg", destination)
    tower_of_hanoi(n - 1, helper, destination, source)
# n = number of disks
n = 3
tower_of_hanoi(n, 'A', 'B', 'C')

Изход:

Move disk 1 from peg A to peg B
Move disk 2 from peg A to peg C
Move disk 1 from peg B to peg C
Move disk 3 from peg A to peg B
Move disk 1 from peg C to peg A
Move disk 2 from peg C to peg B
Move disk 1 from peg A to peg B

Сложност на Ханойската кула

Ето е сложността на времето и пространството на Ханойската кула:

1) Времева сложност:

Ако погледнем назад към алгоритъма, правим рекурсивно извикване за (n-1) диска два пъти на извикване. Всяка (n-1) рекурсия се разделя на ((n-1)-1) рекурсии и така нататък, докато стигнем до базовия случай с един диск.

За три диска:

Диск 3 извиква рекурсивната функция за диск 2 два пъти.
Диск 2 извиква рекурсивната функция за диск 1 два пъти.
Диск 1 се движи за постоянно време, което дава времето за решаване на задачата за три диска.

Изразено като рекурентност:

= 2 × (Време за решаване за два диска) + константа време за преместване на диск 3

= 2 × (2 × време за решаване на задачата за един диск + постоянно време за преместване на диск 2) + постоянно време за преместване на диск 3

= (2 × 2) × постоянно време за преместване на диск 1 + 2 × постоянно време за преместване на диск 2 + постоянно време за преместване на диск 3

За n диска това става:

2^п-1 × постоянно време за преместване на диск 1 + 2^п-2 × константно време за преместване на диск 2 + ….

Тази геометрична прогресия се сумира до O(2ⁿ – 1), което се опростява до O(2ⁿ), експоненциална времева сложност.

2) Сложност на пространството:

Пространствената сложност на Кулата на Ханой е O(n). Рекурсията използва стека от извиквания, а максималната дълбочина на стека е равна на n, броят на дисковете. Ето защо пространствената сложност е O(n).

Въпроси и Отговори

Алгоритъмът „Кулата на Ханой“ е рекурсивна процедура, която премества n диска от изходен колче към целеви колче, използвайки едно помощно колче, като никога не поставя по-голям диск върху по-малък.

Минималният брой ходове за n диска е 2^n – 1. Три диска се нуждаят от 7 хода, четири диска се нуждаят от 15, а десет диска се нуждаят от 1,023 хода.

Времевата сложност е O(2^n), защото всеки допълнителен диск удвоява работата. Рекурентната функция T(n) = 2T(n-1) + 1 се решава до 2^n – 1, което е експоненциално.

Пространствената сложност е O(n), защото стекът за рекурсивни извиквания съдържа по един кадър за всеки обработван диск. Максималната дълбочина на рекурсията достига n, така че необходимата спомагателна памет е линейна в зависимост от броя на дисковете.

Да. Итеративното решение използва цикъл с фиксиран модел: при нечетни ходове най-малкият диск се разменя циклично между колчетата, а при четни ходове се прави единственият допустим не-малък ход.

Алгоритъмът обучава рекурсия, моделира схеми за ротация на резервно копие за съхранение, ръководи секвенирането на роботизирана ръка и се появява в невропсихологични тестове, които измерват способността за планиране.

Агентите за обучение с подсилване решават проблема с Кулата на Ханой, като третират всяка конфигурация на диска като състояние и всяко движение като действие. Това е общ бенчмарк за планиране и йерархично обучение на политики.

Да. GitHub Copilot, ChatGPT и Gemini генериране на рекурсивни решения за Кулата на Ханой в Python, C++, и JavaРазработчиците все пак трябва да проверят базовите случаи и реда на аргументите.

Алгоритъм на Ханойската кула: Python, C++ Code

Какво представлява кулата на Ханой?

Правила на Ханойската кула

Алгоритъм за Ханойската кула

Как да решите пъзела на Ханойската кула

Прякор Code за Ханойската кула

Програмен код в C++

Програмен код в Python

Сложност на Ханойската кула

Въпроси и Отговори

Обобщете тази публикация с:

Регистрирайте се за бюлетина

Какво представлява кулата на Ханой?

Правила на Ханойската кула

Алгоритъм за Ханойската кула

Как да решите пъзела на Ханойската кула

СВЪРЗАНИ СТАТИИ

Прякор Code за Ханойската кула

Програмен код в C++

Програмен код в Python

Сложност на Ханойската кула

Въпроси и Отговори

Обобщете тази публикация с:

Регистрирайте се за бюлетина