Задача о Ханойских башнях, Ханойские башни Опции

[Игорь]

Решить методом "разделяй и властвуй"("divide et impero").
Задача Ханойских башен.
Даны три оси, обозначенные через 1, 2, 3 и n дисков разных диаметров с отверстиями посередине. В начале все диски расположены в убывающем порядке, на одной из осей(от основания к верхушке). Разработайте программу, которая переводит все диски на ось 2 с использованием оси 3, придерживаясь следующих правил:
- На каждом шаге переносится только один диск
- Любой диск может быть положен на только другой диск с большим диаметром.
Указания.
перенос диска с оси i на ось j может быть представлен, как пара(i,j), где i,j принадлежат (1,2,3), i<>j. Через H(m,i,j) обозначим ряд перестановок, необходимых для переноса первых m дисков(расположенных сверху) с оси i на ось j.
Например:
H(1,1,2)=(1,2);
H(2,1,2)=(1,3),(1,2),(3,2);
H(3,1,2)=(1,2),(1,3),(2,3),(1,2),(3,1),(3,2),(1,2).
В общем случае
H(m,i,j)=|(i,j),m=1;
|H(m-1,i,k),(i,j),H(m-1,k,j),m>1.
Где k=6-i-j. Как следствие, задача n дисков сводится к решению двух подзадач того же типа для (n-1) дисков.
:o

см. Ханойские башни ( http://forum.pascalnet.ru/index.php?showtopic=9254 )

Сообщение отредактировано: Altair - 10.02.2006 12:43