1.3.2. Задача “Ханойские башни”

Эта задача формулируется следующим образом. Имеется три стерж-ня, на одном из которых (назовём его занятым) находятся диски разных диаметров, расположенные на стержне в порядке убывания диаметров снизу вверх; второй стержень назовём свободным, а третий - вспомога-тельным (рис 1.17). Требуется, производя одиночные перемещения дисков, переместить всю “стопку” дисков с занятого стержня на свобод-ный, используя вспомогательный стержень; при этом на любом шаге диски должны быть расположены на каждом стержне в порядке убывания их диаметров.

Рис. 1.17. Ханойские башни

В табл. 1.5 приведен результат решения задачи для случая четырех дисков. Здесь А - занятый в начальный момент (нулевой шаг) стержень, В - свободный, а С - вспомогательный стержень. Цифрами обозначен “номер” диска, причём большему номеру соответствует больший диаметр. Отметим, что в середине процесса решения в качестве вспомогательного выступает то стержень А, то стержень С.

Видно, что процесс перемещения стопки дисков можно разбить на фазы (1-я фаза - шаги 1-8; 2-я фаза - шаги 9-12; 3-я фаза - шаги 13 и 14; 4-я фаза - шаг 15). К началу каждой фазы на вспомогательном (занятом) стержне собирается стопка дисков (в табл. 1.5 номера этих дисков подчёркнуты), затем в течение данной фазы самый нижний диск стопки перемещается на свободный стержень

Таблица 1.5.

Шаг	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
А	4-1	4-2	4,3	4,3	4	4,1	4,1	4			2	2,1	2,1	2		
В			2	2,1	2,1	2			4	4,1	4,1	4	4,3	4,3	4-2	4-1
С		1	1		3	3	3,2	3-1	3-1	3,2	3	3		1	1	

Анализ перемещений дисков позволяет выявить определённые зако-номерности, составить словесное описание алгоритма перемещений для общего случая (количество дисков произвольно), а затем перейти к разра-ботке схемы алгоритма.

Чтобы переместить самый нижний диск на стержень В, необходимо 2^n-1 перемещений. Общее число перемещений равно 2ⁿ-1.

Эти утверждения можно доказать по индукции.

Заключение

Любой вычислительный процесс может быть представлен компо-зицией следующих его фрагментов: линейный, ветвящийся, циклический.

Для организации разветвлений и циклов могут быть использованы различные операторы; выбор того или иного оператора в конкретном случае остаётся за программистом.

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

При организации циклов особенно важны два момента: правиль-ное построение начала цикла и его конца. Важно также обеспечить стыковку цикла с остальной частью алгоритма или циклов друг с другом при их вложенности.

СА может быть представлена с разной степенью подробности. Так, предопределённый процесс, например блок ввода/вывода, может вклю-чать в себя несколько циклов; визуально фрагмент СА, включающий в себя этот блок, будет выглядеть линейным. В действительности линей-ными могут быть только очень простые алгоритмы или их некоторые фрагменты.

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

Необходимо повышенное внимание уделять особым случаям, которые встречаются в данных либо в формулах (например, в алгоритме нахождения минимального числа множества - это случай, когда входное множество содержит один элемент либо оно пустое; при некоторых вычислениях возникает необходимость деления на 0 и т.п.).

Контрольные вопросы. Упражнения

1. Какие соединения вершин СА являются допустимыми? Предло-жите несколько вариантов произвольных СА, содержащих 8...10 вершин разных типов.

2. Вы сможете доказать, что каждый из рассмотренных в данной главе вычислительных процессов является алгоритмом?

3. Как надо скорректировать СА решения квадратного уравнения (рис 1.4), чтобы при преобразовании уравнения общего вида (1.7) к приведённому учесть случай а = 0 (при этом вычисление p и q связано с делением на 0, что недопустимо)?

4. Как изменится СА для процедуры MIN_A (пример 1.7), которая встроена в некий вычислительный процесс (модуль), если при обращении к этой процедуре возможны случаи, когда сформированный в основном процессе массив А содержит всего один элемент либо пуст?

5. Каким требованиям должны удовлетворять размерности матриц A, B и C, чтобы корректно выполнить матричную операцию D = A + BхC? Сколько циклов понадобится для вычисления матрицы D?

6. Почему некоммутативна в общем случае операция перемножения двух квадратных матриц одинаковой размерности? В каком частном случае коммутативность имеет место?

7. Составьте фрагменты СА для формул (1.16) ... (1.19) и сравните попарно фрагменты для формул (1.16), (1.18) и (1.17), (1.19). В каком случае вычисления рациональнее и почему?

8. В чём отличие вариантов с использованием от вариантов без использования оператора case ... of? Рассмотрите эти варианты для примера 1.5.

9. Чем отличаются операторы for, while…do, repeat…until?

10. Постройте схему алгоритма выбора, реализующую логическую функцию &, где B1, B2, B3 - некотоpые условия (булевы переменные).

Указание. Ввести промежуточную переменную &.

11. Постройте СА, реализующую предикат p(x)ax<b.

Указание. Учесть, что предикат включает в себя 2 условия.

12. Составьте СА определения максимального элемента множества, содержащего 12 чисел. Какое количество сравнений и перестановок эле-ментов понадобится в случае, если массив отсортирован в порядке возра-стания элементов? Выведите формулу для определения количества срав-нений и перестановок в случае произвольного количества элементов.

13. Составьте словесное описание алгоритма перемножения двух матриц.

14. Для функции y=F(x), представленной разложением в ряд (1.20), постройте схему алгоритма, позволяющего вычислить значение y в точках разбиения с погрешностью  при равномерном разбиении области опре-деления функции [a,b] на m частей.

15. Составьте СА поиска пути в лабиринте.

16. Докажите, что в задаче “Ханойские башни” для перемещения n-го (самого нижнего) диска на свободный стержень необходимо 2^n-1 одиночных перемещений. Докажите также, что общее число перемещений на свобод-ный диск определяется числом 2ⁿ-1.

51