Colleagues, please explain how the program code of the Tower of Hanoi works.

#include <iostream> #include <Windows.h> using namespace std; void Towers(int number, int from, int to, int free) { SetConsoleOutputCP(1251); if(number!=0) { Towers(number-1, from, free, to); cout<<"\n Снимаем "<<number<<"-й диск с "<<from<<"-го стержня и одеваем его на "<<to<<"-й стержень"; Towers(number-1, free, to, from); } } void main() { Towers(3, 1, 3, 2); cout<<"\n "; }
  • "number" is the number of disks.
  • "from" is the pivot from which we transfer all disks.
  • "to" is the pivot on which we transfer all disks.
  • "free" is the third pivot.

And this is the result in the console window:

Снимаем 1-й диск с 1-го стержня и одеваем его на 3-й стержень. Снимаем 2-й диск с 1-го стержня и одеваем его на 2-й стержень. Снимаем 1-й диск с 3-го стержня и одеваем его на 2-й стержень. Снимаем 3-й диск с 1-го стержня и одеваем его на 3-й стержень. Снимаем 1-й диск с 2-го стержня и одеваем его на 1-й стержень. Снимаем 2-й диск с 2-го стержня и одеваем его на 3-й стержень. Снимаем 1-й диск с 1-го стержня и одеваем его на 3-й стержень.

What I understand here is that at the beginning of the function, it immediately recursively calls itself as many times as the "if" condition is true and every time a unit is taken from the "number", comes to "number == 1", and then the first one is output line on console Then again a recursive function call, with arguments arranged in a different order and fog ...

    1 answer 1

    Try an operation with physical objects (rings, paper strips, or something else). The idea is simple: to transfer n rings from one rod to another, you need to transfer n-1 from it to a free (first recursive call), transfer the n-th ring to the target rod ( cout ), then n-1 from the free transfer to the target ( second recursive call). When calling the assignment of rings from, to, free change, you can add the output of their values ​​when rearranging for clarity. So The condition not to put more ring on less is observed. UPD In principle, three debug prints in the procedure itself. True, as far as it helps, it is now unclear to me For the first call (transfer of rings above the lower to the secondary one), for transferring the lower ring (the existing cout) and returning the smaller rings from the secondary ring to the target one.

     #include <iostream> #include <stdio.h> using namespace std; void Towers(int number, int from, int to, int free) { if(number!=0) { fprintf(stderr, "%2d%3d%3d%3d/1\n", number-1, from, free, to); Towers(number-1, from, free, to); fprintf(stderr, "%2d%3d%3d%3d\n", number, from, to, free); cout<<"\n Снимаем "<<number<<"-й диск с "<<from<<"-го стержня и одеваем его на "<<to<<"-й стержень"; fprintf(stderr, "%2d%3d%3d%3d/2\n", number-1, free, to, from); Towers(number-1, free, to, from); } } int main() { cerr << " nfrt" << endl; Towers(3, 1, 3, 2); cout<<"\n "; return 0; }

    Output (/ 1 and / 2 - Tower calls):

      nfrt 2 1 2 3/1 1 1 3 2/1 0 1 2 3/1 1 1 3 2 0 2 3 1/2 2 1 2 3 1 3 2 1/2 0 3 1 2/1 1 3 2 1 0 1 2 3/2 3 1 3 2 2 2 3 1/2 1 2 1 3/1 0 2 3 1/1 1 2 1 3 0 3 1 2/2 2 2 3 1 1 1 3 2/2 0 1 2 3/1 1 1 3 2 0 2 3 1/2

    For proof by induction: the transfer of one ring - just shift. Transfer two - move the top to the backup, move the bottom to the target, move the top from the backup to the target. Transferring several - transfer the upper to the auxiliary pin, transfer the ring number itself, then transfer from auxiliary to target. Since the rings with a diameter smaller are located above, their transfer does not violate the problem rule.

    • Dear, alexlz, this is clear to me. It is not clear another. How are the console window (the console laid out) displayed, for example, the disk numbers, the first line in the console is clear (described when asked the question) The second line: "remove the 2nd disk ...", from where the number 2, etc., I do not I see this in the code. - Key
    • The value of the formal number parameter. It corresponds to the stack depth of the recursive calls to the Towers procedure. Those. at each level, you know which ring is transferred in the procedure body (output to cout). Calling the top level (for transferring all disks) for your example is number == 3. At this point, all the rings above have already been transferred by the first recursive call of Towers to the free pin (in the call, the original to the place of free is the original to and vice versa). And the second call transfers all the rings from free to to with the auxiliary from. While it is better not to explain. It is recommended to print a table of values ​​in the process - alexlz
    • Alexlz, yes, yes, the table is needed, but how to make it? I tried to insert cout-s in the course of the code, but it did not work, and there was no place to insert them. The debugger also does not show. - Key
    • Updated the answer. - alexlz
    • one
      Format output from the library. The prototype is in stdio.h. The first parameter is a stream, the second is a format, the rest are values ​​for output according to a specified format. In iostream, stderr is accessed via cerr. - alexlz