Ханойская башня итеративный метод?

Question

[SJerin]

Здравствуйте! Я изучаю язык С++ по книге, дошла до рекурсии в C++. После главы было задание "Ханойская башня". Проблема заключается в следующем: как решить данную задачу методом рекурсии, я поняла сама, но в книге было предложено решить ту же задачу итеративным методом, и вот с этим возникли проблемы. В целом я поняла, как нужно перекладывать диски в зависимости от четности или нечетности их количества: если четное, то первый диск перекладывается на промежуточный колышек, иначе - на финишный. В процессе решения я пыталась перекладывать, начиная с 1 диска, постепенно увеличивая количество переложенных дисков, так, если нужно переложить 5 дисков с 1-ого на 3-ий колышек, то 1 диск я клала на 3, далее нужно переложить следующий диск из начальной стопки на 2-ой колышек и на него 1 диск, 2 диска переложено, затем кладем 3-ий диск на 3-ий колышек, на него нужно положить те 2 диска, чтобы их переложить, нужно также начинать с одного, и я никак не могла продумать эту идею, никак не выходило в цикле отслеживать сколько мне еще переложить и при этом менять статус колышков(стартовый, промежуточный, финишный). Пыталась найти решение и натыкалась на способы с использованием векторов и массивов, этого в моей книге еще не было, следовательно, мне нужно решить это как-то иначе.

Answer 1

[Philippe Rigovanov]

Вот Вам в помощь отрывок из книги А. Шень. Программирование: теоремы и задачи 2-е изд., М.: МЦНМО, 2004, 296 с. (pdf, 2.1M) здесь правда используется язык Паскаль:

8.2.1. Написать нерекурсивную программу для нахождения последовательности перемещений колец в задаче о ханойских башнях.

Решение.

Вспомним рекурсивную программу, перекладывающую 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 верхних дисков с m-го стержня на n-ый" сводится к трём задачам того же типа: двум задачам с i-1 дисками и к одной задаче с единственным диском. Занимаясь этими задачами, важно не позабыть, что ещё осталось сделать.

Для этой цели заведём стек отложенных заданий, элементами которого будут тройки (i,m,n). Каждая такая тройка интерпретируется как заказ "переложить i верхних дисков с m-го стержня на n-ый". Заказы упорядочены в соответствии с требуемым порядком их выполнения: самый срочный - вершина стека. Получаем такую программу:

procedure move(i,m,n: integer);
    begin
      сделать стек заказов пустым
      положить в стек тройку <i,m,n>
      {инвариант: осталось выполнить заказы в стеке}
      while стек непуст do begin
        удалить верхний элемент, переложив его в <j,p,q>
        if j = 1 then begin
          writeln (’сделать ход’, p, ’->’, q);
        end else begin
          s:=6-p-q;
            {s - третий стержень: сумма номеров равна 6}
          положить в стек тройки <j-1,s,q>, <1,p,q>, <j-1,p,s>
        end;
      end;
    end;

(Заметим, что первой в стек кладётся тройка, которую надо выполнять
последней.) Стек троек может быть реализован как три отдельных стека. (Кроме того, в паскале есть специальный тип, называемый "запись" (record), который может быть применён.)