Обектно-ориентирано програмиране 2004/05 - упражнения и практикум

Дадени са три метални пръта, забити вертикално на хоризонтална дъска. Разполагате с пръстени с различен диаметър 1,2,3,...n. В началото всички пръстени са поставени на най-левия прът както е показано по-долу:

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

1.  Реализирайте шаблона за стек от учебника. Напишете голямата четворка, и функциите pop, push, top и empty.
2. Напишете клас, който описва една Ханойска кула, която има за член данни стек от цели числа и един символ за име (няма нужда от цял низ). Добавете следните член-функции:
   
   • конструктор за създаване на Ханойска кула по име и естествено число n, като на Ханойската кула се поставят всички пръстени с диаметър от 1 до n във възходяш ред.
   • член-функция за изпълняване на описаната по-горе операция, който връща стойност bool дали операцията отговаря на горните правила
     
   • константна член-функция за извеждане на Ханойска кула
   • константна член-функция за броя на пръстените върху Ханойската кула
3. Решете задачата за Ханойските кули с търсене с връщане назад (backtracking). За целта дефинирайте рекурсивна функция findSolution с параметри три Ханойски кули, която връща bool - дали опитът за решаване на задачата е успешен. ВНИМАНИЕ: функцията трябва да приема параметри-стойности, а не псевдоними, за да е възможно връщането назад! Упътване: от всяка ситуация има най-много три смислени хода. Задачата е решена, ако след изпълняване на операция преместване на пръстен сме получили прът с n пръстена.
4. Решете задачата за Ханойските кули с рекурсия като сведете задачата за преместване на n пръстена до задача за преместване на n-1 пръстена. Случаят на един пръстен се решава с просто изпълнение на дадената операция. Тук функцията вече може да приема като параметри псевдоними, понеже нямаме връщане назад.