Основы объектно-ориентированного проектирования

         

У6.3 Стеки Ханоя


(Это упражнение пришло из примера Филиппа Дрикса.)

Рассмотрим отложенный класс STACK с процедурой put для вталкивания элемента на вершину с предусловием, включающим булеву функцию full (которая также может быть названа extendible; когда вы ознакомитесь с упражнением, то заметите, что выбор имени может влиять на возможные решения).

Задача о Ханойских башнях, известная по многим учебникам как пример рекурсивной процедуры, идет от работы Эдварда Лукаса, Париж, 1883 г.

Рассмотрим теперь известную задачу о Ханойских башнях, где нужно перенести пирамиду (башню), составленную из отдельных дисков разного размера, с одного стержня на другой, используя третий, соблюдая правило: диск может быть переложен только на диск большего размера.

Можно ли определить класс HANOI_STACK, представляющий такие пирамиды, как наследника класса STACK? Если да, каким должен быть этот класс? Если нет, может ли HANOI_STACK как-то использовать STACK? Напишите класс полностью для различных возможных решений, обсудите все "за и против" каждого решения. Установите, какое из них предпочтительнее и объясните ваш выбор.



Содержание раздела