On-line: гостей 0. Всего: 0 [подробнее..]
Программисты всех стран, объединяйтесь!

АвторСообщение



ссылка на сообщение  Отправлено: 16.12.18 12:52. Заголовок: Рекурсивная C функция поиска максимального элемента в массиве


Данная тема создана мною на основе вопроса a function that works with arrays, заданного на сайте Stackoverflow.

Требуется написать рекурсивную функцию на языке C, которая находит максимальный элемент массива.

Функция в числе параметров должна принимать два указателя. Один указатель указывает на первый элемент массива, а второй указатель указывает на память, сразу следующую за последним элементом массива.

Если разность этих указателей составляет один элемент, то функция возвращает первый указатель (В исходном вопросе функция возвращает значение, указываемое указателем. Однако такой подход в общем случае некорректный, так как исходный массив может быть "пустым", то есть переданные указатели могут задавать пустой диапазон, когда они равны друг другу. В этом случае разыменование указателя приведет к неопределенному поведению функции.).

В противном случае функция вызывает сама себя два раза. В первом вызова функции ей передается исходный указатель на начало массива (диапазона) и указатель на середину массива. Во втором вызове функции ей передается указатель на середину массива (диапазона) и указатель на память, сразу следующую за последним элементом массива (диапазона). То есть массив (диапазон) делится пополам на две части, и для каждой части снова вызывается функция. Затем значения элементов массива, указываемые возвращаемыми указателями вызовов функции сравниваются между собой, и в итоге возвращается пользователю указатель, указывающий на максимальный элемент массива.

Для начала попробуем написать эту функцию на C++, чтобы затем в сравнении было бы проще выявить те соглашения, которым должна следовать аналогичная функция на C.

Чтобы функция могла быть использована с любыми контейнерами, которые имеют итераторы произвольного доступа (Хотя на самом деле реализация функции, которая будет показана ниже может работать и с последовательными итераторами, но она будет менее эффективна, так как нахождение середины массива имеет сложность O( n ). А также так как аналогичная C функция будет иметь дело с указателями, то речь идет об итераторах произвольного доступа), а не только с массивами, функцию следует сделать шаблонной, принимающей в качестве параметров два итератора,задающих исходный диапазон элементов следующим образом [first, last ).

Как уже было отмечено выше, функции следует возвращать итератор, указывающий на максимальный элемент, а не само значение максимального элемента, так как в общем случае переданный функции диапазон в виде двух итераторов может быть пустым. В этом случае нельзя разыменовывать возвращаемый итератор.

Ниже в демонстрационной программе приведена реализация требуемой функции на C++.
 
#include <iostream>
#include <iterator>

template <typename ForwardIterator, typename Comparator>
ForwardIterator max_element( ForwardIterator first,
ForwardIterator last,
Comparator cmp )
{
if ( first == last || std::next( first ) == last )
{
return first;
}
else
{
auto middle = std::next( first, std::distance( first, last ) / 2 );

auto left = max_element( first, middle, cmp );
auto right = max_element( middle, last, cmp );

return cmp( *left, *right ) ? right : left;
}
}

bool cmp_double( const double &a, const double &b )
{
return a < b;
}

int main()
{
double a[] = { 4.3, 15.1, 2.2, -3.4, 18.1, 1.1, 3.0 };

for ( double d : a ) std::cout << d << ' ';
std::cout << '\n';

auto max = max_element( std::begin( a ), std::end( a ), cmp_double );

std::cout << "Maximum element is " << *max
<< " at position " << max - a << '\n';

return 0;
}

Вывод программы на консоль
 
4.3 15.1 2.2 -3.4 18.1 1.1 3
Maximum element is 18.1 at position 4

Теперь, имея реализацию функции на C++, можно написать соответствующую функцию на C.
Во-первых, желательно, чтобы соответствующая функция на C, могла работать с любыми типами массивов, как это делают стандартные C функции bsearch и qsort.

Следовательно, функция должна принимать два указателя типа const void *, а также требуется передать размер элемента массива и указатель на функцию сравнения элементов, которая будет задавать общий алгоритм сравнения элементов произвольных массивов.

Ниже показана, как может быть реализована соответствующая рекурсивная функция на C, которая сможет работать с массивами произвольного типа.
 
#include <stdio.h>

void * max_element( const void *first, const void *last, size_t size,
int cmp( const void *, const void * ) )
{
if ( first == last || ( const char * )first + size == last )
{
return ( void * )first;
}
else
{
size_t n = ( ( const char * )last - ( const char * )first ) / size / 2;
void *left = max_element( first, ( const char * )first + n * size, size, cmp );
void *right = max_element( ( const char * )first + n * size, last, size, cmp );

return cmp( left, right ) < 0 ? right : left;
}
}

int cmp_double( const void *p, const void *q )
{
double left = *( const double * )p;
double right = *( const double * )q;

return ( right < left ) - ( left < right );
}

int main(void)
{
double a[] = { 4.3, 15.1, 2.2, -3.4, 18.1, 1.1, 3.0 };
const size_t N = sizeof( a ) / sizeof( *a );

for ( size_t i = 0; i < N; i++ ) printf( "%.1f ", a[ i ] );
putchar( '\n' );

double *max = max_element( a, a + N, sizeof( *a ), cmp_double );

printf( "Maximum element is %.1f at position %zu\n",
*max, ( size_t )( max - a ) );

return 0;
}

Вывод программы на консоль:
 
4.3 15.1 2.2 -3.4 18.1 1.1 3.0
Maximum element is 18.1 at position 4

В исходном вопросе на Stackoverflow и в представленном там лучшем ответе приводится частная реализация функции для массивов типа double[].

Если потребуется. например, выполнить поставленную задачу для массивов типа int[], то придется дублировать код и писать новую функцию с новым названием так как в C нет перегрузки функций.

К тому же параметры функции следует объявить с квалификатором const, то есть они должны иметь тип const void *.

Более того функция в выбранном лучшим ответе имеет неопределенное поведение, когда заданный диапазон элементов, переданный через указатели, может быть пустым, то есть когда два указателя равны друг другу.

Кстати сказать, похожий вопрос был также ранее задан на Stackoverflow, на который там же я предоставил свой ответ. Смотрите вопрос Calculating the maximum number of an array by divide and conquer algorithm

Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 1 [только новые]





ссылка на сообщение  Отправлено: 22.12.18 17:39. Заголовок: #include <iostre..


Вернемся к реализациям функций max_element, показанных в предыдущем сообщении.

Реализации C++ функции max_element для последовательных итераторов не является эффективной, так как проход по элементам последовательности происходит дважды: один раз в функции std::distance и второй раз в функции std::next.

Поэтому эту функцию следует специализировать для последовательных итераторов и итераторов произвольного доступа.

Также поместим функцию в пользовательское пространство имен usr, чтобы она не конфликтовала со стандартной функцией std::max_element. Альтернативой было бы просто переименование этой функции.

Ниже в демонстрационной программе приведена новая реализация рекурсивной функции max_element.

 
#include <iostream>
#include <type_traits>
#include <forward_list>
#include <iterator>
#include <algorithm>

namespace usr
{

template <typename ForwardIterator, typename Compare>
ForwardIterator max_element( ForwardIterator first,
ForwardIterator last,
typename std::iterator_traits<ForwardIterator>::difference_type n,
Compare cmp )
{
ForwardIterator middle;

return n < 2 ? first
: ( middle = std::next( first, n / 2 ),
std::max( usr::max_element( first, middle, n / 2, cmp ),
usr::max_element( middle, last, n - n / 2, cmp ),
[&]( const auto &first, const auto &second )
{ return cmp( *first, *second ); } ) );
}

template <typename ForwardIterator, typename Compare>
ForwardIterator max_element( ForwardIterator first,
ForwardIterator last,
Compare cmp )
{
ForwardIterator middle;
auto n = std::distance( first, last );

if constexpr ( std::is_same_v<std::random_access_iterator_tag,
typename std::iterator_traits<ForwardIterator>::iterator_category> )
{
return n < 2 ? first
: ( middle = std::next( first, n / 2 ),
std::max( usr::max_element( first, middle, cmp ),
usr::max_element( middle, last, cmp ),
[&]( const auto &first, const auto &second )
{ return cmp( *first, *second ); } ) );
}
else
{
return n < 2 ? first
: ( middle = std::next( first, n / 2 ),
std::max( usr::max_element( first, middle, n / 2, cmp ),
usr::max_element( middle, last, n - n / 2, cmp ),
[&]( const auto &first, const auto &second )
{ return cmp( *first, *second ); } ) );
}
}

} // end of namespace usr

bool cmp_double( const double &a, const double &b )
{
return a < b;
}

int main()
{

{
double a[] = { 4.3, 15.1, 2.2, -3.4, 18.1, 1.1, 3.0 };

for ( double d : a ) std::cout << d << ' ';
std::cout << '\n';

auto max = usr::max_element( std::begin( a ), std::end( a ), cmp_double );

std::cout << "Maximum element is " << *max
<< " at position " << std::distance( std::begin( a ), max ) << '\n';
}

{
std::forward_list<double> lst = { 4.3, 15.1, 2.2, -3.4, 18.1, 1.1, 3.0 };

for ( double d : lst ) std::cout << d << ' ';
std::cout << '\n';

auto max = usr::max_element( std::begin( lst ), std::end( lst ), cmp_double );

std::cout << "Maximum element is " << *max
<< " at position " << std::distance( std::begin( lst ), max ) << '\n';
}

}

Вывод программы на консоль:
 
4.3 15.1 2.2 -3.4 18.1 1.1 3
Maximum element is 18.1 at position 4
4.3 15.1 2.2 -3.4 18.1 1.1 3
Maximum element is 18.1 at position 4

Соответственно, рекурсивная функция на C может выглядеть следующим образом, как показано в демонстрационной программе ниже.
 
#include <stdio.h>

void * max_element( const void *first, const void *last, size_t size,
int cmp( const void *, const void * ) )
{
void *left, *right;
size_t n = ( ( const char * )last - ( const char * )first ) / size;

return n < 2 ? ( void * )first
: ( left = max_element( first, ( const char * )first + n / 2 * size, size, cmp ),
right = max_element( ( const char * )first + n / 2 * size, last, size, cmp ),
( cmp( left, right ) < 0 ? right : left ) );
}

int cmp_double( const void *p, const void *q )
{
double left = *( const double * )p;
double right = *( const double * )q;

return ( right < left ) - ( left < right );
}

int main(void)
{
double a[] = { 4.3, 15.1, 2.2, -3.4, 18.1, 1.1, 3.0 };
const size_t N = sizeof( a ) / sizeof( *a );

for ( size_t i = 0; i < N; i++ ) printf( "%.1f ", a );
putchar( '\n' );

double *max = ( double * )max_element( a, a + N, sizeof( *a ), cmp_double );

printf( "Maximum element is %.1f "
" at position %zu\n", *max, ( size_t )( max - a ) );

return 0;
}

Вывод программы на консоль:
 
4.3 15.1 2.2 -3.4 18.1 1.1 3.0
Maximum element is 18.1 at position 4


Спасибо: 0 
ПрофильЦитата Ответить
Ответ:
1 2 3 4 5 6 7 8 9
большой шрифт малый шрифт надстрочный подстрочный заголовок большой заголовок видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки моноширинный шрифт моноширинный шрифт горизонтальная линия отступ точка LI бегущая строка оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 31
Права: смайлы да, картинки да, шрифты да, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет