З розділів чистої математики (не заглиблюючись в деталях) відомо, що в формі рекурсивної формулювання може бути виражений будь обчислюваності алгоритм. Однією з найцікавіших ілюстрацій можливостей і мощі рекурсивних обчислень є завдання Ханойська вежа.
стверджується, що це завдання сформулювали і вирішують досі ченці якихось із монастирів Тибету. Завдання полягає в тому, щоб пірамідку з кілець (на манер дитячої іграшки), нанизану на один з 3-х стержнів, перенести на інший такий же стрижень, дотримуючись строгих правил:
- пірамідка складається з N кілець різного розміру, укладених по спадаючій діаметра кілець один на інший;
- перекладати за одну операцію можна тільки одне кільце з будь-якого штиря на будь-який ...
- але тільки за умови, що класти можна тільки менше кільце зверху на більшу, але ніяк не навпаки;
- потрібно, в підсумку, всю вихідну пірамідку, що лежить на штирі №1, перемістити на штир №3, використовуючи штир №2 як проміжний.
Наприклад, для 2-х кілець результат виходить такий ось послідовністю перекладань: 1 => 2 , 1 => 3 , 2 => 3
За переказом, це завдання з перекладання N = 10 кілець, вирішують тибетські монахи, і коли вони її, нарешті, вирішити, тоді і настане кінець світу ... Армагедон, в нашому західному нотації.
Для особливо охочих повправлятися, тут же формулюємо завдання №2: спробуйте вирішити цю завдання не рекурсивними методами (це дуже непросте заняття)!
А тепер запишемо рішення задачі:
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; } |
рішення тут (якщо його таким можна назвати) полягає в тому, щоб при необхідності перенесення піраміди з n кілець з штиря з номером from на штир з номером to послідовно зробити наступне:
- перенести (якимось чином) меншу піраміду з n-1 кілець тимчасово на штир з номером temp, щоб не заважала…
- перенести залишився єдине нижню (найбільше) кільце на результуючий штир з номером to
- після чого, точно так само як в першому пункті, відрізати піраміду (n-1 кілець) з номера temp поверх цього найбільшого кільця на штир з номером to.
Тут важливо те, що ми не знаємо яким чином, і не вміємо виконати 1-й і 3-й пункт нашої програми, але сподіваємося, що він буде рекурсивний розкручуватися за аналогією, за тим же алгоритмом, але для меншого числа n-1 (основоположний принцип рекурсії)… поки n не стане рівним 1 – а там вже зовсім просто.
І ось як розгортається рішення для різних 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 |
Можете виконати цю програму для N = 10 (тільки не спровокує тим кінець світу!) і переконатися, що число перестановок для цього буде потрібно 1023. І взагалі, для будь-якого N число перестановок буде 2**(N – 1), що являє собою дуже високу ступінь зростання обчислювальної складності задачі - експонентну.