Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

for
(
int
i = 1; i <= discs; i++) {
towerA.push(i);
}
}
1.5.2. Решение задачи о ханойских башнях
Как.можно.решить.задачу.о.ханойских.башнях?.Предположим,.что.мы.пыта-
емся.переместить.только.один.диск..Тогда.мы.бы.знали,.как.это.сделать,.верно?.
Фактически.перемещение.одного.диска.—.базовый.случай.для.рекурсивного.
решения.данной.задачи..Перемещение.нескольких.дисков.—.это.рекурсивный.
случай..Ключевой.момент.в.том,.что.у.нас,.по.сути,.есть.два.сценария,.которые.
необходимо.закодировать:.перемещение.одного.диска.(базовый.случай).и.пере-
мещение.нескольких.дисков.(рекурсивный.случай).
Чтобы.понять.рекурсивный.случай,.рассмотрим.конкретный.пример..Предпо-
ложим,.у.нас.есть.три.диска.—.верхний,.средний.и.нижний,.расположенные.на.
башне.А,.и.мы.хотим.переместить.их.на.башню.С..(Впоследствии.это.поможет.

---

44
Глава 1.
Простые задачи
схематически.описать.задачу.).Сначала.мы.могли.бы.переместить.верхний.диск.
на.башню.С..Затем.—.переместить.средний.диск.на.башню.B,.а.после.этого.—.
верхний.диск.с.башни.C.на.башню.B..Теперь.у.нас.есть.нижний.диск,.все.еще.
расположенный.на.башне.A,.и.два.верхних.диска.на.башне.B..По.существу,.мы.
уже.успешно.переместили.два.диска.с.одной.башни.(A).на.другую.(B)..Пере-
мещение.нижнего.диска.с.A.на.C.—.это.базовый.случай.(перемещение.одного.
диска)..Теперь.можем.переместить.два.верхних.диска.с.B.на.C.посредством.той.
же.процедуры,.что.и.с.A.на.B..Перемещаем.верхний.диск.на.A,.средний.—.на.C.
и,.наконец,.верхний.—.с.A.на.C.
СОВЕТ
В.учебных.классах.информатики.нередко.встречаются.маленькие.модели.этих.башен,.
построенные.из.штырей.и.пластиковых.дисков..Вы.можете.изготовить.собственную.
модель.с.помощью.трех.карандашей.и.трех.листов.бумаги..Возможно,.это.поможет.вам.
наглядно.представить.решение.
В.примере.с.тремя.дисками.был.простой.базовый.случай.перемещения.одного.
диска.и.рекурсивный.случай.перемещения.остальных.дисков.(в.данном.случае.
двух).с.применением.временной.третьей.башни..Мы.можем.разбить.рекурсивный.
случай.на.следующие.этапы.
1.. Переместить.верхние.
n
.–.1.дисков.с.башни.A.на.башню.B.(временная),.ис-
пользуя.C.в.качестве.промежуточной.башни.
2.. Переместить.нижний.диск.с.A.на.C.
3.. Переместить.
n
.–.1.дисков.с.башни.B.на.башню.C,.башня.A.—.промежуточная.
Удивительно,.но.этот.рекурсивный.алгоритм.работает.не.только.для.трех,.но.
и.для.любого.количества.дисков..Закодируем.его.как.функцию.
move()
,.которая.
отвечает.за.перемещение.дисков.с.одной.башни.на.другую,.задействуя.третью.
временную.башню.(листинг.1.21).