Tower of Hanoi iterative method?

Question

Programming

Hello! I'm learning C++ from a book, got to recursion in C++. After the chapter was the task "Tower of Hanoi". The problem is this: I figured out how to solve this problem using the recursion method myself, but in the book it was proposed to solve the same problem using the iterative method, and there were problems with this. In general, I understood how to shift the disks depending on the even or odd number of them: if it is even, then the first disk is transferred to the intermediate peg, otherwise - to the finish. In the process of solving, I tried to shift, starting from 1 disc, gradually increasing the number of shifted discs, so if you need to shift 5 discs from the 1st to the 3rd peg, then I put 1 disc on 3, then you need to shift the next disc from the initial stacks on the 2nd peg and 1 disk on it, 2 disks are shifted, then we put the 3rd disc on the 3rd peg, you need to put those 2 discs on it in order to shift them, you also need to start from one, and I couldn’t think of this idea, I couldn’t keep track of how much I still have to shift and while changing the status of the pegs (starting, intermediate, finishing). Tried to find a solution and stumbled on ways using vectors and arrays, this was not in my book yet, therefore, I need to solve it somehow differently.

Answer 1

Here is an excerpt from A. Shen's book to help you. Programming: theorems and problems 2nd ed., M.: MTsNMO, 2004, 296 p. ( pdf, 2.1M ) Pascal language is used here:
Recall a recursive program that shifts the top i rings from m to 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;

It can be seen that the problem of "move i upper disks from the m - th pivot to the n - th one" reduces to three problems of the same type: two problems with i-1 disks and one problem with a single disk. As you tackle these tasks, it's important to remember what's left to do.
For this purpose, let's create a stack of pending tasks , the elements of which will be triplets (i,m,n) . Each such triple is interpreted as an order to "transfer i upper disks from the m - th rod to the n - th one". Orders are ordered according to the required order of their execution: the most urgent is the top of the stack. We get the following program:

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;

(Note that the triple is pushed onto the stack first, and must be executed
last.) A stack of triples can be implemented as three separate stacks. (Also, Pascal has a special type called a "record" ( record ) that can be used.)