| Ханойские башни
На доске есть три иглы: 1,
2, 3. На игле 1 размещена башня из n дисков; нижний диск имеет самый
большой диаметр, а диаметр каждого следующего меньше предыдущего.
За один ход с любой иглы можно взять верхний диск и переместить на
другую, но разрешено класть диск лишь на доску или на диск большего
диаметра. Нужно переместить всю башню с иглы 1 на иглу 3. Эта игра называется "Ханойские башни", поскольку по легенде с n = 64 дисками её начали свыше 1000 лет тому назад монахи в одном монастыре вблизи Ханоя во Вьетнаме; когда они закончат её, наступит конец света. Решением этой игры-задачи является последовательность переносов дисков. Написать программу печати обозначений этих переносов. Для переноса башни из n дисков с иглы 1 на иглу 3 необходимо перенести башню из n - 1 дисков на иглу 2, потом перенести нижний диск на иглу 3 и перенести башню с иглы 2 на иглу 3. При переносе башни с 1 на 2 вспомогательной является игла 3, а при переносе с 2 на 3 - игла 1. Другая последовательность действий невозможна. Как видим, решение задачи для башни высотой n описывается через решение задачи для башни высотой n - 1. Обозначим disk(a, b) перенос одного диска с иглы a на иглу b, tow(h, a, b, c) - перенос башни высотой h с иглы a на иглу b с использованием иглы c как вспомогательной. При h > 1 выполнение tow(h, a, b, c) сводится к выполнению: tow(h - 1, a, c, b); disk(a, b); tow(h - 1, c, b, a). А при h = 1 - к выполнению: Disk(a,b) Итак, имеем программу: Program Hantow (input, output); var n: integer; Procedure disk (f, t: integer); begin writeln(f, '->', t) end; Procedure tow (h: integer; f, t, v: integer); begin if h=1 then disk (f, t) else begin tow (h-1, f, v, t); disk (f, t); tow (h-1, v, t, f); end end; begin readln (n); tow (n, 1, 3, 2) end.Очевидно, что глубина рекурсии этой процедуры равна значению, которое получает первый параметр h. Определим количество переходов дисков как функцию f(n), где n - высота башни. Очевидно, что f(1) = 1 и что f(n) = 2 * f(n - 1) + 1. По принципу индукции нетрудно доказать, что f(n) = 2n - 1. |
