I am learning the C ++ language from a book, it has come to recursion in C ++. After the chapter was the task "Tower of Hanoi". The problem is this: how to solve this problem using the recursion method, I understood it myself, but the book suggested that the same problem be solved using the iterative method, and now there are problems with it. In general, I understood how to shift disks depending on the evenness or oddness of their number: if even, then the first disk is shifted to the intermediate peg, otherwise - to the final one. In the process of solving, I tried to shift, starting from disc 1, gradually increasing the number of disks loaded, so if I need to shift 5 disks from the 1st to the 3rd peg, then I put 1 disk on 3, then I need to shift the next disk from the initial Stacks on the 2nd peg and on it 1 disc, 2 discs are shifted, then we put the 3rd disc on the 3rd peg, we need to put those 2 discs on it, in order to shift them, we also need to start from one, and I can’t I could think of this idea, it didn’t work out in a cycle to keep track of how much I still need to shift and at the same time change pegs status (start, intermediate, finish). I tried to find a solution and ran into ways using vectors and arrays, this was not in my book yet, therefore, I need to solve it in some other way.

  • one
    In this way it is proposed to decide to better assimilate the material of the chapter, and not to jump to what will be in the next one. - SJerin
  • one
    "Try to write an iterative version of the Hanoi Towers problem. If you succeed, compare your iterative version with the recursive one developed in the previous exercise. Examine the issues of performance, clarity, and ability to justify the correctness of the programs." - so the task from the book sounds. I just do not want to leave it, I have been sitting for quite a long time, this task is haunted, I wonder how you can still solve it. - SJerin
  • one
    No one asked for a chewed answer. I asked to clarify the place of my stupor. Thanks for answers. - SJerin
  • one
    When I solved this problem recursively, I didn’t store the tower anywhere, it just exists conditionally. I had a function there that takes 4 parameters: the number of disks, starting, intermediate and finishing pegs, just their numbers were indicated. And there was a change in the status of pegs, i.e. the next time you call this function, for example, the finishing and intermediate pegs change. - SJerin
  • one
    The book "How to program in C ++." H.M. Deitel, P.J. Deytel. - SJerin

1 answer 1

Here is an excerpt from the book of A. Shen. Programming: theorems and problems 2nd ed., M .: MTSNMO, 2004, 296 p. ( pdf, 2.1M ) :

8.2.1. Write a non-recursive program for finding the sequence of displacements of rings in the problem of Hanoi towers.

Decision.

Recall a recursive program that shifts i upper 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-mn; {s - третий стержень: сумма номеров равна 6} move (i-1, m, s); writeln ('сделать ход ', m, '->', n); move (i-1, s, n); end; end;

It can be seen that the task “transfer i top disks from the m th rod to the n th one” is reduced to three tasks of the same type: two tasks with i-1 disks and one task with a single disk. Being engaged in these tasks, it is important not to forget what remains to be done.

For this purpose, we will start a stack of deferred tasks , whose elements are triples (i,m,n) . Each such triple is interpreted as an order "to shift i upper disks from the m th rod to the n th". Orders are ordered according to the 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-pq; {s - третий стержень: сумма номеров равна 6} положить в стек тройки <j-1,s,q>, <1,p,q>, <j-1,p,s> end; end; end;

(Note that a triple is put first on the stack, which must be done last.) A stack of triples can be implemented as three separate stacks. (In addition, there is a special type in pascal called a “record” that can be used.)

  • Either my eyes are fooling me, or it is Pascal. - VladD
  • He is the most, well, if you give a ready solution to the questioner, he (she) does not learn anything, as I understand the person solves the problems for himself from the book in order to learn how to program, and not for someone) - a1ip