Из разделов чистой математики (не углубляясь в деталях) известно, что в форме рекурсивной формулировки может быть выражен любой вычислимый алгоритм. Одной из самых любопытных иллюстраций возможностей и мощи рекурсивных вычислений является задача Ханойская башня.
Утверждается, что эту задачу сформулировали и решают до сих пор монахи каких-то из монастырей Тибета. Задача состоит в том, чтобы пирамидку из колец (на манер детской игрушки), нанизанную на один из 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), что представляет собой очень высокую степень роста вычислительной сложности задачи — экспоненциальную.