Olej писал(а):
Выразительная мощь рекурсивных решений - огромная.
В этом можете не сомневаться
, это известно из теории алгоритмов ... но это не очевидно, и на это нужно
обращать внимание.
Особенно это в
совершенно практических задачах распознавания образов, оценивания гипотез, поиска оптимальных вариантов ... всегда, когда создаются динамические структуры данных: списки, деревья, графы...
Классикой являются и рекурсивные алгоритмы элементарной сортировки ... только упор здесь нужно бы делать не на само запоминание быстрых алгоритмов, а на логику использования рекурсии в них.
Мне так кажется, что одна из лучших иллюстраций
мощности рекурсии как вычислительного метода - это известная задача "ханойская башня":
- есть 3 штыря ...
- на которые нанизываются пирамидки из колец разного диаметра, на манер детских пирамидок ...
- перекладывать "за-раз" можно только 1-но верхнее кольцо с любого штыря на любой...
- при условии, что перекладывать можно только кольцо меньшего диаметра сверху на кольцо большего диаметра, но не наооборот;
- нужно пирамиду из N колец, лежащих на штыре №1, переместить по этим правилам на штырь №3 (№2 и №3 изначально пустые).
Попробуйте желающие решить эту задачу нерекурсивными методами!
(По преданию, эту задачу перекладывая колечки, решают тибетские монахи, и когда они её решат - тогда наступит конец света
.)
А вот рекурсивное решение:
Код: Выделить всё
#include <stdio.h>
#include <stdlib.h>
int nopr = 0;
void put( int from, int to ) {
printf( "%d => %d, ", from, to );
if( 0 == ( ++nopr % 5 ) )
printf( "\n" );
}
int temp( int from, int to ) { // промежуточная позиция
int i = 1;
for( ; i <= 3; i++ )
if( i != from && i != to )
return i;
}
void move( int from, int to, int n ) {
if( 1 == n ) put( from, to );
else {
move( from, temp( from, to ), n - 1 );
put( from, to );
move( temp( from, to ), to, n - 1 );
}
}
int main( int argc, char **argv, char **envp ) {
int n = 5; // число переносимых фишек
if( argc > 1 && atoi( argv[ 1 ] ) != 0 )
n = atoi( argv[ 1 ] );
printf( "размер пирамиды: n=%d\n", n );
move( 1, 3, n ); // вот и всё решение!
if( 0 != ( nopr % 5 ) )
printf( "\n" );
printf( "общее число перемещений %d\n", nopr );
return 0;
}
Здесь всё решение делается 1-м оператором: move( 1, 3, n );
Но самое интересное здесь то, что я
не знаю алгоритма решения задачи, сам алгоритм находится в процессе раскрутки рекурсивно сформулированной цели задачи!
Т.е.решение здесь формулируется так:
- если n=1 и перетаскивать нужно пирамидку только из 1-го кольца - то просто взять его и переложить: from -> to
- а вот если n!=1, тогда: ...
- переставить (а как? - а я не знаю как это сделать!) верхнюю пирамидку n-1 колец на промежуточный штырь (не from и не to) ...
- переместить оставшееся большой кольцо на to ...
- опять же, переместить n-1 пирамидку (см. выше) с промежуточного штыря на to ...
Вот и всё как просто!
Код: Выделить всё
olej@notebook:~/2013_WORK/AntonG/hanoy$ ./hanoy 2
размер пирамиды: n=2
1 => 2, 1 => 3, 2 => 3,
общее число перемещений 3
olej@notebook:~/2013_WORK/AntonG/hanoy$ ./hanoy 3
размер пирамиды: n=3
1 => 3, 1 => 2, 3 => 2, 1 => 3, 2 => 1,
2 => 3, 1 => 3,
общее число перемещений 7
olej@notebook:~/2013_WORK/AntonG/hanoy$ ./hanoy 4
размер пирамиды: n=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
olej@notebook:~/2013_WORK/AntonG/hanoy$ ./hanoy 5
размер пирамиды: n=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
olej@notebook:~/2013_WORK/AntonG/hanoy$ ./hanoy 6
размер пирамиды: n=6
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,
1 => 2, 3 => 1, 3 => 2, 1 => 2, 3 => 1,
2 => 3, 2 => 1, 3 => 1, 3 => 2, 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, 2 => 1,
3 => 1, 3 => 2, 1 => 2, 3 => 1, 2 => 3,
2 => 1, 3 => 1, 2 => 3, 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,
общее число перемещений 63
olej@notebook:~/2013_WORK/AntonG/hanoy$ ./hanoy 7
размер пирамиды: n=7
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, 1 => 2, 3 => 2, 3 => 1, 2 => 1,
3 => 2, 1 => 3, 1 => 2, 3 => 2, 3 => 1,
2 => 1, 2 => 3, 1 => 3, 2 => 1, 3 => 2,
3 => 1, 2 => 1, 3 => 2, 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, 2 => 1,
3 => 2, 3 => 1, 2 => 1, 3 => 2, 1 => 3,
1 => 2, 3 => 2, 3 => 1, 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, 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,
общее число перемещений 127
Так что конец света - близок!
Боюсь, что без правильного ответа не запомнют
