Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Башни ханоя - модифиц. версия

Автор: nini 4.2.2007, 16:36

Дана проблема "Башни ханоя" - 3 оси A,B и C; Самый малый, верхний диск обозн. как 1, самый нижний и самый большой - n. Диски должны быть перенесены с А на B.
Условие (и моя проблема) - диск не может быть перенесен непосредственно с А на B или наоборот.
--
Как подказка - должны использоваться 3 рекурсивных вызова.

Кто-нибудь может уже сталкивался с такой проблемой? Какие-нибудь идеи?
Буду очень, очень признателен за помощь!

Автор: Michael_Rybak 5.2.2007, 15:09

Зная, как решить задачу для некоторого N-1, получим решение для N. Сначала применим полностью решение для N-1. Получаем:

A: (N), C: (), B: (N-1, N-2, ..., 1)

Теперь выполняем A->C:

A: (), C: (N), B: (N-1, N-2, ..., 1)

Теперь применяем опять решение для N-1, но мысленно поменяв между собой А и В. Получаем

A: (N-1, N-2, ..., 1), C: (N), B: ()

Дальше понятно.

Автор: nini 6.2.2007, 00:05

Спасибо,
Это, насколько я помню, матем.индукция?
Но, честно говоря, как это запрограммировать (т.е. алгоритм с в.н. ограничением), я так и понял; не смог, сколько ни пытался smile

Автор: Michael_Rybak 6.2.2007, 00:15

Что-то вроде этого:

Код


SolveABC(int N, char A, char B, char C)
  if N = 1
    print A "->" B
    print B "->" C
  else
    SolveABC(N - 1, A, B, C)
    print A "->" B
    SovleABC(N - 1, C, B, A)
    print B "->" C
    SolveABC(N - 1, A, B, C)
End

input x
SolveABC(x, 'A', 'B', 'C')

Автор: nini 6.2.2007, 11:25

Спасибо большое!!! smile

Заработало!
А можно smile

немного больше объяснения к теоретической части?

Автор: Michael_Rybak 6.2.2007, 23:50

А что тебе непонятно? Я даже не знаю, что именно тут подробнее описывать. Умея решать задачу для 5 дисков, мы это умение применяем, не обращая внимания на 6й диск. Потом его перекладываем. Потом опять применяем умение, только диски ставим в другую сторону (не с А на В а с В на А). Опять обращая внимания на 6й диск. Потому что 6й большой, ему видней. Ну и потом его переставляем на В, и опять таки применяем свое умение, и получаем +3 опыта и артефакт - башню В.