Задача о Ханойской башне

при наборе использовался TeX

{\bf \large Задача о Ханойской башне}
\vskip3mm
\noindent
Рекурсия является одним из фундаментальных «концептуальных
инструментов», имеющихся в распоряжении программиста.

Проиллюстрируем некоторые принципы решения задач c
помощью {\it рекурсивных} алгоритмов
на примере {\it
задачи о Ханойской башне}.

Эту головоломку придумал
французский математик Эдуард Люк\’а в 1883~г. Башня
представляет собой восемь дисков, нанизанных на один из
трех колышков в определенном порядке: диаметр нижнего
диска самый большой, затем от диска к диску
диаметры уменьшаются (самый верхний диск самого маленького
диаметра):

%\vskip1.54cm
\begin{center}
\scalebox{0.7}{\includegraphics{hanoi}}\\*
\end{center}
\noindent
Как переместить всю «башню» на один из свободных колышков,
не нарушая следующих  условий:
\vskip-2mm
\begin{itemize}
\item[—] за один «ход» можно снимать один диск;
\item[—] нельзя диск большего диаметра класть на диск меньшего диаметра?
\end{itemize}

\noindent
(Диски можно нанизывать на любой из колышков: использовать
третий, возвращать диски на первый,\dots)

\vskip3mm
\hrule
\vskip2mm

\noindent
{\bf Упражнение.} Подумайте, как можно это сделать за
как можно меньшее число «ходов».
\vskip2mm
\hrule
\vskip3mm

\noindent
Если вы испытываете затруднения при решении этой задачи,
попробуйте для начала переложить три диска.

\vskip3mm
\noindent
Готово? Теперь переложите

\noindent
{\bf 4 диска}.
Если вы снова запутались, то представьте следующую
ситуацию: вы 3 диска уже переложили, например,
на третий колышек. На первом колышке
остался самый большой диск. Вы перекладываете его
на второй колышек, а затем на него, уже проверенным вами способом,
перекладываете 3 остальных диска. После этого объяснения
можно представить, как переложить

\noindent
{\bf 5 дисков}: переложить 4 диска (см. предыдущий абзац), затем
один (последний), и на него только что описанным способом
водрузить эти 4 диска.

%\newpage
\noindent
{\bf 8 дисков} мы
начинаем перемещать после того, как получили
башню из сначала 5 (предыдущий абзац), затем, последовательно, 6
и 7 дисков).

\noindent
Таким образом, для любого числа $n$ дисков их можно переместить
следующим образом: сначала переместить $n-1$ меньших дисков,
затем переложить самый большой, и, наконец
$n-1$ меньших дисков поместить обратно на самый большой диск.
Давайте подсчитаем,  сколько перемещений дисков понадобится,
чтобы решить головоломку «ханойская башня».

\noindent
Переместить башню, состоящую из одного диска, можно за один ход.
Башню из двух дисков — за 3 хода, из четырех — за 3+3+1=7 ходов,
из 5 за 7+7+1=15 ходов и т.д. Запишем это в виде таблицы:

%\vskip2mm
\begin{tabular}{cc}
{\bf количество дисков}& {\bf число перемещений}\\
&\\
1&1\\
2&3\\
3&3+3+1=7\\
4&7+7+1=15\\
5&15+15+1=31\\
6&31+31+1=63\\
7&63+63+1=127\\
8&127+127+1=255\\
\end{tabular}
\vskip1mm

\noindent
%В общем
%случае для нахождения количества $P_n$ перемещений $n$ дисков  нужно количество,
%ходов, полученное для перемещения $n-1$ диска умножить на 2 и прибавить
%1 — перемещение последнего диска: $P_n=2\cdot P_{n-1}+1$.
%
%[МП2 -15]
Можно ли сдедать меньше ходов? Простое рассуждение показыает, что нет.
Пусть $P_n$ — минимальное число перемещений. В определенный
момент понадобится перенести самый большой, $n$-й диск на
третий колышек. Для этого необходимо, чтобы все $n-1$
дисков были на втором колышке, что потребует, по меньшей мере
$P_{n-1}$ перемещений. Затем будет выполнено одно перемещение
большого диска, а затем еше по меньшей мере (можно же ведь перекладывать
один диск несколько раз туда и обратно, не трогая других) $P_{n-1}$
перемещений. Итого $P_{n}=2\cdot P_{n-1}+1$ $(*)$. Но $P_0=0$ и, исходя из
последнего равенства, таблица «количество дисков — количество
соответствующих им перемещений» будет в точности такой же.
Получаем, что найденный нами алгоритм оптимальный.

%\vskip3mm
\noindent
Автор головоломки связывал свою игрушку с легендой о башне Брамы,
состоящей из 64 золотых дисков, нанизанных на три алмазных
шпиля. По легенде Всевышний при сотворении мира поместил диски на
первый шпиль и повелел, чтобы жрецы переместили их на третий,
не нарушая приведенных выше правил. Жрецы занимаются
перекладыванием дисков день и ночь, а когда они закончат,
башня рассыплется в прах и наступит конец света.

Предположим, что перекладывание одного диска занимает секунду.
Тогда башню из 8 дисков можно переложить за 255 секунд,
то есть чуть больше, чем за 4 минуты.
Сколько времени потребуется жрецам для перекладывания
своей башни?

Напишим программу, подсчитывающую количество перекладываний для
$n$ дисков.

%\newpage
\begin{alltt}
Program bashnya;
var n:integer;
function podschet(n:integer):longint;
begin
if n<=0 then begin writeln('n ошибочно!');exit; end;
if n=1  then podschet:=1;
if n>1  then podschet:=2*podschet(n-1)+1;
end;
begin
readln(n);
writeln('Количество перекладываний = ', podschet(n));
end.
\end{alltt}

\vskip2mm
\noindent
В этой программе мы употребили новый тип — {\tt longint}
(сокр. от long integer — «длинное целое»).
Типом {\tt integer} описываются целые числа, большие — 32 767,
но меньшие 32 768. Ячейка памяти, отводимая для целых
чисел типа {\tt integer}, занимает 2 байта (= 8 бит).
Как вы помните (см. {\bf Введение}, раздел «Единицы
измерения памяти компьютера»), в одном бите размещается
либо 0, либо 1. Поскольку числа в компьютере хранятся в
двоичном виде, то максимальное число, которое можно
записать в 8 битах — $1111 1111_2= 1 0000 0000_2-1 = 2^9-1=65 535_{10}$,
но целые числа могут быть и отрицательными, поэтому 8 битов размещают
числа от -32 767 до 32 768.

Если же мы работаем с числами, выходящими за рамки этого
диапазона, то тип выбираем другой ({\tt longint, comp} для
работы с целыми числами, {\tt double} и {\tt extended} —
c действительными — см. таблицу ниже). Почему бы не оставить
один тип, вмещающий самые большие числа? Исключительно в целях
экономии памяти и времени работы программы. Для этого даже ввели типы,
которые описывают числа в диапазоне, меньшем, чем integer.

\noindent
\begin{tabular}{| c| c| c| c| c|}
\hline
& тип     &число & минимальное& максимальное \\
& данного & байт & (по модулю для& (по модулю для\\
&         &      & вещественных) & вещественных)\\
&         &      & число         & число\\
\hline
целочис- & shortint& 1  &-128           & 127\\
ленные   & byte    & 1  &0              & 255 \\
(целые)  & integer & 2  &- 32 768       & 32 767\\
значения & word    & 2  & 0             & 65 535 \\
& longint & 4  & -2 147 483 648&2 147 483 647\\
& comp\footnotemark{}&8&
$-9\cdot 10^{18}$&$9\cdot 10^{18}$\\
\hline
вещест- & single   & 4  &$2.9\cdot 10^{-39}$  &$\pm 1.7\cdot 10^{38}$ \\
венные   & real    & 6  &$1.5\cdot 10^{-45}$  & $\pm 3.4\cdot 10^{38}$\\
значения & double  & 8  & $1.7\cdot 10^{-308}$  & $\pm 1.7\cdot 10^{308}$\\
& extended&10  & $1.1\cdot 10^{-4932}$  & $\pm 1.7\cdot 10^{4932}$\\
\hline

\end{tabular}
%\vskip2mm

\noindent
\begin{tabular}{| c| c| c| c|}
\hline
символь-&\ \ char\ \ \ & 1& \\
ный&\ string\ \ &\ \ \ 0-$k,$ \ \ \ & где $k=255$(символов)\\
\hline
логичес-\ \  &\ boolean\ \ &1&(0 — «ложь», 1 — «истина»)\\
\hline
\end{tabular}

\footnotetext{\ Паскаль по техническим причинам считает этот тип вещественным.}
\vskip2mm
\noindent
Целочисленные константы можно записывать в шестнадцатеричной
системе счисления. Перед числом в этом случае ставится символ «\$».
Обычный способ 100, -1, шестнадцатеричный — \$64, \$FFFF.

\vskip2mm
\noindent
{\bf Замечание.}
\vskip1mm
\noindent
Если переменной определенного типа присвоить
число, выходящее по размеру за диапазон допустимых для этого типа чисел,
то Паскаль сообщение об ошибке выдает не всегда.

Пусть, например, в разделе {\tt var} описана переменная {\tt a:integer}.
Если в программе записать {\tt a:=40000}, то при трансляции компилятор
Паскаля выдаст ошибку ({\tt Error 76: constant  out of range}).
Последовательность операторов {\tt a:=40; a:=a*a*a;}
«проглотится» Паскалем, без каких-либо последствий. Программа будет
успешно откомпилирована. Но если вы захотите посмотреть содержимое
переменной {\tt a} после выполнения этих операторов (распечатать или
через {\bf Watch} из меню {\bf Debug}), то увидите отрицательное
число {\tt -1536}.
Проверяйте самостоятельно, не превышают ли
по модулю данные, заносимые в переменные максимально (минимально)
допустимое значение для объявленного типа!

{\scriptsize
\noindent
Есть еще один способ~— «автоматизировать проверку»~в опциях компилятора
({\bf Options/Compiler/}) установить {\bf Overflow checking}.
В этом случае компилятор будет подсчитывать результаты вычислений
и проверять, не выходят ли они за диапазон допустимых зачений
данного типа. Не забудьте, установив данную опцию, перекомпилировать
вашу программу ({\bf F9}). Если программа уже компилировалась до смены
опций, то запуск ее на исполнение с новыми
опциями командой {\bf Run (F9)} ничего не изменит. Если же все
изменения внесены корректно, то при компиляции, дойдя до
строки {\tt a:=a*a*a;},  Паскаль выдаст сообщение
об ошибке: {\tt Error 215: Arithmetic overflow}.
}
\vskip2mm
\hrule
\vskip2mm

\noindent
{\bf Упражнение.} Проверьте, какое максимальное
количество дисков можно вводить в программу
подсчета количества шагов в головоломке «ханойская башня»
(тип функции можно изменить).

\vskip2mm
\hrule
\vskip3mm

\noindent
Как было уже сказано, программирование рекурсивных алгоритмов
сопряжено с рядом трудностей. Поэтому, рекурсивно проанализировав задачу,
стремятся вывести формулу, не требующую вычислений всех
значений меньшей размерности~— такую функцию $f(n)$,
что для вычисления ее значения для $n$ не требуется
знать ее значение для $n-1$, $n-2$ и т.д.

Взгляните еще раз на таблицу
«количество дисков — количество соответствующих им перемещений»:
1 диск — 1 перемещение, 2 диска— 3, 3 диска — 7, 4 — 15.
Похоже на то, что для $n$ дисков требуется $2^n-1$ перемещений.
Но утверждать мы это пока не можем: нужно сначала  проверить
эту формулу для любого возможного количества дисков. Сделать это
можно с помощью {\it метода математической индукции}.

Для этого проверяется «крайние» значения: для $n=0$ $2^0-1=0$,
для $n=1$ $2^1-1=1$ — формула верна.
Пусть формула верна для $n-1$ дисков, то есть предположем,
что количество перемещений для башни из $n-1$ дисков требуется
$2^{n-1}-1$
перемещений. Если исходя из этого мы докажем,
что формула верна для $n$ дисков, т.е. $P_n=2^n-1$, то,
метод математической индукции «признает»
формулу, которую мы доказываем, справедливой для всевозможного
количества дисков.

\noindent
Итак,
%\noindent
1. $P_n=2\cdot P_{n-1}+1$ (было показано ранее).\\
2. $P_{n-1}=2^{n-1}-1$ — предположение.\\
3. Из 1. и 2. следует, что $P_n=2\cdot (2^{n-1}-1)+1=2^n+1$,
что и требовалось доказать. ([1])

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

методические материалы по информатике