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

След като вече минахме през урока за рекурсия, значи сме готови да разгледаме друга задача, в която неколкократното използване на рекурсия наистина ще ни помогне. Това е задачата Ханойски кули. Дадени са три колони и $n$‍ диска, като всеки диск е с различен размер. Да наречем дисковете A, B и C и да номерираме дисковете – от 1 за най-малкия до $n$‍ за най-големия. В началото всичките $n$‍ дискове са на колона A, подредени в низходящ ред от най-долния към най-горния, така че диск $n$‍ е най-отдолу, а диск 1 е най-отгоре. Ето как изглеждат Ханойските кули с $n=5$‍ диска:

Целта е да преместим всичките $n$‍ диска от колона A до колона B:

Звучи лесно, нали? Не е толкова просто, защото трябва да спазваш две правила:

Може би си мислиш, че тази задача не е толкова важна. Напротив! Според легендата някъде в Азия (Тибет, Виетнам, Индия – избери си легенда от интернет), монасите са решавали тази задача с 64 диска и – поне така се твърди – монасите вярвали, че след като преместят по правилата всички дискове от колона А на колона В, светът ще свърши. Ако монасите са прави, дали трябва да се паникьосваме?

Първо да видим как да решим задачата с рекурсия. Ще започнем с нещо лесно: един диск, което значи $n=1$‍. Случаят $n=1$‍ ще бъде базовият случай. Винаги можеш да преместиш диск 1 от колона А на колона В, защото знаеш, че всеки диск под него трябва да е по-голям. Няма нищо специално при колоните А и В. Можеш да преместиш диск 1 от колона В на колона С, ако искаш, или от колона С на колона А – от всяка колона на всяка друга колона. Решаването на Ханойските кули с един диск е лесно и изисква преместването само на един диск.

Ами с два диска? Как решаваш задачата, когато $n=2$‍? Можеш да го направиш с три стъпки. Ето как изглежда в началото:

Първо местиш диск 1 от колона А на колона С:

Забележи, че използваме колона С като резервна колона, на която да поставим диск 1, за да можем да вземем диск 2. Сега диск 2 – най-долният диск – е открит и можем да го преместим на колона В:

Накрая местим диск 1 от колона С на колона В:

Това решение има три стъпки и отново няма нищо специално за преместването на два диска от колона А на колона В. Можеш да ги преместиш от колона В на колона С, като използваш А за резервна колона: преместваш диск 1 от колона В на колона А, след това преместваш диск 2 от колона В на колона С и завършваш, като преместиш диск 1 от колона А на колона С. Съгласяваш ли се, че можеш да преместиш дисковете 1 и 2 от всяка колона на всяка друга колона с три стъпки? (Кажи "да.")

Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.