Классическая задачка, однако, её всё ещё решают новые поколения школьников и студентов :)
Даны три стержня, на один из которых нанизано N колец, при этом все кольца отличаются размером и лежат меньшее на большем. Требуется перенести пирамиду на другое кольцо за наименьшее число ходов. За один раз разрешается переносить только одно (лежащее сверху) кольцо, при этом нельзя класть большее кольцо на меньшее.

Для решения задачи достаточно переложить всё, что находится выше самого большого диска, с первого стержня на вспомогательный, затем переложить самый большой диск с первого стержня на второй, наконец, переложить оставшуюся пирамиду с третьего стержня на второй, пользуясь освободившимся первым как вспомогательным. Получается классический пример рекурсии.

Вот реализация на Паскале, близкая к оптимальной:

procedure Move (M,A,B:integer);
{Перемещает M верхних колец со стержня A на B}
var C:integer;
begin
 if M=1 then write (A,'->',B,'  ') 
 else begin
  C:=6-A-B; {C - третий стержень}
  Move(M-1,A,C);
  Move(1,A,B);
  Move(M-1,C,B)
 end
end;

var n:integer;
begin
 write('Число колец='); readln(N);
 write ('Порядок перекладывания колец по стержням: ');
 Move(N,1,2);
 reset (input); readln;
end.

Программа показывает весь порядок перекладывания колец по стержням, с какого стержня и на какой следует переложить верхнее кольцо. Здесь кольца перекладываются с первого на второй стержень, что нужно изменить в программе, чтобы перекладывать с первого на третий? Правильно, только вызов процедуры, он будет иметь вид

Move(N,1,3);

Легко заметить, что число перекладываний при числе колец N равно 2N-1.

гостевая; E-mail