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

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

Ханойската кула (от името на град Ханой) е математическа игра, измислена от френския математик Едуард Люка през 1883 година. Играта представлява осем диска, различни по размер един от друг, и три стълба. В началото дисковете са подредени на левия стълб, като най-големият е най-отдолу, а най-малкият - отгоре. Целта е кулата да бъде преместена на десния стълб. Може да се мести само по един диск на ход и не може по-голям диск да бъде поставен върху по-малък. Всеки ход е съставен от взимането на горния диск от даден стълб и в поставянето му най-отгоре на друг стълб.

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

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

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

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

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

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

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

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

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

Сега можем да проверим стойностите на 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:

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

Забелязваме, че 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 милиарда години от където и идва легендата за края на света.

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

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

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

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

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

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

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