Проблемот на Ханојски кули (Tower of Hanoi) е позната математичка игра.
Се состои од три стапчиња, и број на дискови со различна големина кои можат да се стават како прстен на било кое од стапчињата. Играта започнува со тоа што сите дискови се наоѓаат на првото стапче во растечки редослед од горе кон доле (најмалиот диск се наоѓа горе). Целта на играта е да се преместат сите дискови на друго стапче, но да не се прекршуваат правилата:
Во еден потег може да биде поместен само еден диск.
Секој потег се состои од земање на еден диск кој се наоѓа на врв на некое стапче и негово преместување најгоре врз другите дискови на некое друго стапче.
Не може еден диск да се постави врз друг помал диск.
Интересна игра со навистина едноставни правила. Најголем дел од вас ја сретнале загаткава како пример за рекурзија во основните курсеви за програмирање.
Но да бидам искрен, тогаш не сфатив кој е принципот на решавање, но после една година седнав малку подлабоко да ја проучам играва.
Рекурзивно многу е кратко решението, иако изгледа комплицирано на прв поглед.
#include<iostream>
using namespace std;
void hanoi(int N, char from, char to, char other) {
if (N == 0) return;
// we move N-1 disks from "from" to "other"
hanoi(N-1, from, other, to);
// we move the biggest disk from "from" to "to"
cout<<"I moved "<<N<<" from "<<from<<" "<<to<<"\n";
// we move N-1 disks from "other" to "to"
hanoi(N-1, other, to, from);
}
int main() {
int i,j,k;
hanoi(4, 'A', 'C', 'B');
cin>>i;
return 0;
}
Еве го решението во C++. Како што можеме да забележиме, и без да ја сфатиме логиката гледаме дека е едноставна рекурзија која има почетен услов и рекурзивно двапати се повикува самата функција hanoi. Меѓувреме се печати нешто на екран.
Да го проучиме подлабоко проблемот.
Да ги дефинираме параметрите на функцијата и потоа преку опис на параметрите на функцијата да ја дефинираме почетната состојба.
void hanoi(int N, char from, char to, char other);
Првиот аргумент N претставува број на дискови кои сакаме да ги префлиме од дискот кој е обележан како from кон дискот обележан како to. Третиот параметар (иако може да се исфрли) го претставува третиот диск кој индиректно ќе биде искористен при поместувањето.
Значи ако функцијата hanoi ни го решава соодветниот генерален проблем на Ханојските кули, ние со повикување на оваа функција со параметри hanoi(N, 'A', 'C', 'B') го решаваме нашиот конкретен проблем, пренесување на N дискови од дискот обележан како 'A' кон дискот обележан како 'C'.
Сега да ја разгледаме "маѓијата" внатре во функцијата.
Клучната чекор кој го правиме е делењето на еден проблем на потпроблеми од ист тип.
Значи треба некако соодветниот проблем префрлање на N дискови од дискот from кон дискот to да го поедноставиме.
Ако сакаме да префлиме N дискови од дискот from, тогаш знаеме дека тие N дискови се наоѓаат најгоре на стапчето и се наредени по растечки редослед од горе кон доле. Притоа ако најгорниот диск го обележиме со 1, и како одиме надоле давајќи повисоки индекси, дискот обележан како N ќе биде најголем во оваа група од N дискови.
Кога добро ќе се сфати ова идеме на следна фаза.
Префрламе N дискови од A кон C така што прво префламе N-1 дискови од A кон B, потоа дискот кој што ќе остане најгоре на A го префрламе на C, потоа ги префрлуваме (N-1) -те дискови од B кон C.
Да повториме уште еднаш, овојпат наместо A ставаме from, наместо C ставаме to, наместо B ставаме other.
Префрламе N дискови од from кон to така што прво префламе N-1 дискови од from кон other, потоа дискот кој што ќе остане најгоре на from го префрламе на to, потоа ги префрлуваме (N-1) -те дискови од other кон to.
Имаме и почетен услов со кој прекинува рекурзијата, кога бројот на дискови кои треба да се префрлат е нула.
