Ханойската кула (от името на град Ханой) е математическа игра, измислена от френския математик Едуар Лука през 1883 година.
Правила на играта Играта представлява осем диска, различни по размер един от друг, и три стълба. В началото дисковете са подредени на левия стълб, като най-големият е най-отдолу, а най-малкият – отгоре. Целта е кулата да бъде преместена на десния стълб. Може да се мести само по един диск на ход и не може по-голям диск да бъде поставен върху по-малък. Всеки ход е съставен от взимането на горния диск от даден стълб и в поставянето му най-отгоре на друг стълб.
Кула на Брахма Легенда, измислена от професор Люка, разказва, че във Великия храм в град Бенарес , под катедралата, отбелязваща Центъра на света, има бронзов диск, върху който са закрепени три диамантени пръта, всеки висок един лакът и дебел колкото пчела. Много отдавна, в самото начало на времето, монасите от този манастир обидили бог Брахма. Разгневен, той издигнал три високи пръта и поставил 64 диска, изработени от чисто злато, върху един от тях. Всеки по-малък диск лежи върху по-голям. Веднага щом всичките 64 диска бъдат прехвърлени от пръта, на който Брахма ги е поставил при създаването на света, към друг прът, кулата и храмът ще се превърнат в прах и светът ще загине под гърмежите на гръмотевиците.
Броят на ходовете в зависимост от броя на пръстените се изчислява по формулата: . Броят на движенията на диска, които монасите трябва да направят, е 18 446 744 073 709 551 615. Ако монасите работеха денем и нощем, правейки по едно движение на диска всяка секунда, работата им щеше да продължи почти 585 милиарда години.
Алгоритъм за рекурсивно решение с най-малко ходове Ще обобщим решението, което търсим за 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 милиарда години от където и идва легендата за края на света.
Приложения Играта на Ханойска кула намира различни приложения в ежедневието. Психолозите я използват в изследванията си върху човешките капацитети за решаване на проблеми, а невропсихолозите – като тест за диагностициране на амнезия.
На места, където се правят резервни копия на данни върху магнитни ленти Ханойската кула се използва в схемата за смяна на ролките. В университетите Ханойската кула се използва за демонстриране на рекурсивността пред студентите по математика и информатика.
Вижте също Рекурсия
Външни препратки Ханойска кула в психоанализата Игра на Ханойска кула
Категория:Алгоритми Категория:Математика Категория:Ханой