Ханойска кула

Ханойската кула (от името на град Ханой) е математическа игра, измислена от френския математик Едуар Лука през 1883 година.

Играта представлява осем диска, различни по размер един от друг, и три стълба. В началото дисковете са подредени на левия стълб, като най-големият е най-отдолу, а най-малкият – отгоре. Целта е кулата да бъде преместена на десния стълб. Може да се мести само по един диск на ход и не може по-голям диск да бъде поставен върху по-малък. Всеки ход е съставен от взимането на горния диск от даден стълб и в поставянето му най-отгоре на друг стълб.

Съществува вариант на играта с 64 диска, наречен Кулата на Брахма. Легендата разказва, че когато монасите от Брахма приключат играта ще настъпи краят на света.

Алгоритъм за рекурсивно решение с най-малко ходове

Ще обобщим решението, което търсим за n диска:

това позволява да изследваме случаите в които n е малко
намирайки решение за n диска, можем лесно да изчислим n=8 и n=64

Нека T_n бъде броят ходове, нужни за решаване на задачата. Един от начините за решаване на задачата с n диска е:

преместваме (n-1) диска от левия към средния стълб: T_n-1 хода
преместваме най-големия диск от левия на десния стълб: 1 ход
преместваме дисковете от средния стълб на десния: T_n-1 хода

Следователно T_n = 2T_n-1+1, ∀n>1

От където получаваме:

$\left\{{\begin{array}{ll}T_{0}=0\\T_{n}=2T_{n-1}+1,\forall n\geq 1\end{array}}\right.$

Сега можем да проверим стойностите на T_n при малки стойности на n:

T₁ = 2T₀+1 = 1

T₂ = 2T₁+1 = 3

T₃ = 2T₂+1 = 7

Това решение може да бъде представено на различни програмни езици като например CAML:

 let rec T n=
    if n=0
        then 0
    else 1+(2*(T(n-1)));;

или Python:

 def T(n):
    if(n==0):
       return 0
    else
       return 1+2*T(n-1)

или C:

int conf[HEIGHT]; /* Елементът conf[d] връща текущата позиция на диск d. */

void move(int d, int t) {
    /* премества диск d на стълба t */
    conf[d] = t;
}

void hanoi(int h, int t) {
    if (h > 0) {
        int f = conf[h-1];
        if (f != t) {
            int r = 3 – f – t;
            hanoi(h-1, r);
            move(h-1, t);
        }
        hanoi(h-1, t);
    }
}

Въпреки че този рекурсивен алгоритъм позволява да се изчисли T_n, той не е ефикасен при големи стойности на n. Затова решението е да намерим затворена форма на рекурсията. Нека погледнем стойностите на T_n при n=0...7:

n	0	1	2	3	4	5	6	7
T_n	0	1	3	7	15	31	63	127

Забелязваме, че T_n = 2ⁿ-1, ∀n≥0.

Това свойство може да бъде доказано, чрез математическа индукция:

T₀=2⁰-1=0, следователно основният случай е верен.
Нека n > 0. Да предположим, че T_k = 2^k-1 за 0≤k≤n-1. Тогава T_n = 2T_n-1+1 = 2(2^n-1-1)+1 (според индукционната хипотеза) От където T_n = 2ⁿ-1

Така за играта Ханойска кула получаваме T₈ = 2⁸-1 = 255 хода, а за Кулата на Брахма – T₆₄ = 2⁶⁴-1 ≈ 10^19,3 хода. Ако предположим, че можем да извършваме по един ход на секунда, то за решаването на Ханойска кула ще са ни нужни 4 мин и 15 секунди, докато за кулата на Брахма ще са необходими около 585 милиарда години от където и идва легендата за края на света.

Приложения

Играта на Ханойска кула намира различни приложения в ежедневието.

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

На места, където се правят резервни копия на данни върху магнитни ленти Ханойската кула се използва в схемата за смяна на ролките.

В университетите Ханойската кула се използва за демонстриране на рекурсивността пред студентите по математика и информатика.

Вижте също

Рекурсия

Външни препратки

Портал „Информатика“