Форум » C/C++ для начинающих (C/C++ for beginners) » Рекурсивная функция разбиения массива на две партиции по заданному условию » Ответить
Рекурсивная функция разбиения массива на две партиции по заданному условию
Сыроежка: Еще одно упражнение на рекурсию для начинающих программистов, изучающих язык C, появившееся на сайте Stackoverflow. Требуется написать рекурсивную функцию, которая упорядочивает элементы массива таким образом, что элементы массива, меньшие значения произвольно заданного числа, располагаются в левой части массива, а остальные элементы массива, которые не удовлетворяют указанному условию, располагаются в правой части массива. Например, если имеется массив со следующими элементами { 4, 6, 2, 9, 1, 7, 3, 10 } и задано число 5, то результатом работы функции будет переупорядоченный массив вида { 4, 3, 2, 1, 9, 7, 6, 10 }. Функцию вывода на консоль исходного и результирующего массивов также требуется сделать рекурсивной. Прежде, чем познакомиться с готовым решением, представленным в следующем сообщении данной темы, попробуйте самостоятельно выполнить данное задание.
Ответов - 1
Сыроежка: Вот как могут выглядеть реализации соответствующих рекурсивных функций, описанных в предыдущем сообщении. [pre2] #include <stdio.h> void partition( int a[], size_t n, int pivot ) { if ( !( n < 2 ) ) { if ( *a < pivot ) { partition( a + 1, n - 1, pivot ); } else { if ( *( a + n - 1 ) < pivot ) { int tmp = *a; *a = *( a + n - 1 ); *( a + n - 1 ) = tmp; partition( a + 1, n - 2, pivot ); } else { partition( a, n - 1, pivot ); } } } } void printArray( const int a[], size_t n ) { n == 0 ? ( void )putchar( '\n' ) : ( printf( "%d ", *a ), printArray( a + 1, n - 1 ) ); } int main(void) { int a[] = { 4, 6, 2, 9, 1, 7, 3, 10 }; const size_t N = sizeof( a ) / sizeof( *a ); printArray( a, N ); int pivot = 5; partition( a, N, pivot ); printArray( a, N ); return 0; }[/pre2] Вывод программы на консоль следующий [pre2] 4 6 2 9 1 7 3 10 4 3 2 1 9 7 6 10 [/pre2] Вот ссылка на исходный вопрос на Stackoverflow C Sorting without loops with recursion (kind of)
полная версия страницы