Of the sections of pure mathematics (without going into details) known, that any computable algorithm can be expressed in the form of a recursive formulation. One of the most interesting features of images and the power of recursive computation is the problem of the Tower of Hanoi.
Allegedly, that this problem is formulated and solved still some monks from monasteries in Tibet. The challenge is, to the pyramid of the rings (in the style of children's toys), strung on one of the 3 bars, transfer to another such rod, adhering to strict rules:
- N pyramid consists of rings of different sizes, descending rings stacked one on another diameter;
- shift in a single operation can be only one ring from any pin on any ...
- but only if, that can only be put on top of a smaller ring for more, but not vice versa;
- necessary, eventually, All original pyramid, lying on the pin №1, move to pin №3, №2 using the pin as an intermediate.
For example, for 2 rings result is such a sequence rearrangements: 1 => 2 , 1 => 3 , 2 => 3
According to legend, the task of passing the N = 10 rings, solve the Tibetan monks, and when it, finally, decide, and then come to an end ... Armageddon, in our Western notation.
For those wishing to exercise special, immediately formulate the task №2: try to solve this problem is not recursive methods (this is a very difficult task)!
Now we write the solution of the problem:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #include <stdlib.h> #include <iostream> using namespace std; // ============> схема что и куда переносим // -|- | | // --|-- | | // ---|--- | | // 1 2 3 int nopr = 0; // счётчик операций // собственно перенос 1-го кольца с from на to void put( int from, int to ) { cout << from << " => " << to << " | "; if( 0 == ( ++nopr % 5 ) ) cout << endl; } // перенос с позиции from на позицию to n колец: void move( int from, int to, int n ) { int temp = from ^ to; // промежуточная позиция if( 1 == n ) put( from, to ); // перенести это единственное кольцо else { move( from, temp, n - 1 ); // перенести n-1 верхних на temp put( from, to ); // перенести самое нижнее на to move( temp, to, n - 1 ); // поместить n-1 с temp на to } } int main( int argc, char **argv, char **envp ) { int n = 5; // число переносимых фишек if( argc > 1 && atoi( argv[ 1 ] ) != 0 ) n = atoi( argv[ 1 ] ); cout << "размер пирамиды: " << n << endl; move( 1, 3, n ); // вот вам и всё решение! if( 0 != ( nopr % 5 ) ) cout << endl; cout << "общее число перемещений " << nopr << endl; return 0; } |
The solution here (if such can be named) It is, if necessary, to transfer the pyramid of n rings from the pin number on the pin with sequence number to make the following:
- postpone (somehow) smaller pyramid of n-1 rings temporarily pin number with temp, not to interfere…
- transfer remains the sole bottom (most) ring on the pin with the result to the number
- then, just as in the first paragraph, hoist the pyramid (n-1 rings) with temp numbers on top of the largest ring to pin to a number.
It is important that, we do not know how, and we are not able to perform the 1 st and 3 rd place in our program, but hope, that he will Recursive unwind by analogy, using the same algorithm, but a smaller number of n-1 (the fundamental principle of recursion)… while n equals 1 – and there is quite simply.
And now unfold solution for different N:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | $ ./hanoy 2 размер пирамиды: 2 1 => 2 | 1 => 3 | 2 => 3 | общее число перемещений 3 $ ./hanoy 3 размер пирамиды: 3 1 => 3 | 1 => 2 | 3 => 2 | 1 => 3 | 2 => 1 | 2 => 3 | 1 => 3 | общее число перемещений 7 $ ./hanoy 4 размер пирамиды: 4 1 => 2 | 1 => 3 | 2 => 3 | 1 => 2 | 3 => 1 | 3 => 2 | 1 => 2 | 1 => 3 | 2 => 3 | 2 => 1 | 3 => 1 | 2 => 3 | 1 => 2 | 1 => 3 | 2 => 3 | общее число перемещений 15 $ ./hanoy 5 размер пирамиды: 5 1 => 3 | 1 => 2 | 3 => 2 | 1 => 3 | 2 => 1 | 2 => 3 | 1 => 3 | 1 => 2 | 3 => 2 | 3 => 1 | 2 => 1 | 3 => 2 | 1 => 3 | 1 => 2 | 3 => 2 | 1 => 3 | 2 => 1 | 2 => 3 | 1 => 3 | 2 => 1 | 3 => 2 | 3 => 1 | 2 => 1 | 2 => 3 | 1 => 3 | 1 => 2 | 3 => 2 | 1 => 3 | 2 => 1 | 2 => 3 | 1 => 3 | общее число перемещений 31 |
You can run this program for N = 10 (not only provoke the end of the world!) and make sure, that the number of permutations for this need 1023. And generally speaking, for any N is the number of permutations 2**(N – 1), that is a very high degree of growth of the computational complexity of the problem - the exponential.