Кодинг
★ Рубрика: Кодинг
★ Тема: Алгоритмы

Рекурсия и ханойские башни

Задача. Игра "Ханойские башни" состоит в следующем. Есть три стержня. На первый из них надета пирамидка из n колец (большие кольца снизу, меньшие сверху). Требуется переместить кольца на другой стержень. Разрешается перекладывать кольца со стержня на стержень, но класть большее кольцо поверх меньшего нельзя. Составить программу, указывающую требуемые действия.
Решение. Напишем рекурсивную процедуру перемещения i верхних колец с m-го стержня на n-ый (предполагается, что остальные кольца больше по размеру и лежат на стержнях без движения).
procedure move(i,m,n: integer);
 | var s: integer;
 begin
 | if i = 1 then begin
 | | writeln ('сделать ход', m, '->', n);
 | end else begin
 | | s:=6-m-n; {s - третий стержень: сумма номеров равна 6}
 | | move (i-1, m, s);
 | | writeln ('сделать ход', m, '->', n);
 | | move (i-1, s, n);
 | end;
 end;
Сначала переносится пирамидка из i-1 колец на третью палочку. После этого i-ое кольцо освобождается, и его можно перенести куда следует. Остается положить на него пирамидку.
 Похожие публикации: Алгоритмы

Войдите, чтобы добавить Ваш ответ. [ Регистрация | Вход ]