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

от Уикипедия, свободната енциклопедия
Направо към навигацията Направо към търсенето
Начална постановка на играта Ханойска Кула
Анимирано решение с 4 диска

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

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

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

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

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

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

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

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

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

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

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

T1 = 2T0+1 = 1

T2 = 2T1+1 = 3

T3 = 2T2+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);
    }
}

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

n01234567
Tn0137153163127

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

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

  • T0=20-1=0, следователно основният случай е верен.
  • Нека n > 0. Да предположим, че Tk = 2k-1 за 0≤k≤n-1. Тогава Tn = 2Tn-1+1 = 2(2n-1-1)+1 (според индукционната хипотеза) От където Tn = 2n-1

Така за играта Ханойска кула получаваме T8 = 28-1 = 255 хода, а за Кулата на Брахма – T64 = 264-1 ≈ 1019,3 хода. Ако предположим, че можем да извършваме по един ход на секунда, то за решаването на Ханойска кула ще са ни нужни 4 мин и 15 секунди, докато за кулата на Брахма ще са необходими около 585 милиарда години от където и идва легендата за края на света.

Приложения[редактиране | редактиране на кода]

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

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

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

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

Вижте също[редактиране | редактиране на кода]

Външни препратки[редактиране | редактиране на кода]