Задача о Ханойских башнях

С ГРАФИЧЕСКИМ ИНТЕРФЕЙСОМ (GUI)

формулировка

Модифицированная задача о Ханойских башнях:

Существует 8 шпинделей, пронумерованых от 8 до 1 слева направо. На каждом шпинделе надеты диски, в количестве, равном соответствующей цифре из ID студента. Все диски имеют разные диаметры. Диаметр диска равен M * 10 + N, где М – номер шпинделя, на котором надет диск, а N – это номер диска на шпинделе, считая сверху вниз.

1.     Необходимо визуально изобразить предложенную задачу. Диски на шпинделях сделать случайных цветов. На каждом диске отображать цифру, равную его диаметру. Диаметр диска также показывать его фактическим размером в пикселях.

2.     Необходимо вычислить, за какое минимальное количество итераций переместятся все диски на шпиндель номер 1 по следующим правилам:

а) За одну итерацию можно переместить не более одного диска

б) Диски можно класть только с большего на меньший

в) Со шпинделя номер 8 можно перекладывать диски только на шпиндели 7 и 6

г) Со шпинделя номер 1 можно перекладывать диски только на шпиндели номер 2 и 3

д) Со шпинделей от 2 по 7 можно перекладывать диски только на два соседних шпинделя.

     3. Необходимо отобразить начальное и конечное расположение дисков на шпинделях, для этого под изображением Ханойских башен предусмотреть две кнопки «Начало» и «Окончание». При нажатии на нее, в надписи под схемой должен выводится текст «Итерация ХХ», где ХХ – номер итерации (либо 0, либо номер итоговой итерации, соответственно).

     4. Необходимо графически отобразить четыре промежуточные итерации перекладывания дисков. Для этого:

            а) общее количество итераций признаётся равным 100%, 

            б) ID студента делится на 4 двузначных числа, каждое из которых обозначает итерацию, соответствующую этому проценту выполнения общей задачи.

           в) Под изображением Ханойских башень предусмотреть четыре поля для ввода цифр с процентами выполнения. По-умолчанию добавить туда числа из п. б)

          г) Под каждым полем для ввода предусмотреть кнопку, при нажатии на которую схема Ханойской башни отображает расположение дисков на соответствующей итерации. Также в надписи под схемой должен выводится текст «Итерация ХХ», где ХХ – номер итерации

  5. Дать возможность пользователю изменять проценты в полях для ввода цифр, и по нажатию соответствующей кнопки просматривать расположение дисков на данной итерации.

Методические указания

Так как задача алгоритмически достаточно проста, то основная часть работы над задачей студента сводится к правильной визуализации полученных результатов, а также оптимальному поиску промежуточных результатов. Схема ханойских башен должна выглядеть примерно таким образом:

(В данном примере расположение дисков соответствует ID студента 70256421)

Так как размер диска должен соответствовать его номеру на шпинделе и номеру самого шпинделя, умноженного на 10, то как нетрудно догадаться, максимальный диаметр диска может быть 89. Поэтому для правильной визуализации без наложения дисков рекомеднуется выдерживать расстояние между шпинделями примерно в 100-120 пикселей (для окна формата 1280х1024).

Поскольку диски близких размеров будут отличаться всего на один пиксель, то для контроля на каждом диске необходимо проставить его диамер в виде цифры. Так как в конце задачи все диски будут находиться на первом шпинделе, а общее количество дисков теоретически может быть равно 72, то рекомендуется сделать толщину одного диска примерно равной 10-12 пикселям, для указанного окна.

Остальные элементы управления под схемой Ханойской башни рекомендуется выстраивать в следующем порядке:

 На данном рисунке также видно, как следует разбивать ID студента для выведения промежуточных итогов.  При нажатии на кнопки, нужно показать итерации, соответствующие 70%, 25%, 64% и 21% выполнения задачи.

Выходные данные

На цифровом дисплее должно отображаться окно с начальным расположением дисков на шпинделях Ханойских башень. Шпиндели пронумерованы, на дисках также обозначены соответствующие диаметры. Под ней отображается шесть кнопок и четыре поля для ввода цифр. В нижней части экрана демонстрируется надпись «Итерация 0»

При нажатии на любую из шести имеющихся кнопок, либо при заполнении поля ввода другими данными и нажатии на кнопку, схема ханойских башень меняется, для отображения соответствующей итерации. Надпись в нижней части экрана также меняется.